Abstract
We present new cryptographic protocols for multi-authority secret ballot elections that guarantee privacy, robustness, and univer- sal verifiability. Application of some novel techniques, in particular the construction of witness hiding/indistinguishable protocols from Cramer, Damgård and Schoenmakers, and the verifiable secret sharing scheme of Pedersen, reduce the work required by the voter or an authority to a linear number of cryptographic operations in the population size (com- pared to quadratic in previous schemes). Thus we get significantly closer to a practical election scheme.
Work done while at CWI.
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
J. Benaloh. Cryptographic capsules: A disjunctive primitive for interactive protocols. In Advances in Cryptology—CRYPTO’ 86, volume 263 of Lecture Notes in Computer Science, pages 213–222, Berlin, 1987. Springer-Verlag.
J. Benaloh. Verifiable Secret-Ballot Elections. PhD thesis, Yale University, Department of Computer Science Department, New Haven, CT, September 1987.
J. Benaloh and D. Tuinstra. Receipt-free secret-ballot elections. In Proc. 26th Symposium on Theory of Computing (STOC’ 94), pages 544–553, New York, 1994. A.C.M.
J. Benaloh and M. Yung. Distributing the power of a government to enhance the privacy of voters. In Proc. 5th ACM Symposium on Principles of Distributed Computing (PODC’ 86), pages 52–62, New York, 1986. A.C.M.
R. Cramer, I. Damgård, and B. Schoenmakers. Proofs of partial knowledge and simplified design of witness hiding protocols. In Advances in Cryptology—CRYPTO’ 94, volume 839 of Lecture Notes in Computer Science, pages 174–187, Berlin, 1994. Springer-Verlag.
J. Cohen and M. Fischer. A robust and verifiable cryptographically secure election scheme. In Proc. 26th IEEE Symposium on Foundations of Computer Science (FOCS’ 85), pages 372–382. IEEE Computer Society, 1985.
D. Chaum. Untraceable electronic mail, return addresses, and digital pseudonyms. Communications of the ACM, 24(2):84–88, 1981.
L. Chen. Witness Hiding Proofs and Applications. PhD thesis, Aarhus University, Computer Science Department, Aarhus, Denmark, August 1994.
L. Chen and T. P. Pedersen. New group signature schemes. In Advances in Cryptology—EUROCRYPT’ 94, volume 950 of Lecture Notes in Computer Science, pages 171–181, Berlin, 1995. Springer-Verlag.
A. Fiat and A. Shamir. How to prove yourself: Practical solutions to identification and signature problems. In Advances in Cryptology—CRYPTO’ 86, volume 263 of Lecture Notes in Computer Science, pages 186–194, New York, 1987. Springer-Verlag.
R. Gennaro. Achieving independence efficiently and securely. In Proc. 14th ACM Symposium on Principles of Distributed Computing (PODC’ 95), New York, 1995. A.C.M.
L. C. Guillou and J.-J. Quisquater. A practical zero-knowledge protocol fitted to security microprocessor minimizing both transmission and memory. In Advances in Cryptology—EUROCRYPT’ 88, volume 330 of Lecture Notes in Computer Science, pages 123–128, Berlin, 1988. Springer-Verlag.
T. Okamoto. Provably secure and practical identification schemes and corresponding signature schemes. In Advances in Cryptology—CRYPTO’ 92, volume 740 of Lecture Notes in Computer Science, pages 31–53, Berlin, 1993. Springer-Verlag.
T. P. Pedersen. Non-interactive and information-theoretic secure verifiable secret sharing. In Advances in Cryptology—CRYPTO’ 91, volume 576 of Lecture Notes in Computer Science, pages 129–140, Berlin, 1992. Springer-Verlag.
C. P. Schnorr. Efficient signature generation by smart cards. Journal of Cryptology, 4(3):161–174, 1991.
K. Sako and J. Kilian. Secure voting using partially compatible homomorphisms. In Advances in Cryptology—CRYPTO’ 94, volume 839 of Lecture Notes in Computer Science, pages 411–424, Berlin, 1994. Springer-Verlag.
K. Sako and J. Kilian. Receipt-free mix-type voting scheme—a practical solution to the implementation of a voting booth. In Advances in Cryptology—EUROCRYPT’ 95, volume 921 of Lecture Notes in Computer Science, pages 393–403, Berlin, 1995. Springer-Verlag.
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 1996 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Cramer, R., Franklin, M., Schoenmakers, B., Yung, M. (1996). Multi-Authority Secret-Ballot Elections with Linear Work. In: Maurer, U. (eds) Advances in Cryptology — EUROCRYPT ’96. EUROCRYPT 1996. Lecture Notes in Computer Science, vol 1070. Springer, Berlin, Heidelberg. https://doi.org/10.1007/3-540-68339-9_7
Download citation
DOI: https://doi.org/10.1007/3-540-68339-9_7
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-61186-8
Online ISBN: 978-3-540-68339-1
eBook Packages: Springer Book Archive