Pith. sign in

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 →

arxiv 1908.05127 v2 pith:HX7J3D6W submitted 2019-08-14 cs.CR

classification cs.CR MSC 94A60
keywords InternetvotingsecurityElGamalencryptiondiscretelogarithmquadraticresidueLegendresymbolsemanticsubgroupattackMoscowelection
verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

The paper reports two attacks on the encryption used in Moscow's September 2019 Internet voting experiment, both confirmed against the public source code and both fixed after disclosure. In the original revision, each ballot was encrypted with a three-level ElGamal construction over 256-bit prime fields; the paper shows that recovering the three private keys from the public keys by discrete logarithm takes minutes, so any ballot can be decrypted. In the modified revision, a single 1024-bit ElGamal encryption was used, but the message space was not restricted to the quadratic-residue subgroup generated by the encryption key, so the Legendre symbol of the second ciphertext component leaks whether the plaintext is a quadratic residue, breaking the scheme's semantic security. Because the plaintext is the candidate's identifier, this one-bit leak can reveal the vote when the leading candidates' identifiers fall into different residue classes.

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.

Watch

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

Editorial extensions of the paper, not claims the author makes directly.

  • 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.
Share X Bluesky LinkedIn Reddit HN

Signed reviews

No signed human review yet.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Referee Report

0 major / 3 minor

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)
  1. [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.
  2. [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.
  3. [References] Reference [12] contains a doubled article: 'An attack on the the encryption scheme...' should read 'An attack on the encryption scheme...'.

Circularity Check

0 steps flagged · score 0.0 of 10

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 0 free parameters · 5 assumptions · 0 invented entities

The attacks are mounted against an external system whose code and keys are public; no constants are fitted and no entities are invented. The only assumptions the claims rest on beyond standard finite-field and ElGamal background are empirical facts about the deployed code (key sizes, message encoding, payload structure) and the contingent distribution of deputy IDs, which limits the reach of the second attack rather than the validity of the semantic-security break.

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].
    Stated in Section 2.2 as the state of the code after the first fix; the Legendre-symbol distinguisher depends on exactly this mismatch between the message space (all integers) and the encrypted subgroup Q_p.
  • 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.
    Section 2.3: "the deputy ids seem to be chosen at random with no specific arithmetic property." This assumption converts the one-bit leakage into a vote-counting attack in plausible two-candidate races; it is not guaranteed by the scheme.
  • 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.
    Section 2.3 derives this from the voting-form source code. Both attacks aim at this payload, and the second attack's real-world utility relies on the mapping being public.
  • 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.
    This is the mathematical backbone of the semantic-security argument in Section 2.2; it is textbook material.
  • 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.
    Section 2.1 describes the multilevel ElGamal and the enforcement; the first attack needs only these sizes.

how reviews work

0 comments
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.

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

34 extracted references · 34 canonical work pages

  1. [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

  2. [2]

    Alex Halderman, Nadia Heninger, Drew Springall, Emmanue l Thomé, Luke Valenta, Ben- jamin VanderSloot, Eric Wustrow, Santiago Zanella Béguelin , and Paul Zimmermann

    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...

  3. [3]

    Ethereum white paper, 2013

    Vitalik Buterin. Ethereum white paper, 2013. GitHub repo sitory: https://github.com/ethereum/wiki/wiki/White-Paper

  4. [4]

    Ha ndbook of MAGMA functions,

    John Cannon, Wieb Bosma, Claus Fieker, and Allan Steel. Ha ndbook of MAGMA functions,

  5. [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

  6. [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

  7. [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

  8. [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

Show all 34 references
  1. [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

  2. [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

  3. [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

  4. [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

  5. [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

  6. [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

  7. [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/

  8. [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

  9. [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

  10. [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

  11. [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

  12. [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

  13. [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

  14. [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

  15. [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

  16. [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,

  17. [25]

    Schirokauer

    O. Schirokauer. Discrete logarithms and local units. Philos. Trans. Roy. Soc. London Ser. A , 345(1676):409–423, 1993

  18. [26]

    Swiss On-line Voting Protocol, 2016

    Scytl. Swiss On-line Voting Protocol, 2016. Manuscrip t

  19. [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/

  20. [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/

  21. [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

  22. [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

  23. [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

  24. [32]

    Modern computer algebra

    Joachim Von Zur Gathen and Jürgen Gerhard. Modern computer algebra. Cambridge university press, 2013. Third edition

  25. [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 ...

  26. [2006]

    http://magma.maths.usyd.edu.au/magma/handbook/

Pith tools

Reviewed August 14, 2026 · model on record in the stance chip above.