Paper 2021/338

Lattice-Based Proof of Shuffle and Applications to Electronic Voting

Diego F. Aranha, Carsten Baum, Kristian Gjøsteen, Tjerand Silde, and Thor Tunge

Abstract

A verifiable shuffle of known values is a method for proving that a collection of commitments opens to a given collection of known messages, without revealing a correspondence between commitments and messages. We propose the first practical verifiable shuffle of known values for lattice-based commitments. Shuffles of known values have many applications in cryptography, and in particular in electronic voting. We use our verifiable shuffle of known values to build a practical lattice-based cryptographic voting system that supports complex ballots. Our scheme is also the first construction from candidate post-quantum secure assumptions to defend against compromise of the voter's computer using return codes. We implemented our protocol and present benchmarks of its computational runtime. The size of the verifiable shuffle is $22 \tau$ KB and takes time $33 \tau$ ms for $\tau$ voters. This is around $5$ times faster and $40$ % smaller per vote than the lattice-basedvoting scheme by del Pino et al. (ACM CCS 2017), which can only handle yes/no-elections.

Note: This is the full version of the paper being published at CT-RSA 2021.

Metadata
Available format(s)
PDF
Category
Cryptographic protocols
Publication info
Published elsewhere. Major revision. CT-RSA 2021
DOI
10.1007/978-3-030-75539-3_10
Keywords
Lattice-Based CryptographyProof of ShuffleVerifiable EncryptionReturn CodesElectronic VotingImplementation
Contact author(s)
tjerand silde @ ntnu no
History
2022-05-22: last of 2 revisions
2021-03-17: received
See all versions
Short URL
https://ia.cr/2021/338
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2021/338,
      author = {Diego F.  Aranha and Carsten Baum and Kristian Gjøsteen and Tjerand Silde and Thor Tunge},
      title = {Lattice-Based Proof of Shuffle and Applications to Electronic Voting},
      howpublished = {Cryptology ePrint Archive, Paper 2021/338},
      year = {2021},
      doi = {10.1007/978-3-030-75539-3_10},
      note = {\url{https://eprint.iacr.org/2021/338}},
      url = {https://eprint.iacr.org/2021/338}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.