Welcome to the resource topic for 2023/933
Title:
Concrete NTRU Security and Advances in Practical Lattice-Based Electronic Voting
Authors: Patrick Hough, Caroline Sandsbråten, Tjerand Silde
Abstract: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.
ePrint: https://eprint.iacr.org/2023/933
See all topics related to this paper.
Feel free to post resources that are related to this paper below.
Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.
For more information, see the rules for Resource Topics .