Secure voting using partially compatible homomorphisms

Kazue Sako, Joe Kilian

Research output: Chapter in Book/Report/Conference proceedingConference contribution

94 Citations (Scopus)


We introduce a new number-theoretic based protocol for secure electronic voting. Our scheme is much more communication efficient than previous schemes of its type, and has a much lower round complexity than is currently possible using the anonymous-channel/mixer techniques. Preprocessing allows for nearly all of the communication and computation to be performed before any voting takes place. Unlike the mixer-based protocols, anyone can verify that everyone’s vote has been properly counted. Also, our techniques allow for a wide variety of different schemes. Our protocols are based on families of homomorphic encryptions which have a partial compatibility property, generalizing a method of Benaloh and Yung [2]. We use these functions to generate very simple interactive proofs on encrypted shares. We also develop amortization techniques yielding dramatic efficiency improvements over our simple protocols. Our protocols can be realized by current-generation PC’s with access to an electronic bulletin board.

Original languageEnglish
Title of host publicationAdvances in Cryptology — CRYPTO 1994 - 14th Annual International Cryptology Conference, Proceedings
EditorsYvo G. Desmedt
PublisherSpringer Verlag
Number of pages14
ISBN (Print)9783540583332
Publication statusPublished - 1994
Externally publishedYes
Event14th Annual International Cryptology Conference, CRYPTO 1994 - Santa Barbara , United States
Duration: 1994 Aug 211994 Aug 25

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume839 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349


Conference14th Annual International Cryptology Conference, CRYPTO 1994
Country/TerritoryUnited States
CitySanta Barbara

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Computer Science(all)


Dive into the research topics of 'Secure voting using partially compatible homomorphisms'. Together they form a unique fingerprint.

Cite this