Paper 2023/933
More Efficient Post-Quantum Electronic Voting from NTRU
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)
- 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
-
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} }