1997 | Ronald Cramer, Rosario Gennaro, Berry Schoenmakers
This paper presents a new multi-authority secret-ballot election scheme that ensures privacy, universal verifiability, and robustness. The scheme is optimal in terms of time and communication complexity, with the voter's effort being independent of the number of authorities. The voter simply posts a single encrypted message along with a compact proof that it contains a valid vote. The scheme is complementary to previous work, where the voter's effort was linear in the number of authorities, but this scheme provides computational privacy without requiring information-theoretic privacy. The majority of existing voting schemes provide only computational privacy, and this scheme is superior in that aspect.
The scheme is based on the ElGamal cryptosystem and uses a robust threshold decryption technique to ensure that individual votes remain private. The scheme also allows for homomorphic encryption, enabling the final tally to be verified without decrypting individual votes. The scheme is applicable to both large-scale and small-scale elections, and can be extended using proactive threshold cryptosystems to ensure long-term security.
The scheme is secure under the Diffie-Hellman assumption and provides universal verifiability, computational privacy, robustness, and prevents vote duplication. It also extends to multi-way elections by using multiple generators and accumulating votes for each option. The scheme is also applicable to alternative number-theoretic assumptions, such as the q-th residuosity assumption, and provides similar security guarantees.
The paper discusses the importance of information-theoretic privacy and the challenges of achieving it in election schemes. It also addresses the issue of incoercible protocols, where voters can be forced to reveal their votes, and proposes a deniable encryption scheme that allows for such protection. The scheme is also discussed in terms of proactive security, where the public key can be kept secure for long periods of time by periodically refreshing the private key shares. The paper concludes that the proposed scheme is efficient, secure, and suitable for a wide range of election scenarios.This paper presents a new multi-authority secret-ballot election scheme that ensures privacy, universal verifiability, and robustness. The scheme is optimal in terms of time and communication complexity, with the voter's effort being independent of the number of authorities. The voter simply posts a single encrypted message along with a compact proof that it contains a valid vote. The scheme is complementary to previous work, where the voter's effort was linear in the number of authorities, but this scheme provides computational privacy without requiring information-theoretic privacy. The majority of existing voting schemes provide only computational privacy, and this scheme is superior in that aspect.
The scheme is based on the ElGamal cryptosystem and uses a robust threshold decryption technique to ensure that individual votes remain private. The scheme also allows for homomorphic encryption, enabling the final tally to be verified without decrypting individual votes. The scheme is applicable to both large-scale and small-scale elections, and can be extended using proactive threshold cryptosystems to ensure long-term security.
The scheme is secure under the Diffie-Hellman assumption and provides universal verifiability, computational privacy, robustness, and prevents vote duplication. It also extends to multi-way elections by using multiple generators and accumulating votes for each option. The scheme is also applicable to alternative number-theoretic assumptions, such as the q-th residuosity assumption, and provides similar security guarantees.
The paper discusses the importance of information-theoretic privacy and the challenges of achieving it in election schemes. It also addresses the issue of incoercible protocols, where voters can be forced to reveal their votes, and proposes a deniable encryption scheme that allows for such protection. The scheme is also discussed in terms of proactive security, where the public key can be kept secure for long periods of time by periodically refreshing the private key shares. The paper concludes that the proposed scheme is efficient, secure, and suitable for a wide range of election scenarios.