A verifiable secret shuffle and its application to e-voting

ABSTRACT

We present a mathematical construct which provides a cryptographic protocol to verifiably shuffle a sequence of k modular integers, and discuss its application to secure, universally verifiable, multi-authority election schemes. The output of the shuffle operation is another sequence of k modular integers, each of which is the same secret power of a corresponding input element, but the order of elements in the output is kept secret. Though it is a trivial matter for the "shuffler" (who chooses the permutation of the elements to be applied) to compute the output from the input, the construction is important because it provides a linear size proof of correctness for the output sequence (i.e. a proof that it is of the form claimed) that can be checked by an arbitrary verifiers. The complexity of the protocol improves on that of Furukawa-Sako[16] both measured by number of exponentiations and by overall size.The protocol is shown to be honest-verifier zeroknowledge in a special case, and is computational zeroknowledge in general. On the way to the final result, we also construct a generalization of the well known Chaum-Pedersen protocol for knowledge of discrete logarithm equality [10], [7]. In fact, the generalization specializes exactly to the Chaum-Pedersen protocol in the case k = 2. This result may be of interest on its own.An application to electronic voting is given that matches the features of the best current protocols with significant efficiency improvements. An alternative application to electronic voting is also given that introduces an entirely new paradigm for achieving Universally Verifiable elections.

REFERENCES

• 1: Masayuki Abe, Mix-Networks on Permutation Networks, Proceedings of the International Conference on the Theory and Applications of Cryptology and Information Security: Advances in Cryptology, p.258-273, November 14-18, 1999
• 2: Masayuki Abe , Fumitaka Hoshino, Remarks on Mix-Network Based on Permutation Networks, Proceedings of the 4th International Workshop on Practice and Theory in Public Key Cryptography: Public Key Cryptography, p.317-324, February 13-15, 2001
• 3: Josh Cohen Benaloh, Secret sharing homomorphisms: keeping shares of a secret secret, Proceedings on Advances in cryptology---CRYPTO '86, p.251-260, January 1987, Santa Barbara, California, United States
• 4: Josh C Benaloh , Moti Yung, Distributing the power of a government to enhance the privacy of voters, Proceedings of the fifth annual ACM symposium on Principles of distributed computing, p.52-62, August 11-13, 1986, Calgary, Alberta, Canada [doi>10.1145/10590.10595]
• 5: Ronald Cramer , Ivan Damgård , Berry Schoenmakers, Proofs of Partial Knowledge and Simplified Design of Witness Hiding Protocols, Proceedings of the 14th Annual International Cryptology Conference on Advances in Cryptology, p.174-187, August 21-25, 1994
• 6: R. Cramer, M. Franklin, B. Schoenmakers, M. Yung. Multi-authority secret-ballot elections with linear work. Advances in Cryptology - EUROCRYPT '96, Lecture Notes in Computer Science, Springer-Verlag, Berlin, 1996.
• 7: R. Cramer, R. Gennaro, B. Schoenmakers. A secure and optimally efficient multi-authority election scheme. Advances in Cryptology - EUROCRYPT '97, Lecture Notes in Computer Science, Springer-Verlag, 1997.
• 8: David L. Chaum, Untraceable electronic mail, return addresses, and digital pseudonyms, Communications of the ACM, v.24 n.2, p.84-90, Feb. 1981 [doi>10.1145/358549.358563]
• 9: David Chaum, Zero-knowledge undeniable signatures (extended abstract), Proceedings of the workshop on the theory and application of cryptographic techniques on Advances in cryptology, p.458-464, February 1991, Aarhus, Denmark
• 10: David Chaum , Torben P. Pedersen, Wallet Databases with Observers, Proceedings of the 12th Annual International Cryptology Conference on Advances in Cryptology, p.89-105, August 16-20, 1992
• 11: A. De Santis, G. Di Crescenzo, G. Persiano and M. Yung. On Monotone Formula Closure of SZK. FOCS 94, pp. 454-465.
• 12: W. Diffie, M. E. Hellman. New directions in cryptography. IEEE Transactions on Information Theory, 22(6):644-654, 1976.
• 13: T. ElGamal. A public-key cryptosystem and a signature scheme based on discrete logarithms. IEEE Transactions on Information Theory, IT-31(4):469-472, 1985.
• 14: Atsushi Fujioka , Tatsuaki Okamoto , Kazuo Ohta, A Practical Secret Voting Scheme for Large Scale Elections, Proceedings of the Workshop on the Theory and Application of Cryptographic Techniques: Advances in Cryptology, p.244-251, December 13-16, 1992
• 15: Amos Fiat , Adi Shamir, How to prove yourself: practical solutions to identification and signature problems, Proceedings on Advances in cryptology---CRYPTO '86, p.186-194, January 1987, Santa Barbara, California, United States
• 16: Jun Furukawa , Kazue Sako, An Efficient Scheme for Proving a Shuffle, Proceedings of the 21st Annual International Cryptology Conference on Advances in Cryptology, p.368-387, August 19-23, 2001
• 17: Rosario Gennaro, Achieving independence efficiently and securely, Proceedings of the fourteenth annual ACM symposium on Principles of distributed computing, p.130-136, August 20-23, 1995, Ottowa, Ontario, Canada [doi>10.1145/224964.224979]
• 18: Alfred J. Menezes , Scott A. Vanstone , Paul C. Van Oorschot, Handbook of Applied Cryptography, CRC Press, Inc., Boca Raton, FL, 1996
• 19: Neal Koblitz, A course in number theory and cryptography, Springer-Verlag New York, Inc., New York, NY, 1987
• 20: A M Odlyzko, Discrete logarithms in finite fields and their cryptographic significance, Proc. of the EUROCRYPT 84 workshop on Advances in cryptology: theory and application of cryptographic techniques, p.224-314, December 1985, Paris, France
• 21: T. Pedersen. A threshold cryptosystem without a trusted party, Advances in Cryptology - EUROCRYPT '91, Lecture Notes in Computer Science, pp. 522-526, Springer-Verlag, 1991.
• 22: Choonsik Park , Kazutomo Itoh , Kaoru Kurosawa, Efficient anonymous channel and all/nothing election scheme, Workshop on the theory and application of cryptographic techniques on Advances in cryptology, p.248-259, January 1994, Lofthus, Norway
• 23: C. P. Schnorr. Efficient signature generation by smart cards. Journal of Cryptology, 4(3):161-174, 1991.
• 24: Adi Shamir, How to share a secret, Communications of the ACM, v.22 n.11, p.612-613, Nov. 1979 [doi>10.1145/359168.359176]
• 25: Kazue Sako , Joe Kilian, Secure Voting Using Partially Compatible Homomorphisms, Proceedings of the 14th Annual International Cryptology Conference on Advances in Cryptology, p.411-424, August 21-25, 1994
• 26: K. Sako, J. Kilian. Receipt-free mix-type voting scheme - A practical solution to the implementation of a voting booth, Advances in Cryptology -EUROCRYPT '95, Lecture Notes in Computer Science, Springer-Verlag, 1995.
• 27: J. Kilian, K. Sako, Secure electronic voting using partially compatible homomorphisms, awarded 2/27/1996, filed 8/19/1994.
• 28: J. Kilian, K. Sako, Secure anonymous message transfer and voting scheme, awarded 10/28/1997, filed 1/23/1995.

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.1 Numerical Algorithms and Problems
          Subjects: Number-theoretic computations (e.g., factoring, primality testing)

Additional Classification:
  E. Data
  E.3 DATA ENCRYPTION
      Subjects: Public key cryptosystems

  K. Computing Milieux
  K.4 COMPUTERS AND SOCIETY
      K.4.4 Electronic Commerce
          Subjects: Electronic data interchange (EDI)

General Terms:
Algorithms, Performance, Security

Keywords:
anonymous credentials, electronic voting, honest-verifier, mix-net, permutation, universal verifiability, verifiable mix, verifiable shuffle, zeroknowledge