Paper 2023/933

More Efficient Post-Quantum Electronic Voting from NTRU

Patrick Hough, Oxford University
Caroline Sandsbråten, Norwegian University of Science and Technology
Tjerand Silde, Norwegian University of Science and Technology
Abstract

In recent years, there has been much focus on developing core cryptographic primitives based on lattice assumptions, driven by the NIST cal for post-quantum key encapsulation and digital signature algorithms. However, more work must be conducted on efficient privacy-preserving protocols with post-quantum security. Electronic voting is one such privacy-preserving protocol whose adoption is increasing across the democratic world. E-voting offers both a fast and convenient alternative to postal voting whilst further ensuring cryptographic privacy of votes and offering full verifiability of the process. Owing to the sensitivity of voting and the infrastructure challenges it poses, it is important that post-quantum security be baked into e-voting solutions early. We present a post-quantum e-voting scheme based on the hardness of the RLWE and NTRU lattice problems, providing concrete parameters and an efficient implementation. Our design achieves a factor $\times 5.3$ reduction in ciphertext size, $\times 2.5$ reduction in total communication cost, and $\times 2$ reduction in total computation time compared to the state-of-the-art lattice-based voting scheme by Aranha et al. (ACM CCS 2023). We argue that the efficiency of this scheme makes it suitable for real-world elections. Our scheme makes use of non-ternary NTRU secrets to achieve optimal parameters. In order to compute the security of our design, we extend the ternary-NTRU work of Ducas and van Woerden (ASIACRYPT 2021) by determining the concrete fatigue point (for general secrets) of NTRU to be $q=0.0058\cdot \sigma^2 \cdot d^{\:2.484}$ (above which parameters become overstretched) for modulus $q$, ring dimension $d$ and secrets drawn from a Gaussian of parameter $\sigma$. We consider this relation to be of independent interest and demonstrate its significance by improving the efficiency of the (partially) blind signature scheme by del Pino and Katsumata (CRYPTO 2022).

Metadata
Available format(s)
PDF
Category
Cryptographic protocols
Publication info
Preprint.
Keywords
NTRU SecurityLattice CryptographyElectronic Voting
Contact author(s)
patrick hough @ maths ox ac uk
caroline sandsbraten @ ntnu no
tjerand silde @ ntnu no
History
2024-03-13: revised
2023-06-14: received
See all versions
Short URL
https://ia.cr/2023/933
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2023/933,
      author = {Patrick Hough and Caroline Sandsbråten and Tjerand Silde},
      title = {More Efficient Post-Quantum Electronic Voting from {NTRU}},
      howpublished = {Cryptology {ePrint} Archive, Paper 2023/933},
      year = {2023},
      url = {https://eprint.iacr.org/2023/933}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.