REVIEW 3 minor 34 references
Breaking the encryption scheme of the Moscow Internet voting system
T0 review · 0 major / 3 minor · reviewed 2026-08-14 · deepseek-v4-flash
Pith's one-line read The Moscow Internet voting system's ElGamal encryption was broken in both tested versions: the first via fast discrete-logarithm key recovery, the second via a one-bit quadratic-residue leak.
desk verdict The paper delivers two reproducible breaks of a real deployed e-voting encryption; the techniques are old but the applied result is solid and deserves review. read the letter →
The pith
A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.
The reading
What carries the argument
The first mechanism is discrete-logarithm computation modulo primes of about 256 bits via the General Number Field Sieve; the identity that carries the attack is $sk = \log_g pk$, and because each $p_i$ is small enough the logarithm is computable in seconds to minutes. The second mechanism is a quadratic-residue test: with $p = 2q+1$, generator $g \in Q_p$, and message $m \in [1,q-1]$, the second ciphertext component satisfies $b = pk^r m$, and the Legendre symbol $\left(\frac{b}{p}\right)$ equals $\left(\frac{m}{p}\right)$, giving an efficient distinguisher. The paper thus shows that the scheme's security rests on two things: sufficiently large prime groups, and encoding the message inside the group generated by the encryption key. When either condition fails, vote secrecy leaks.
What would settle it
Run the paper's key-recovery procedure against the published public keys of the original revision and time it; if a private key cannot be recovered within an hour on comparable hardware, the claim of minute-scale recovery fails. For the second attack, compute the residue class of every candidate identifier for an election run under the modified scheme; if all identifiers of viable candidates lie in one class, the leaked bit distinguishes nothing.
Extended reading notes
Core claim
The central claim is that neither of the two tested versions of the Moscow Internet voting system's ElGamal encryption was secure. For revision d70986b2c4da, the three 256-bit primes make the discrete logarithm of each public key computable with a number field sieve implementation in 314 to 507 seconds, giving an attacker the three private keys and full decryption of all ballots. For revision 1d4f348681e9, although the generator was moved to the quadratic-residue subgroup of a 1024-bit safe prime, the message was still any integer in $[1, q-1]$; therefore the Legendre symbol of $b = pk^r \cdot m$ immediately says whether $m$ is a quadratic residue, and the scheme is not semantically secure. The paper demonstrates this leak on the published test data: exactly five of ten published ciphertexts had $b$ a quadratic residue, and in the August 28 test the two candidate identifiers were one in each class, so every vote would have been decodable.
Load-bearing premise
For the one-bit leak to reveal which candidate a voter chose, the two leading candidates' identifier numbers must fall into different classes under the scheme's residue test; the paper assumes that is likely because the identifiers look random, but it is not guaranteed by the scheme.
Editorial extensions
If this is right
- Under the original revision, an attacker who reads the blockchain can decrypt every ballot as soon as the three public keys are published, which is before or during the election; the 12-hour challenge window is irrelevant because key recovery takes minutes.
- Under the modified revision, computing one Legendre symbol per ciphertext recovers one bit of every plaintext; in the Moscow protocol that bit distinguishes between a voter's two main candidates whenever their deputy IDs lie in different quadratic-residue classes.
- Both attacks were validated against real published data: the three private keys of the original system were recovered in 314 to 507 seconds each, and in the modified system five of ten published test ciphertexts corresponded to quadratic non-residues.
- The fix adopted for the final election, squaring the message before encryption, closes the Legendre-symbol leak, but the paper notes the 1024-bit prime remains too small for medium-term security and that textbook ElGamal is not IND-CCA2, so future protocol changes could reintroduce exploitable weaknesses.
Reading between the lines
- A general screening rule for any ElGamal-based system follows: if the generator lives in a proper subgroup, the encryption routine must test that every plaintext lies in that subgroup, otherwise any multiplicative character of the group leaks one bit.
- The residue split is easy to audit in advance: an election authority could list the Legendre symbol of every candidate identifier before the vote, and in any election where the two front-runners fall on opposite sides the modified scheme is a full vote-revealer, not just a one-bit curiosity.
- A less obvious consequence is that the leaked bit is a deterministic fingerprint of a candidate: even if ballots are rerandomized, the Legendre symbol of the ciphertext's second component stays fixed for a given candidate, which could allow linking multiple encryptions of the same choice.
Signed reviews
Editorial analysis
A structured set of objections, weighed in public.
Referee Report
Summary. The paper analyzes the encryption used by the Moscow Internet voting system at two revisions. In the original revision (d70986b2c4da), the system uses a triple-nested ElGamal over finite fields with three 256-bit safe primes; the authors show via CADO-NFS discrete-log computations that the secret keys can be recovered from the public keys in roughly five to nine minutes per key on a desktop machine, and they provide a shell script and measured timings. In the modified revision (1d4f348681e9), after the key size was increased to 1024 bits and the scheme simplified, the authors identify a subgroup/one-bit leak: because the generator lies in the quadratic-residue subgroup while plaintexts are arbitrary small integers, the Legendre symbol of the second ciphertext component equals that of the plaintext. This is a distinguisher that breaks semantic security. They verify the bit split in the published test ciphertexts (five out of ten) and show in Appendix C that in the August 28 test the two candidates' IDs fell in opposite quadratic-residue classes, so the leaked bit would have distinguished the two candidates. The paper also discusses the protocol-level consequences and the final fix (squaring the plaintext before encryption).
Significance. The first attack is a reproducible, precisely documented break of a deployed e-voting encryption scheme: exact git revisions, a public toolchain, and measured running times are given. The second attack is a clean and correct distinguisher argument that does not rely on fitted parameters or unstated assumptions; it demonstrates how a subtle encoding error converts standard ElGamal into a scheme that is not semantically secure. The paper is more than a catalog of mistakes: it gives concrete evidence of the leak's practical relevance while honestly acknowledging the contingency that the vote-counting scenario requires the candidate IDs to be split between quadratic-residue classes. The appendices with scripts and data are a strength of the paper. If the claims hold, this is a significant case study for both the cryptographic and e-voting communities.
minor comments (3)
- [Section 2.2] The symbol q denotes both the subgroup order (p = 2q + 1) and the upper bound of the plaintext interval [1, q−1] in the same section. This is mathematically consistent, but a sentence clarifying that [1, q−1] is a set of integers mapped into F_p^*, and that the Legendre symbols are computed modulo p, would remove a likely source of confusion.
- [Section 3.2] The description of the sign choice after taking the square root ('the sign choice is based on the relative size of p − m and m') is terse; please spell out that only one of the two square roots lies in the small interval corresponding to a 32-bit deputy id, which is what allows unambiguous decryption.
- [References] Reference [12] contains a doubled article: 'An attack on the the encryption scheme...' should read 'An attack on the encryption scheme...'.
Circularity Check
No significant circularity: both attacks are self-contained cryptanalyses of an externally deployed system.
full rationale
The paper's central claims are attacks on a real, externally deployed voting system whose source code, public keys, and ciphertexts were published independently of the authors. The first attack derives the private keys by computing discrete logarithms in 256-bit prime fields with CADO-NFS; the primes, generators, and public keys come from the deployed repository, and the running times are experimental measurements, not fitted parameters. The second attack derives a one-bit distinguisher from the algebraic structure of ElGamal: because the generator and public key are quadratic residues, the second ciphertext component is a quadratic residue if and only if the plaintext is. This follows from the paper's own equations and the law of quadratic reciprocity, and the authors verify it against the published encrypted ballots, finding exactly five of ten quadratic residues. The paper explicitly acknowledges in Section 2.3 that turning this distinguisher into a vote-counting attack requires the relevant candidate deputy IDs to fall into different quadratic-residue classes; that is an honest statement of an empirical contingency, not a hidden assumption that makes the derivation circular. The only self-citations are references to the authors' own earlier preprints [9] and [12], disclosed in the footnote as the source of the merged material; these citations are provenance, not load-bearing mathematical evidence. Consequently, none of the identified circularity patterns applies, and the derivation is self-contained against external benchmarks.
Assumptions & free parameters
assumptions (5)
- domain assumption The modified implementation uses F_p^* with a safe prime p=2q+1 and a generator g that is a quadratic residue of prime order q, while messages m may be any integer in [1, q-1].
- domain assumption Candidate deputy IDs are 32-bit unsigned integers with no arithmetic structure relevant to quadratic residuosity, so roughly half of them fall in Q_p.
- domain assumption Each encrypted ballot consists solely of the 32-bit deputy ID, and the public mapping from deputy IDs to candidate names is available in the client-side JavaScript.
- standard math Standard number-theoretic facts: quadratic reciprocity gives an efficient Legendre-symbol algorithm, and DDH is false when messages are not restricted to the subgroup generated by g.
- domain assumption In the original version the primes p_i are safe primes with p_i < 2^256 and p1<p2<p3, as enforced in the source code.
Cite this review
Pith. "Pith review of Breaking the encryption scheme of the Moscow Internet voting system." pith.science (2026). https://pith.science/paper/HX7J3D6W
@misc{pith2026190805127,
author = {Pith},
title = {Pith review of: Breaking the encryption scheme of the Moscow Internet voting system},
year = {2026},
howpublished = {\url{https://pith.science/paper/HX7J3D6W}},
note = {Machine review of arXiv:1908.05127}
}
read the original abstract
In September 2019, voters for the election at the Parliament of the city of Moscow were allowed to use an Internet voting system. The source code of it had been made available for public testing. In this paper we show two successful attacks on the encryption scheme implemented in the voting system. Both attacks were sent to the developers of the system, and both issues had been fixed after that.The encryption used in this system is a variant of ElGamal over finite fields. In the first attack we show that the used key sizes are too small. We explain how to retrieve the private keys from the public keys in a matter of minutes with easily available resources.When this issue had been fixed and the new system had become available for testing, we discovered that the new implementation was not semantically secure. We demonstrate how this newly found security vulnerability can be used for counting the number of votes cast for a candidate.
Reference graph
Works this paper leans on
-
[1]
Electing a university president using open-audit voting: Analysis of real-world use of Helios
Ben Adida, Olivier De Marneffe, Olivier Pereira, and Jean- Jacques Quisquater. Electing a university president using open-audit voting: Analysis of real-world use of Helios. In Proceedings of the 2009 Conference on Electronic Voting Technology/Wor kshop on Trustworthy Elections , EVT/WOTE’09, pages 10–10. USENIX, 2009. 11
work page 2009
-
[2]
David Adrian, Karthikeyan Bhargavan, Zakir Durumeric, P ierrick Gaudry, Matthew Green, J. Alex Halderman, Nadia Heninger, Drew Springall, Emmanue l Thomé, Luke Valenta, Ben- jamin VanderSloot, Eric Wustrow, Santiago Zanella Béguelin , and Paul Zimmermann. Imper- fect forward secrecy: How Diffie-Hellman fails in practice. I n ACM CCS 15: 22nd Conference on C...
work page 2015
-
[3]
Vitalik Buterin. Ethereum white paper, 2013. GitHub repo sitory: https://github.com/ethereum/wiki/wiki/White-Paper
work page 2013
-
[4]
John Cannon, Wieb Bosma, Claus Fieker, and Allan Steel. Ha ndbook of MAGMA functions,
-
[5]
SoK: Verifiability notions for e-voting protocols
Véronique Cortier, David Galindo, Ralf Küsters, Johann es Mueller, and Tomasz Truderung. SoK: Verifiability notions for e-voting protocols. In IEEE Symposium on Security and Privacy (S&P 2016) , pages 779–798. IEEE, 2016
work page 2016
-
[6]
Continued fraction s and lattice sieving
Jens Franke and Thorsten Kleinjung. Continued fraction s and lattice sieving. In Special-Purpose Hardware for Attacking Cryptographic Systems–SHARCS , 2005. 40 pages
work page 2005
-
[7]
A kilobit hidden SNFS discrete logarithm computation
Joshua Fried, Pierrick Gaudry, Nadia Heninger, and Emma nuel Thomé. A kilobit hidden SNFS discrete logarithm computation. In EUROCRYPT 2017, volume 10210 of LNCS, pages 202–231. Springer, 2017
work page 2017
-
[8]
2015 N euchâtel’s cast-as-intended verifica- tion mechanism
David Galindo, Sandra Guasch, and Jordi Puiggali. 2015 N euchâtel’s cast-as-intended verifica- tion mechanism. In 5th International Conference on E-Voting and Identity, (Vo teID’15), pages 3–18, 2015
work page 2015
Show all 34 references
-
[9]
Breaking the encryption scheme of the Mo scow internet voting system
Pierrick Gaudry. Breaking the encryption scheme of the Mo scow internet voting system. arXiv:1908.05127, 2019
1908 arXiv
-
[10]
https://github.com/moscow-technologies/blockchain-voting, 2019
Public source code of the Moscow internet voting system . https://github.com/moscow-technologies/blockchain-voting, 2019
2019
-
[11]
The Norwegian Internet voting prot ocol
Kristian Gjøsteen. The Norwegian Internet voting prot ocol. In E-Voting and Identity , volume 7187 of LNCS, pages 1–18. Springer, 2012
2012
-
[12]
An attack on the the encryption sch eme of the Moscow internet voting system
Alexander Golovnev. An attack on the the encryption sch eme of the Moscow internet voting system. arXiv:1908.09170, 2019
1908 arXiv
-
[13]
Internet voting in a local election in Canada
Nicole J Goodman. Internet voting in a local election in Canada. In The Internet and Democ- racy in Global Perspective , pages 7–24. Springer, 2014
2014
-
[14]
A verifiable secret shuffle of homomorphic enc ryptions
Jens Groth. A verifiable secret shuffle of homomorphic enc ryptions. Journal of Cryptology , 23(4):546–579, 2010
2010
-
[15]
Swiss Post public intrusion test – Generat ing random group elements, 2019
Rolf Haenni. Swiss Post public intrusion test – Generat ing random group elements, 2019. Preprint: https://e-voting.bfh.ch/publications/2019/
2019
-
[16]
Koenig, Philipp Locher, and Eric Du buis
Rolf Haenni, Reto E. Koenig, Philipp Locher, and Eric Du buis. CHVote system specification. Cryptology ePrint Archive, Report 2017/325, 2017. https://eprint.iacr.org/2017/325. 12
2017
-
[17]
Verifiable internet vot ing in Estonia
Sven Heiberg and Jan Willemson. Verifiable internet vot ing in Estonia. In 2014 6th Inter- national Conference on Electronic Voting: Verifying the Vo te (EVOTE) , pages 1–8. IEEE, 2014
2014
-
[18]
Joux and R
A. Joux and R. Lercier. Improvements to the general numb er field sieve for discrete logarithms in prime fields. A comparison with the gaussian integer metho d. Mathematics of Computation , 72(242):953–967, 2003
2003
-
[19]
Computation of a 768-bit prime field discrete logarithm
Thorsten Kleinjung, Claus Diem, Arjen K Lenstra, Chris tine Priplata, and Colin Stahlke. Computation of a 768-bit prime field discrete logarithm. In EUROCRYPT 2017, volume 10210 of LNCS, pages 185–201. Springer, 2017
2017
-
[20]
Internet voting in Russia: how? https://medium.com/@juliakrivonosova/internet-voting-in-russia-how-9382db4da71f , 2019
Julia Krivonosova. Internet voting in Russia: how? https://medium.com/@juliakrivonosova/internet-voting-in-russia-how-9382db4da71f , 2019
2019
-
[21]
A. K. Lenstra and H. W. Lenstra, Jr., editors. The development of the number field sieve , volume 1554 of Lecture Notes in Math. Springer-Verlag, 1993
1993
-
[22]
Trapdoor com- mitments in the SwissPost e-voting shuffle proof, 2019
Sarah Jamie Lewis, Olivier Pereira, and Vanessa Teague . Trapdoor com- mitments in the SwissPost e-voting shuffle proof, 2019. Blog no te: https://people.eng.unimelb.edu.au/vjteague/SwissVote.html
2019
-
[23]
A key recovery attack on d iscrete log-based schemes using a prime order subgroup
Chae Hoon Lim and Pil Joong Lee. A key recovery attack on d iscrete log-based schemes using a prime order subgroup. In CRYPTO’97, volume 1294 of LNCS, pages 249–263. Springer, 1997
1997
-
[24]
https://www.mos.ru/upload/documents/files/5381/Formal_Offer.pdf,
Public testing of the Internet voting system. https://www.mos.ru/upload/documents/files/5381/Formal_Offer.pdf,
-
[25]
Schirokauer
O. Schirokauer. Discrete logarithms and local units. Philos. Trans. Roy. Soc. London Ser. A , 345(1676):409–423, 1993
1993
-
[26]
Swiss On-line Voting Protocol, 2016
Scytl. Swiss On-line Voting Protocol, 2016. Manuscrip t
2016
-
[27]
CADO-NFS, an implement ation of the num- ber field sieve algorithm, 2019
The CADO-NFS Development Team. CADO-NFS, an implement ation of the num- ber field sieve algorithm, 2019. Development version fdae0f 9f382c, available from http://cado-nfs.gforge.inria.fr/
2019
-
[28]
PARI/GP version 2.11.0, 2018
The PARI Group. PARI/GP version 2.11.0, 2018. available from http://pari.math.u-bordeaux.fr/
2018
-
[29]
Sagemath, the Sage Mathematics So ftware System (Version 8.8), 2019
The Sage Developers. Sagemath, the Sage Mathematics So ftware System (Version 8.8), 2019. https://www.sagemath.org
2019
-
[30]
E. Thomé. Subquadratic computation of vector generati ng polynomials and improvement of the block Wiedemann algorithm. Journal of Symbolic Computation , 33(5):757–775, 2002
2002
-
[31]
Measuring small subgr oup attacks against Diffie- Hellman
Luke Valenta, David Adrian, Antonio Sanso, Shaanan Coh ney, Joshua Fried, Marcella Hastings, J Alex Halderman, and Nadia Heninger. Measuring small subgr oup attacks against Diffie- Hellman. In NDSS, 2017. 13
2017
-
[32]
Modern computer algebra
Joachim Von Zur Gathen and Jürgen Gerhard. Modern computer algebra. Cambridge university press, 2013. Third edition
2013
-
[33]
gp -q --default colors=\
Damian Weber, Thomas Denny, and Joerg Zayer. Discrete l ogarithms mod p: 215, 248 and 281 bit computation announcements on the NMBRTHRY mai ling list, 1995. https://listserv.nodak.edu/cgi-bin/wa.exe?A0=NMBRTHRY. 14 A A shell script for the first attack ## These are commands to ...
1995
-
[2006]
http://magma.maths.usyd.edu.au/magma/handbook/
Reviewed August 14, 2026 · model on record in the stance chip above.
Discussion (0). Continue with ORCID to comment.