Paper 2023/1499

Linearly-Homomorphic Signatures for Short Randomizable Proofs of Subset Membership

David Pointcheval, École Normale Supérieure - PSL

Electronic voting is one of the most interesting application of modern cryptography, as it involves many innovative tools (such as homomorphic public-key encryption, non-interactive zero-knowledge proofs, and distributed cryptography) to guarantee several a priori contradictory security properties: the integrity of the tally and the privacy of the individual votes. While many efficient solutions exist for honest-but-curious voters, that follow the official procedure but try to learn more than just the public result, preventing attacks from malicious voters is much more complex: when voters may have incentive to send biased ballots, the privacy of the ballots is much harder to satisfy, whereas this is the crucial security property for electronic voting. We present a new technique to prove that an ElGamal ciphertext contains a message from a specific subset (quasi-adaptive NIZK of subset membership), using linearly-homomorphic signatures. The proofs are both quite efficient to generate, allowing the use of low-power devices to vote, and randomizable, which is important for the strong receipt-freeness property. They are well-suited to prevent vote-selling and replay attacks, which are the main threats against the privacy in electronic voting, with security proofs in the generic group model and the random oracle model.

Available format(s)
Cryptographic protocols
Publication info
Published elsewhere. Major revision. E-Vote-ID conference 2023
NIZKElectronic Voting
Contact author(s)
david pointcheval @ ens fr
2023-10-03: approved
2023-10-01: received
See all versions
Short URL
Creative Commons Attribution


      author = {David Pointcheval},
      title = {Linearly-Homomorphic Signatures for Short Randomizable Proofs of Subset Membership},
      howpublished = {Cryptology ePrint Archive, Paper 2023/1499},
      year = {2023},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.