Abstract
We formalize the notion of a cryptographic counter, which allows a group of participants to increment and decrement a cryptographic representation of a (hidden) numerical value privately and robustly. The value of the counter can only be determined by a trusted authority (or group of authorities, which may include participants themselves), and participants cannot determine any information about the increment/decrement operations performed by other parties.
Previous efficient implementations of such counters have relied on fully-homomorphic encryption schemes; this is a relatively strong requirement which not all encryption schemes satisfy. We provide an alternate approach, starting with any encryption scheme homomorphic over the additive group ℤ2 (i.e., 1-bit XOR). As our main result, we show a general and efficient reduction from any such encryption scheme to a general cryptographic counter. Our main reduction does not use additional assumptions, is efficient, and gives a novel implementation of a general counter. The result can also be viewed as an efficient construction of a general n-bit cryptographic counter from any 1-bit counter which has the additional property that counters can be added securely.
As an example of the applicability of our construction, we present a cryptographic counter based on the quadratic residuosity assumption and use it to construct an efficient voting scheme which satisfies universal verifiability, privacy, and robustness.
Work done while the author was at Telcordia Technologies.
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
M. Bellare and P. Rogaway. Random Oracles are Practical: A Paradigm for Designing Efficient Protocols. ACM CCCS 1993.
J. Benaloh and D. Tuinstra. Receipt-Free Secret-Ballot Elections. STOC 1994.
J. Benaloh and M. Yung. Distributing the Power of a Government to Enhance the Privacy of Voters. PODC 1986.
J. Benaloh. Verifiable Secret-Ballot Elections. PhD thesis, Yale University, Department of Computer Science, New Haven, CT, 1987.
M. Blum, P. Feldman, and S. Micali. Non-Interactive Zero-Knowledge and its Applications. STOC 1988.
J. Cohen and M. Fischer. A Robust and Verifiable Cryptographically Secure Election Scheme. FOCS 1985.
D. Coppersmith. Fast Evaluation of Logarithms in Fields of Characteristic Two. IEEE Transactions on Information Theory, Vol. 30, pp. 587–594, 1984
R. Cramer, M. Franklin, B. Schoenmakers, and M. Yung. Multi-Authority Secret-Ballot Elections with Linear Work. Eurocrypt 1996.
R. Cramer, R. Gennaro, and B. Schoenmakers. A Secure and Optimally Efficient Multi-Authority Election Scheme. Eurocrypt 1997.
I. Damgård and M. Jurik. Efficient Protocols Based on Probabilistic Encryption Using Composite Degree Residue Classes. Manuscript, May 2000.
A. De Santis, G. Di Crescenzo, G. Persiano, and M. Yung. On Monotone Formula Closure of SZK. FOCS 1994.
T. ElGamal. A Public-Key Cryptosystem and a Signature Scheme Based on Discrete Logarithms. IEEE Trans. Info. Theory, 31(4): 469–472, 1985.
A. Fiat and A. Shamir. How to Prove Yourself: Practical Solution to Identification and Signature Problems. CRYPTO 1986.
O. Goldreich. Secure Multi-Party Computation (Working Draft, Version 1.1). Manuscript, 1998.
O. Goldreich, S. Micali, and A. Wigderson. How to Play Any Mental Game, or a Completeness Theorem for Protocols with an Honest Majority. STOC '87.
S. Goldwasser and S. Micali. Probabilistic Encryption. JCSS 28(2): 270–299, 1984.
M. Hirt and K. Sako. Efficient Receipt-Free Voting Based on Homomorphic Encryption. Eurocrypt 2000.
J. Katz and M. Yung. Threshold Cryptosystems with Distributed Prime Factors. Manuscript.
R. Lidl and H. Niederreiter. Introduction to Finite Fields and their Applications (Revised Edition), Cambridge University Press, 1994.
R. Lidl and G. Pilz. Applied Abstract Algebra (Second Edition), Springer, 1997.
P. Pallier. Public-Key Cryptosystems Based on Composite Degree Residue Classes. Eurocrypt 1999.
J. Rifa and J. Borrell. Improving the Time Complexity of the Computation of Irreducible and Primitive Polynomials in Finite Fields. Applied Algebra, Algebraic Algorithms, and Error-Correcting Codes, 1991.
B. Schoenmakers. A Simple Publicly Verifiable Secret Sharing Scheme and its Application to Electronic Voting. CRYPTO 1999.
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2001 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Katz, J., Myers, S., Ostrovsky, R. (2001). Cryptographic Counters and Applications to Electronic Voting. In: Pfitzmann, B. (eds) Advances in Cryptology — EUROCRYPT 2001. EUROCRYPT 2001. Lecture Notes in Computer Science, vol 2045. Springer, Berlin, Heidelberg. https://doi.org/10.1007/3-540-44987-6_6
Download citation
DOI: https://doi.org/10.1007/3-540-44987-6_6
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-42070-5
Online ISBN: 978-3-540-44987-4
eBook Packages: Springer Book Archive