Abstract
A shuffle consists of a permutation and re-encryption of a set of input ciphertexts. One application of shuffles is to build mix-nets. We suggest an honest verifier zero-knowledge argument for the correctness of a shuffle of homomorphic encryptions.
Our scheme is more efficient than previous schemes both in terms of communication and computation. The honest verifier zero-knowledge argument has a size that is independent of the actual cryptosystem being used and will typically be smaller than the size of the shuffle itself. Moreover, our scheme is well suited for the use of multi-exponentiation and batch-verification techniques.
Additionally, we suggest a more efficient honest verifier zero-knowledge argument for a commitment containing a permutation of a set of publicly known messages. We also suggest an honest verifier zero-knowledge argument for the correctness of a combined shuffle-and-decrypt operation that can be used in connection with decrypting mix-nets based on ElGamal encryption.
All our honest verifier zero-knowledge arguments can be turned into honest verifier zero-knowledge proofs. We use homomorphic commitments as an essential part of our schemes. When the commitment scheme is statistically hiding we obtain statistical honest verifier zero-knowledge arguments; when the commitment scheme is statistically binding, we obtain computational honest verifier zero-knowledge proofs.
Article PDF
Similar content being viewed by others
Avoid common mistakes on your manuscript.
References
M. Abe, Universally verifiable mix-net with verification work independent of the number of mix-servers, in EUROCRYPT. Lecture Notes in Computer Science, vol. 1403 (Springer, Berlin, 1998), pp. 437–447
M. Abe, F. Hoshino, Remarks on mix-network based on permutation networks, in PKC. Lecture Notes in Computer Science, vol. 1992 (Springer, Berlin, 2001), pp. 317–324
M. Abe, H. Imai, Flaws in some robust optimistic mix-nets, in ACISP. Lecture Notes in Computer Science, vol. 2727 (Springer, Berlin, 2003), pp. 39–50
M. Bellare, O. Goldreich, On defining proofs of knowledge, in CRYPTO. Lecture Notes in Computer Science, vol. 740 (Springer, Berlin, 1992), pp. 390–420
M. Bellare, P. Rogaway, Random oracles are practical: a paradigm for designing efficient protocols, in ACM CCS (1993), pp. 62–73
D. Boneh, P. Golle, Almost entirely correct mixing with applications to voting, in ACM CCS (2002), pp. 68–77
F. Brandt, Efficient cryptographic protocol design based on distributed ElGamal encryption, in ICISC. Lecture Notes in Computer Science, vol. 3935 (Springer, Berlin, 2006), pp. 32–47
D. Chaum, Untraceable electronic mail, return addresses, and digital pseudonyms. Commun. ACM 24(2), 84–88 (1981)
R. Cramer, V. Shoup, Design and analysis of practical public-key encryption schemes secure against adaptive chosen ciphertext attack, in CRYPTO. Lecture Notes in Computer Science, vol. 1462 (Springer, Berlin, 1998), pp. 13–25
R. Cramer, I. Damgård, B. Schoenmakers, Proofs of partial knowledge and simplified design of witness hiding protocols, in CRYPTO. Lecture Notes in Computer Science, vol. 893 (Springer, Berlin, 1994), pp. 174–187
I. Damgård, Efficient concurrent zero-knowledge in the auxiliary string model, in EUROCRYPT. Lecture Notes in Computer Science, vol. 1807 (Springer, Berlin, 2000), pp. 418–430
I. Damgård, E. Fujisaki, A statistically-hiding integer commitment scheme based on groups with hidden order, in ASIACRYPT. Lecture Notes in Computer Science, vol. 2501 (Springer, Berlin, 2002), pp. 125–142
I. Damgård, M.J. Jurik, A generalisation, a simplification and some applications of Paillier’s probabilistic public-key system, in PKC. Lecture Notes in Computer Science, vol. 1992 (Springer, Berlin, 2001)
I. Damgård, M.J. Jurik, A length-flexible threshold cryptosystem with applications, in ACISP. Lecture Notes in Computer Science, vol. 2727 (Springer, Berlin, 2003), pp. 350–364
Y. Desmedt, K. Kurosawa, How to break a practical MIX and design a new one, in EUROCRYPT. Lecture Notes in Computer Science, vol. 1807 (Springer, Berlin, 2000), pp. 557–572
T. ElGamal, A public key cryptosystem and a signature scheme based on discrete logarithms. IEEE Trans. Inf. Theory 31(4), 469–472 (1985)
J. Furukawa, Efficient and verifiable shuffling and shuffle-decryption. IEICE Trans. Fundam. Electron. Commun. Comput. Sci. 88-A(1), 172–188 (2005)
E. Fujisaki, T. Okamoto, Statistical zero knowledge protocols to prove modular polynomial relations, in CRYPTO. Lecture Notes in Computer Science, vol. 1294 (Springer, Berlin, 1997), pp. 16–30
J. Furukawa, H. Miyauchi, K. Mori, S. Obana, K. Sako, An implementation of a universally verifiable electronic voting scheme based on shuffling, in Financial Cryptography. Lecture Notes in Computer Science, vol. 2357 (Springer, Berlin, 2002), pp. 16–30
J. Furukawa, K. Sako, An efficient scheme for proving a shuffle, in CRYPTO. Lecture Notes in Computer Science, vol. 2139 (Springer, Berlin, 2001), pp. 368–387
J.A. Garay, P.D. MacKenzie, K. Yang, Strengthening zero-knowledge protocols using signatures. J. Cryptol. 19(2), 169–209 (2006)
P. Golle, A. Juels, Parallel mixing, in ACM CCS (2004), pp. 220–226,
J. Groth, A verifiable secret shuffle of homomorphic encryptions, in PKC. Lecture Notes in Computer Science, vol. 2567 (Springer, Berlin, 2003), pp. 145–160
J. Groth, Honest verifier zero-knowledge arguments applied. Dissertation Series DS-04-3, BRICS (2004). Ph.D. thesis, pp. xii+119
J. Groth, Cryptography in subgroups of \(\mathbb{Z}_{n}^{*}\), in TCC. Lecture Notes in Computer Science, vol. 3378 (Springer, Berlin, 2005), pp. 50–65
J. Groth, Non-interactive zero-knowledge arguments for voting, in ACNS. Lecture Notes in Computer Science, vol. 3531 (Springer, Berlin, 2005)
J. Groth, S. Lu, Verifiable shuffle of large size ciphertexts, in PKC. Lecture Notes in Computer Science, vol. 4450 (Springer, Berlin, 2007), pp. 377–392
M. Jakobsson, A practical mix, in EUROCRYPT. Lecture Notes in Computer Science, vol. 1403 (Springer, Berlin, 1998), pp. 448–461
M. Jakobsson, Flash mixing, in PODC (1999), pp. 83–89
M. Jakobsson, A. Juels, Millimix: Mixing in small batches (1999)
M. Jakobson, A. Juels, R.L. Rivest, Making mix nets robust for electronic voting by randomized partial checking, in USENIX Security (Springer, Berlin, 2002), pp. 339–353
A. Kiayias, M. Yung, The vector-ballot e-voting approach, in Financial Cryptography. Lecture Notes in Computer Science, vol. 3110 (Springer, Berlin, 2004), pp. 74–89
H.W. Lenstra, Factoring integers with elliptic curves. Ann. Math. 126, 649–673 (1987)
C.H. Lim, Efficient multi-exponentiation and application to batch verification of digital signatures. Manuscript (2000)
Y. Lindell, Parallel coin-tossing and constant-round secure two-party computation. J. Cryptol. 16(3), 143–184 (2003)
C.A. Neff, A verifiable secret shuffle and its application to e-voting, in ACM CCS (2001), pp. 116–125
C.A. Neff, Verifiable mixing (shuffling) of ElGamal pairs (2003)
C.A. Neff, Personal communication (2005)
L. Nguyen, R. Safavi-Naini, Breaking and mending resilient mix-nets, in PET. Lecture Notes in Computer Science, vol. 2760 (Springer, Berlin, 2003), pp. 66–80
L. Nguyen, R. Safavi-Naini, K. Kurosawa, Verifiable shuffles: a formal model and a Paillier-based three-round construction with provable security. Int. J. Inf. Secur. 5(4), 241–255 (2006)
J. Manuel González Nieto, C. Boyd, E. Dawson, A public key cryptosystem based on a subgroup membership problem. Des. Codes and Cryptogr. 36(3), 301–316 (2005)
M. Ohkubo, M. Abe, A length-invariant hybrid mix, in ASIACRYPT. Lecture Notes in Computer Science, vol. 1976 (Springer, Berlin, 2000), pp. 178–191
T. Okamoto, S. Uchiyama, A new public-key cryptosystem as secure as factoring, in EUROCRYPT. Lecture Notes in Computer Science, vol. 1403 (Springer, Berlin, 1998), pp. 308–318
T. Onodera, K. Tanaka, Shufle for Paillier’s encryption scheme. IEICE Trans. Fundam. Electron. Commun. Comput. Sci. E88-A(5), 1241–1248 (2005)
P. Paillier, Public-key cryptosystems based on composite residuosity classes, in EUROCRYPT. Lecture Notes in Computer Science, vol. 1592 (Springer, Berlin, 1999), pp. 223–239
C. Park, K. Itoh, K. Kurosawa, Efficient anonymous channel and all/nothing election scheme, in EUROCRYPT. Lecture Notes in Computer Science, vol. 765 (Springer, Berlin, 1993), pp. 248–259
T.P. Pedersen, Non-interactive and information-theoretic secure verifiable secret sharing, in CRYPTO. Lecture Notes in Computer Science, vol. 576 (Springer, Berlin, 1991), pp. 129–140
K. Peng, C. Boyd, E. Dawson, K. Viswanathan, A correct, private, and efficient mix network, in PKC. Lecture Notes in Computer Science, vol. 2947 (Springer, Berlin, 2004), pp. 439–454
B. Pfitzmann, A. Pfitzmann, How to break the direct RSA-implementation of mixes, in EUROCRYPT. Lecture Notes in Computer Science, vol. 434 (Springer, Berlin, 1989), pp. 373–381
K. Sako, J. Kilian, Receipt-free mix-type voting scheme—a practical solution to the implementation of a voting booth, in EUROCRYPT. Lecture Notes in Computer Science, vol. 921 (Springer, Berlin, 1995), pp. 393–403
H. Stamer, Efficient electronic gambling: an extended implementation of the toolbox for mental card games, in WEWoRC 2005, ed. by C. Wolf, S. Lucks, P.-W. Yau. Lecture Notes in Informatics, vol. P-74 (Gesellschaft für Informatik e.V., 2005), pp. 1–12
D. Wikström, The security of a mix-center based on a semantically secure cryptosystem, in INDOCRYPT. Lecture Notes in Computer Science, vol. 2551 (Springer, Berlin, 2002), pp. 368–381
D. Wikström, Five practical attacks for optimistic mixing for exit-polls, in SAC. Lecture Notes in Computer Science, vol. 3006 (Springer, Berlin, 2003), pp. 160–175
Author information
Authors and Affiliations
Corresponding author
Additional information
Communicated by Kazue Sako
Part of the work done while at University of Aarhus, Cryptomathic and UCLA.
Rights and permissions
About this article
Cite this article
Groth, J. A Verifiable Secret Shuffle of Homomorphic Encryptions. J Cryptol 23, 546–579 (2010). https://doi.org/10.1007/s00145-010-9067-9
Received:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s00145-010-9067-9