Cryptology ePrint Archive: Report 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 ${\cal S}$ runs in time ${\cal 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 ${\cal S}^{0.25}$, which also beats the ${\cal S}^{\frac 1 3}$ complexity of the best known quantum algorithm.

For the round-3 NIST post-quantum encryptions NTRU-Encrypt and NTRU-Prime we obtain non-asymptotic instantiations of our attack with complexity roughly ${\cal S}^{0.35}$. 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 signatures we obtain non-asymptotic combinatorial attacks in between ${\cal S}^{0.31}$ and ${\cal S}^{0.35}$, for GLP signatures in ${\cal S}^{0.3}$.

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.

Keywords: Meet in the Middle, Representation Technique, NTRU/BLISS/GLP

Category / Keywords: public-key cryptography / cryptanalysis

Date: received 26 Feb 2021, last revised 26 Feb 2021

Contact author: alex may at rub de

Available format(s): PDF | BibTeX Citation

Version: 20210302:145710 (All versions of this report)

Short URL: ia.cr/2021/216