Abstract
We show how to prove in honest verifier zero-knowledge the correctness of a shuffe of homomorphic encryptions (or homomorphic commitments.) A shuffe consists in a rearrangement of the input ciphertexts and a reencryption of them so that the permutation is not revealed. Our scheme is more efficient than previous schemes both in terms of communication complexity and computational complexity. Indeed, in the case of shuffling ElGamal encryptions, the proof of correctness is smaller than the encryptions themselves.
Basic Research in Computer Science (www.brics.dk), funded by the Danish National Research Foundation.
Chapter PDF
Similar content being viewed by others
Keywords
These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.
References
R. Cramer, I. Damgård and B. Schoenmakers, “Proofs of Partial Knowledge and Simplified Design of Witness Hiding Protocols”, CRYPTO’ 94, LNCS series, volume 893: p. 174–187, 1994146
I. Damgård and E. Fujisaki, “An Integer Commitment Scheme based on Groups with Hidden Order”, Cryptology ePrint Archive, Report 2001/064, 2001 148
I. Damgård and M. J. Jurik, “A Generalisation, a Simplification and Some Applications of Paillier’s Probabilistic Public-Key System”, PKC 2001, LNCS series, volume 1992: p. 119–136, 2001 150, 151
J. Furukawa and K. Sako, “An Efficient Scheme for Proving a Shuffle”, CRYPTO’ 01, LNCS series, volume 2139: p. 368–387, 2001 145, 146, 159
M. Jakobson, A. Juels and R. L. Rivest, “Making Mix Nets Robust for Electronic Voting by Randomized Partial Checking”, USENIX Security’ 02, 2002 146
A. Neff, “A Verifiable Secret Shuffle and its Application to E-Voting”, ACM CCS’ 01: p. 116–125, 2001 145, 146, 147, 151
P. Paillier, “Public-key cryptosystems based on composite residuosity classes”, EUROCRYPT’ 99, LNCS series, volume 1592: p. 223–239, 1999 150
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2003 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Groth, J. (2003). A Verifiable Secret Shuffe of Homomorphic Encryptions. In: Desmedt, Y.G. (eds) Public Key Cryptography — PKC 2003. PKC 2003. Lecture Notes in Computer Science, vol 2567. Springer, Berlin, Heidelberg. https://doi.org/10.1007/3-540-36288-6_11
Download citation
DOI: https://doi.org/10.1007/3-540-36288-6_11
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-00324-3
Online ISBN: 978-3-540-36288-3
eBook Packages: Springer Book Archive