Movatterモバイル変換

[0]ホーム
URL:

Skip to main content

Advertisement

Springer Nature Link
Log in

Non-interactive Zero-Knowledge Arguments for Voting

  • Conference paper

Part of the book series:Lecture Notes in Computer Science ((LNSC,volume 3531))

  • 3868Accesses

Abstract

In voting based on homomorphic threshold encryption, the voter encrypts his vote and sends it in to the authorities that tally the votes. If voters can send in arbitrary plaintexts then they can cheat. It is therefore important that they attach an argument of knowledge of the plaintext being a correctly formed vote. Typically, these arguments are honest verifier zero-knowledge arguments that are made non-interactive using the Fiat-Shamir heuristic. Security is argued in the random oracle model.

The simplest case is where each voter has a single vote to cast. Practical solutions have already been suggested for the single vote case. However, as we shall see homomorphic threshold encryption can be used for a variety of elections, in particular there are many cases where voters can cast multiple votes at once. In these cases, it remains important to bring down the cost of the NIZK argument.

We improve on state of the art in the case of limited votes, where each voter can vote a small number of times. We also improve on the state of the art in shareholder elections, where each voter may have a large number of votes to spend. Moreover, we improve on the state of the art in Borda voting. Finally, we suggest a NIZK argument for correctness of an approval vote. To the best of our knowledge, approval voting has not been considered before in the cryptographic literature.

Similar content being viewed by others

References

  1. Benaloh, J.C.: Verifiable secret ballot elections. Technical Report 561, Yale University, PhD thesis. x+123 pp. (1987)

    Google Scholar 

  2. Baudron, O., Fouque, P.-A., Pointcheval, D., Poupard, G.: a. Stern. Practical multi-candidate election scheme. In: Proceedings of PODC 2001, pp. 274–283 (2001)

    Google Scholar 

  3. Boudot, F.: Efficient proofs that a committed number lies in an interval. In: Preneel, B. (ed.) EUROCRYPT 2000. LNCS, vol. 1807, p. 431. Springer, Heidelberg (2000)

    Chapter  Google Scholar 

  4. Bellare, M., Rogaway, P.: Random oracles are practical: A paradigm for designing efficient protocols. In: ACM CCS 1993, pp. 62–73 (1993)

    Google Scholar 

  5. Benaloh, J.C., Yung, M.: Distributing the power of a government to enhance the privacy of voters. In: proceedings of PODC 1986, pp. 52–62 (1986)

    Google Scholar 

  6. Cohen, J.D., Fischer, M.J.: A robust and verifiable cryptographically secure election scheme. In: proceedings of FOCS 1985, pp. 372–382 (1985)

    Google Scholar 

  7. Cramer, R., Gennaro, R., Schoenmakers, B.: A secure and optimally efficient multi-authority election scheme. In: Fumy, W. (ed.) EUROCRYPT 1997. LNCS, vol. 1233, pp. 103–118. Springer, Heidelberg (1997)

    Google Scholar 

  8. Camenisch, J., Stadler, M.: Efficient group signature schemes for large groups. In: Kaliski Jr., B.S. (ed.) CRYPTO 1997. LNCS, vol. 1294, pp. 410–424. Springer, Heidelberg (1997)

    Google Scholar 

  9. Damgård, I.B., Fujisaki, E.: A statistically-hiding integer commitment scheme based on groups with hidden order. In: Zheng, Y. (ed.) ASIACRYPT 2002. LNCS, vol. 2501, pp. 125–142. Springer, Heidelberg (2002)

    Chapter  Google Scholar 

  10. Damgård, I., Groth, J., Salomonsen, G.: The theory and implementation of an electronic voting system. In: Gritzalis, D. (ed.) Secure Electronic Voting, pp. 77–100. Kluwer Academic Publishers, Dordrecht (2003)

    Google Scholar 

  11. Damgård, I., Jurik, M.J.: A generalisation, a simplification and some applications of paillier’s probabilistic public-key system. In: Kim, K.-c. (ed.) PKC 2001. LNCS, vol. 1992. Springer, Heidelberg (2001)

    Chapter  Google Scholar 

  12. Damgård, I., Jurik, M.J., Nielsen, J.B.: A generalization of paillier’s public-key system with applications to electronic voting (2003) (manuscript),http://www.brics.dk/~ivan/GenPaillierfinaljour.ps

  13. El Gamal, T.: A public key cryptosystem and a signature scheme based on discrete logarithms. In: Blakely, G.R., Chaum, D. (eds.) CRYPTO 1984. LNCS, vol. 196, pp. 10–18. Springer, Heidelberg (1985)

    Chapter  Google Scholar 

  14. Fujisaki, E., Okamoto, T.: Statistical zero knowledge protocols to prove modular polynomial relations. In: Kaliski Jr., B.S. (ed.) CRYPTO 1997. LNCS, vol. 1294, pp. 16–30. Springer, Heidelberg (1997)

    Google Scholar 

  15. Furukawa, J.: Efficient, verifiable shuffle decryption and its requirement of unlinkability. Manuscript, Full version of [Fur04b] (2004)

    Google Scholar 

  16. Furukawa, J.: Efficient, verifiable shuffle decryption and its requirement of unlinkability. In: Bao, F., Deng, R., Zhou, J. (eds.) PKC 2004. LNCS, vol. 2947, pp. 319–332. Springer, Heidelberg (2004)

    Chapter  Google Scholar 

  17. Groth, J.: A verifiable secret shuffle of homomorphic encryptions. In: Desmedt, Y.G. (ed.) PKC 2003. LNCS, vol. 2567, pp. 145–160. Springer, Heidelberg (2002)

    Chapter  Google Scholar 

  18. Groth, J.: Cryptography in subgroups of formula_image. In: Kilian, J. (ed.) TCC 2005. LNCS, vol. 3378, pp. 50–65. Springer, Heidelberg (2005)

    Chapter  Google Scholar 

  19. Ishida, N., Matsuo, S., Ogata, W.: Divisible voting scheme. In: Boyd, C., Mao, W. (eds.) ISC 2003. LNCS, vol. 2851, pp. 137–150. Springer, Heidelberg (2003)

    Chapter  Google Scholar 

  20. Lipmaa, H., Asokan, N., Niemi, V.: Secure vickrey auctions without threshold trust. In: Blaze, M. (ed.) FC 2002. LNCS, vol. 2357, pp. 87–101. Springer, Heidelberg (2003)

    Chapter  Google Scholar 

  21. Lipmaa, H.: On diophantine complexity and statistical zero-knowledge arguments. In: Laih, C.-S. (ed.) ASIACRYPT 2003. LNCS, vol. 2894, pp. 398–415. Springer, Heidelberg (2003)

    Chapter  Google Scholar 

  22. Paillier, P.: Public-key cryptosystems based on composite degree residuosity classes. In: Stern, J. (ed.) EUROCRYPT 1999. LNCS, vol. 1592, pp. 223–239. Springer, Heidelberg (1999)

    Google Scholar 

  23. Rabin, M., Shallit, J.: Randomized algorithms in number theory. Commun. Pure and Appl. Math. 39(suppl.), S240–S256 (1986)

    Google Scholar 

  24. Wang, C.: Personal communication (2005)

    Google Scholar 

  25. Wang, C., Leung, H.F.: A secure and fully private borda voting protocol with universal verifiability. In: Proceedings of COMPSAC 2004, pp. 224–229 (2004)

    Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Dept. of Computer Science, UCLA, USA

    Jens Groth

Authors
  1. Jens Groth

    You can also search for this author inPubMed Google Scholar

Editor information

Editors and Affiliations

  1. AT&T Labs – Research,  

    John Ioannidis

  2. Computer Science Department, Columbia University,  

    Angelos Keromytis

  3. Computer Science Department, Google Inc. and Columbia University, 1214 Amsterdam Avenue, 10027, New York, NY, USA

    Moti Yung

Rights and permissions

Copyright information

© 2005 Springer-Verlag Berlin Heidelberg

About this paper

Cite this paper

Groth, J. (2005). Non-interactive Zero-Knowledge Arguments for Voting. In: Ioannidis, J., Keromytis, A., Yung, M. (eds) Applied Cryptography and Network Security. ACNS 2005. Lecture Notes in Computer Science, vol 3531. Springer, Berlin, Heidelberg. https://doi.org/10.1007/11496137_32

Download citation

Publish with us

[8]ページ先頭
©2009-2025 Movatter.jp