Paper 2023/933

Concrete NTRU Security and Advances in Practical Lattice-Based Electronic Voting

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

In recent years there has been much focus on the development of core cryptographic primitives based on lattice assumptions. This has been driven by the NIST call for post-quantum key encapsulation and digital signature specifications. However, there has been much less work on efficient privacy-preserving protocols with post-quantum security. In this work we present an efficient electronic voting scheme from lattice assumptions, ensuring the long-term security of encrypted ballots and voters' privacy. The scheme relies on the NTRU and RLWE assumptions. We begin by conducting an extensive analysis of the concrete hardness of the NTRU problem. Extending the ternary-NTRU analysis of Ducas and van Woerden (ASIACRYPT 2021), we determine the concrete fatigue point 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$. Moreover, we demonstrate that the nature of this relation enables a more fine-grained choice of secret key sizes, leading to more efficient parameters in practice. Using the above analysis, our second and main contribution is to significantly improve the efficiency of the state-of-the-art lattice-based voting scheme by Aranha et al. (ACM CCS 2023). Replacing the BGV encryption scheme with NTRU we obtain a factor $\times 5.3$ reduction in ciphertext size and $\times 2.6$ more efficient system overall, making the scheme suitable for use in real-world elections. As an additional contribution, we analyse the (partially) blind signature scheme by del Pino and Katsumata (CRYPTO 2022). We note that the NTRU security is much lower than claimed and propose new parameters. This results in only a minor efficiency loss, enabled by our NTRU analysis where previous parameter selection techniques would have been much more detrimental.

Available format(s)
Cryptographic protocols
Publication info
NTRU SecurityLattice CryptographyElectronic Voting
Contact author(s)
patrick hough @ maths ox ac uk
caroline sandsbraten @ ntnu no
tjerand silde @ ntnu no
2023-06-15: approved
2023-06-14: received
See all versions
Short URL
Creative Commons Attribution


      author = {Patrick Hough and Caroline Sandsbråten and Tjerand Silde},
      title = {Concrete NTRU Security and Advances in Practical Lattice-Based Electronic Voting},
      howpublished = {Cryptology ePrint Archive, Paper 2023/933},
      year = {2023},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.