Paper 2016/975

(Universal) Unconditional Verifiability in E-Voting without Trusted Parties

Gina Gallegos-Garcia, Vincenzo Iovino, Alfredo Rial, Peter B. Roenne, and Peter Y. A. Ryan


In e-voting protocol design, cryptographers must balance usability and strong security guarantees, such as privacy and verifiability. In traditional e-voting protocols, privacy is often provided by a trusted authority that learns the votes and computes the tally. Some protocols replace the trusted authority by a set of authorities, and privacy is guaranteed if less than a threshold number of authorities are corrupt. For verifiability, stronger security guarantees are demanded. Typically, corrupt authorities that try to fake the result of the tally must always be detected. To provide verifiability, many e-voting protocols use Non-Interactive Zero-Knowledge proofs (NIZKs). Thanks to their non-interactive nature, NIZKs allow anybody, including third parties that do not participate in the protocol, to verify the correctness of the tally. Therefore, NIZKs can be used to obtain universal verifiability. Additionally, NIZKs also improve usability because they allow voters to cast a vote non-interactively. The disadvantage of NIZKs is that their security is based on setup assumptions such as the common reference string (CRS) or the random oracle model. The former requires a trusted party for the generation of a CRS. The latter, though a popular methodology for designing secure protocols, has been shown to be unsound. In this paper, we address the design of e-voting protocols that provide verifiability without any trust assumptions, where verifiability here is meant without eligibility verification. We show that Non-Interactive Witness-Indistinguishable proofs can be used for this purpose. All our e-voting schemes are private under the Decision Linear assumption, while the verifiability holds unconditionally. We first present a general construction that supports any tally function but with the drawback of representing the computation as a circuit. Then, we show how to efficiently instantiate it for specific types of elections through Groth-Sahai proofs. To our knowledge, this is the first private e-voting scheme with perfect universal verifiability, i.e. one in which the probability of a fake tally not being detected is 0, and with non-interactive protocols that does not rely on trust assumptions.

Note: This version consists of a major revision of the previous one. The main scheme for general tally functions is untouched but we now added a more efficient instantiation for specific tally functions from Groth-Sahai proofs.

Available format(s)
Publication info
Preprint. MINOR revision.
e-votingverifiabilitywitness indistinguishabilitybilinear maps
Contact author(s)
vinciovino @ gmail com
2017-02-24: last of 4 revisions
2016-10-12: received
See all versions
Short URL
Creative Commons Attribution


      author = {Gina Gallegos-Garcia and Vincenzo Iovino and Alfredo Rial and Peter B.  Roenne and Peter Y.  A.  Ryan},
      title = {(Universal) Unconditional Verifiability in E-Voting without Trusted Parties},
      howpublished = {Cryptology ePrint Archive, Paper 2016/975},
      year = {2016},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.