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. 1.M. Abe. Mix-Networks on Permutation Networks - ASIACRYPT 99, Lecture Notes in Computer Science, pp. 258-273, Springer-Verlag, 1999.]]
2. 2.M. Abe and F. Hoshino. Remarks on Mix-Network Based on Permutation Networks. Proceedings 4th International Workshop on Practice and Theory in Public Key Cryptography PKC 2001, Lecture Notes in Computer Science, pages 317-324, Springer-Verlag, 2001.]]
3. 3.J. Benaloh. Secret Sharing Homomorphisms: Keeping Shares of a Secret Secret. Advances in Cryptology - CRYPTO '86, Lecture Notes in Computer Science, pp. 251-260, Springer-Verlag, Berlin, 1987.]]
4. 4.J. Benaloh, M. Yung. Distributing the power of a government to enhance the privacy of voters. ACM Symposium on Principles of Distributed Computing, pp. 52-62, 1986.]]
5. 5.R. Cramer, I. Damgrd, B. Schoenmakers. Proofs of partial knowledge and simplified design of witness hiding protocols. Advances in Cryptology - CRYPTO '94, Lecture Notes in Computer Science, pp. 174-187, Springer-Verlag, Berlin, 1994.]]
6. 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. 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. 8.D. Chaum. Untraceable electronic mail, return addresses, and digital pseudonyms. Communications of the ACM, 24(2):84-88, 1981.]]
9. 9.D. Chaum. Zero-knowledge undeniable signatures. Advances in Cryptology - EUROCRYPT '90, Lecture Notes in Computer Science, volume 473, pages 458-464, Springer-Verlag, 1991.]]
10. 10.D. Chaum and T.P. Pedersen. Wallet databases with observers. Advances in Cryptology - CRYPTO '92, volume 740 of Lecture Notes in Compute Science, pages 89-105, Berlin, 1993. Springer-Verlag.]]
11. 11.A. De Santis, G. Di Crescenzo, G. Persiano and M. Yung. On Monotone Formula Closure of SZK. FOCS 94, pp. 454-465.]]
12. 12.W. Diffie, M. E. Hellman. New directions in cryptography. IEEE Transactions on Information Theory, 22(6):644-654, 1976.]]
13. 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. 14.A. Fujioka, T. Okamoto, K. Ohta. A practical secret voting scheme for large scale elections. Advances in Cryptology - AUSCRYPT '92, Lecture Notes in Computer Science, pp. 244-251, Springer-Verlag, 1992.]]
15. 15.A. Fiat, A. Shamir. How to prove yourself: Practical solutions to identification and signature problems. Advances in Cryptology - CRYPTO '86, Lecture Notes in Computer Science, pp. 186-194, Springer-Verlag, New York, 1987.]]
16. 16.J. Furukawa and K. Sako. An Efficient Scheme for Proving a Shuffle. To appear in CRYPTO 2001.]]
17. 17.R. Gennaro. Achieving independence efficiently and securely. Proceedings 14th ACM Symposium on Principles of Distributed Computing (PODC '95), New York, 1995.]]
18. 18.A.J. Menezes, P.C. van Oorschot, and S.A. Vanstone. Handbook of Applied Cryptography, CRC Press, 1997.]]
19. 19.N. Koblitz, A Course in Number Theory and Cryptography, 2nd edition, Springer, 1994.]]
20. 20.A. M. Odlyzko, Discrete logarithms in finite fields and their cryptographic significance, Advances in Cryptology - EUROCRYPT '84, Lecture Notes in Computer Science, Springer-Verlag, 1984.]]
21. 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. 22.C. Park, K. Itoh, K. Kurosawa. Efficient anonymous channel and all/nothing election scheme. Advances in Cryptology - EUROCRYPT '93, Lecture Notes in Computer Science, pp. 248-259, Springer-Verlag, 1993.]]
23. 23.C. P. Schnorr. Efficient signature generation by smart cards. Journal of Cryptology, 4(3):161-174, 1991.]]
24. 24.A. Shamir. How to share a secret. Communications of the ACM, 22(11):612-613, 1979.]]
25. 25.K. Sako, J. Kilian. Secure voting using partially compatible homomorphisms, Advances in Cryptology -CRYPTO '94, Lecture Notes in Computer Science, Springer-Verlag, 1994.]]
26. 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. 27.J. Kilian, K. Sako, Secure electronic voting using partially compatible homomorphisms, awarded 2/27/1996, filed 8/19/1994.]]
28. 28.J. Kilian, K. Sako, Secure anonymous message transfer and voting scheme, awarded 10/28/1997, filed 1/23/1995.]]

Index Terms

• Applied computing

  • Electronic commerce

    • Electronic data interchange

• Mathematics of computing

  • Mathematical analysis

    • Numerical analysis

      • Number-theoretic computations

• Security and privacy

  • Cryptography

    • Public key (asymmetric) techniques

      • Public key encryption