Cryptographic Counters and Applications to Electronic Voting.
Jonathan Katz, Steven Myers, Rafail Ostrovsky
Abstract:
We formalize the notion of a \emph{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 b y 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 \emph{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 $\integers{2}$ (i.e., 1-bit {\sc 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.
comment: Appeared in Proceedings of Advances in Cryptology, (EUROCRYPT-2001) Springer-Verlag/IACR Lecture Notes in Computer Science.
Fetch PostScript file of the paper Fetch PDF file of the paper