Welcome to the resource topic for 2021/216
Title:
How to Meet Ternary LWE Keys
Authors: Alexander May
Abstract:The LWE problem with its ring variants is today the most prominent candidate for building efficient public key cryptosystems resistant to quantum computers. NTRU-type cryptosystems use an LWE-type variant with small max-norm secrets, usually with ternary coefficients from the set \{-1,0,1\}. The presumably best attack on these schemes is a hybrid attack that combines lattice reduction techniques with Odlyzko’s Meet-in-the-Middle approach. Odlyzko’s algorithm is a classical combinatorial attack that for key space size S runs in time S^{0.5}. We substantially improve on this Meet-in-the-Middle approach, using the representation technique developed for subset sum algorithms. Asymptotically, our heuristic Meet-in-the-Middle attack runs in time roughly S^{0.25}, which also beats the S^{\frac 1 3} complexity of the best known quantum algorithm. For the round-3 NIST post-quantum encryptions NTRU and NTRU Prime we obtain non-asymptotic instantiations of our attack with complexity roughly S^{0.3}. As opposed to other combinatorial attacks, our attack benefits from larger LWE field sizes q, as they are often used in modern lattice-based signatures. For example, for BLISS and GLP signatures we obtain non-asymptotic combinatorial attacks around S^{0.28}. Our attacks do not invalidate the security claims of the aforementioned schemes. However, they establish improved combinatorial upper bounds for their security. We leave it is an open question whether our new Meet-in-the-Middle attack in combination with lattice reduction can be used to speed up the hybrid attack.
ePrint: https://eprint.iacr.org/2021/216
Talk: https://www.youtube.com/watch?v=Fa6PxC5ufvU
Slides: https://iacr.org/submit/files/slides/2021/crypto/crypto2021/226/slides.pdf
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 .