Paper 2019/1451
Tight bound on NewHope failure probability
Thomas Plantard, Arnaud Sipasseuth, Willy Susilo, and Vincent Zucca
Abstract
NewHope Key Encapsulation Mechanism (KEM) has been presented at USENIX 2016 by Alchim et al. and is one of the remaining lattice-based candidates to the post-quantum standardization initiated by the NIST. However, despite the relative simplicity of the protocol, the bound on the decapsulation failure probability resulting from the original analysis is not tight. In this work we refine this analysis to get a tight upper-bound on this probability which happens to be much lower than what was originally evaluated. As a consequence we propose a set of alternnative parameters, increasing the security and the compactness of the scheme. However using a smaller modulus prevent the use of a full NTT algorithm to perform multiplications of elements in dimension 512 or 1024. Nonetheless, similarly to previous works, we combine different multiplication algorithms and show that our new parameters are competitive on a constant time vectorized implementation. Our most compact parameters bring a speed- up of 17% (resp. 11%) in performance but allow to gain more than 19% over the bandwidth requirements and to increase the security of 10% (resp. 7%) in dimension 512 (resp. 1024).
Metadata
- Available format(s)
-
PDF
- Category
- Public-key cryptography
- Publication info
- Preprint. MINOR revision.
- Keywords
- Post-Quantum CryptographyKaratsubaNum- ber Theoretic TransformAVX implementationLattice Based CryptographyRing-LWE
- Contact author(s)
- vincent zucca @ kuleuven be
- History
- 2020-01-09: revised
- 2019-12-16: received
- See all versions
- Short URL
- https://ia.cr/2019/1451
- License
-
CC BY
BibTeX
@misc{cryptoeprint:2019/1451,
author = {Thomas Plantard and Arnaud Sipasseuth and Willy Susilo and Vincent Zucca},
title = {Tight bound on NewHope failure probability},
howpublished = {Cryptology ePrint Archive, Paper 2019/1451},
year = {2019},
note = {\url{https://eprint.iacr.org/2019/1451}},
url = {https://eprint.iacr.org/2019/1451}
}
