Paper 2021/216

How to Meet Ternary LWE Keys

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.

Note: Full version.

Metadata
Available format(s)
PDF
Category
Public-key cryptography
Publication info
A minor revision of an IACR publication in Crypto 2021
Keywords
cryptanalysis
Contact author(s)
alex may @ rub de
History
2021-06-25: last of 2 revisions
2021-03-02: received
See all versions
Short URL
https://ia.cr/2021/216
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2021/216,
      author = {Alexander May},
      title = {How to Meet Ternary LWE Keys},
      howpublished = {Cryptology ePrint Archive, Paper 2021/216},
      year = {2021},
      note = {\url{https://eprint.iacr.org/2021/216}},
      url = {https://eprint.iacr.org/2021/216}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.