Cryptographic Counters and Applications to Electronic Voting

  • Jonathan Katz
  • Steven Myers
  • Rafail Ostrovsky
Conference paper
Part of the Lecture Notes in Computer Science book series (LNCS, volume 2045)


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.


Encryption Scheme Random Oracle Vote Scheme Quadratic Residue Linear Feedback Shift Register 
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.


  1. 1.
    M. Bellare and P. Rogaway. Random Oracles are Practical: A Paradigm for Designing Efficient Protocols. ACM CCCS 1993.Google Scholar
  2. 2.
    J. Benaloh and D. Tuinstra. Receipt-Free Secret-Ballot Elections. STOC 1994.Google Scholar
  3. 3.
    J. Benaloh and M. Yung. Distributing the Power of a Government to Enhance the Privacy of Voters. PODC 1986.Google Scholar
  4. 4.
    J. Benaloh. Verifiable Secret-Ballot Elections. PhD thesis, Yale University, Department of Computer Science, New Haven, CT, 1987.Google Scholar
  5. 5.
    M. Blum, P. Feldman, and S. Micali. Non-Interactive Zero-Knowledge and its Applications. STOC 1988.Google Scholar
  6. 6.
    J. Cohen and M. Fischer. A Robust and Verifiable Cryptographically Secure Election Scheme. FOCS 1985.Google Scholar
  7. 7.
    D. Coppersmith. Fast Evaluation of Logarithms in Fields of Characteristic Two. IEEE Transactions on Information Theory, Vol. 30, pp. 587–594, 1984zbMATHCrossRefMathSciNetGoogle Scholar
  8. 8.
    R. Cramer, M. Franklin, B. Schoenmakers, and M. Yung. Multi-Authority Secret-Ballot Elections with Linear Work. Eurocrypt 1996.Google Scholar
  9. 9.
    R. Cramer, R. Gennaro, and B. Schoenmakers. A Secure and Optimally Efficient Multi-Authority Election Scheme. Eurocrypt 1997.Google Scholar
  10. 10.
    I. Damgård and M. Jurik. Efficient Protocols Based on Probabilistic Encryption Using Composite Degree Residue Classes. Manuscript, May 2000.Google Scholar
  11. 11.
    A. De Santis, G. Di Crescenzo, G. Persiano, and M. Yung. On Monotone Formula Closure of SZK. FOCS 1994.Google Scholar
  12. 12.
    T. ElGamal. A Public-Key Cryptosystem and a Signature Scheme Based on Discrete Logarithms. IEEE Trans. Info. Theory, 31(4): 469–472, 1985.zbMATHCrossRefMathSciNetGoogle Scholar
  13. 13.
    A. Fiat and A. Shamir. How to Prove Yourself: Practical Solution to Identification and Signature Problems. CRYPTO 1986.Google Scholar
  14. 14.
    O. Goldreich. Secure Multi-Party Computation (Working Draft, Version 1.1). Manuscript, 1998.Google Scholar
  15. 15.
    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.Google Scholar
  16. 16.
    S. Goldwasser and S. Micali. Probabilistic Encryption. JCSS 28(2): 270–299, 1984.zbMATHMathSciNetGoogle Scholar
  17. 17.
    M. Hirt and K. Sako. Efficient Receipt-Free Voting Based on Homomorphic Encryption. Eurocrypt 2000.Google Scholar
  18. 18.
    J. Katz and M. Yung. Threshold Cryptosystems with Distributed Prime Factors. Manuscript.Google Scholar
  19. 19.
    R. Lidl and H. Niederreiter. Introduction to Finite Fields and their Applications (Revised Edition), Cambridge University Press, 1994.Google Scholar
  20. 20.
    R. Lidl and G. Pilz. Applied Abstract Algebra (Second Edition), Springer, 1997.Google Scholar
  21. 21.
    P. Pallier. Public-Key Cryptosystems Based on Composite Degree Residue Classes. Eurocrypt 1999.Google Scholar
  22. 22.
    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.Google Scholar
  23. 23.
    B. Schoenmakers. A Simple Publicly Verifiable Secret Sharing Scheme and its Application to Electronic Voting. CRYPTO 1999.Google Scholar

Copyright information

© Springer-Verlag Berlin Heidelberg 2001

Authors and Affiliations

  • Jonathan Katz
    • 1
  • Steven Myers
    • 2
  • Rafail Ostrovsky
    • 3
  1. 1.Telcordia Technologies and Department of Computer ScienceColumbia UniversityColumbia
  2. 2.Department of Computer ScienceUniversity of TorontoToronto
  3. 3.Telcordia Technologies, Inc.Morristown

Personalised recommendations