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