Skip to Main content Skip to Navigation
Conference papers

Linearly-Homomorphic Signatures and Scalable Mix-Nets

Chloé Hébant 1, 2 Duong Hieu Phan 3 David Pointcheval 1, 2
1 CASCADE - Construction and Analysis of Systems for Confidentiality and Authenticity of Data and Entities
Inria de Paris, CNRS - Centre National de la Recherche Scientifique : UMR 8548, DI-ENS - Département d'informatique de l'École normale supérieure
Abstract : Anonymity is a primary ingredient for our digital life. Several tools have been designed to address it such as, for authentication, blind signatures, group signatures or anonymous credentials and, for confidentiality, randomizable encryption or mix-nets. When it comes to complex electronic voting schemes, random shuffling of authenticated ciphertexts with mix-nets is the only known tool. However, it requires huge and complex zero-knowledge proofs to guarantee the actual permutation of the initial ciphertexts in a privacy-preserving way. In this paper, we propose a new approach for proving correct shuffling of signed ElGamal ciphertexts: the mix-servers can simply randomize individual ballots, which means the ciphertexts, the signatures, and the verification keys, with an additional global proof of constant size, and the output will be publicly verifiable. The security proof is in the generic bilinear group model. The computational complexity for the each mix-server is linear in the number of ballots. Verification is also linear in the number of ballots, but independent of the number of rounds of mixing. This leads to a new highly scalable technique. Our construction makes use of linearly-homomorphic signatures, with new features, that are of independent interest.
Document type :
Conference papers
Complete list of metadatas
Contributor : David Pointcheval <>
Submitted on : Wednesday, September 23, 2020 - 11:22:33 PM
Last modification on : Wednesday, October 14, 2020 - 3:52:20 AM




Chloé Hébant, Duong Hieu Phan, David Pointcheval. Linearly-Homomorphic Signatures and Scalable Mix-Nets. PKC 2020 - IACR International Conference on Practice and Theory of Public-Key Cryptography, Jun 2020, Edinburgh / Virtual, United Kingdom. pp.597-627, ⟨10.1007/978-3-030-45388-6_21⟩. ⟨hal-02947353⟩



Record views