Security Analysis of Hybrid Attack for NTRU-Class Encryption Schemes

Abstract

One of the significant post-quantum cryptographic candidates is the NTRU public key cryptosystem. It operates on polynomial rings, where the parameter largely determines the security of the system. Although NTRU is being studied currently, it has a long and well-established history. There are several lattice-based attacks on NTRU-like systems that exploit the special structures of the rings used in these systems. The aim of this paper is to analyze the original NTRU, NTRU Encrypt, and NTRU Primes encryption schemes by structuring their common elements and showing the strongest hybrid attack using both lattice reduction and meet-in-the-middle (MITM) search on them. Furthermore, it is noted that, ignoring a polynomial factor of the not-well-studied cost of Block Korkin-Zolotarev (BKZ) algorithm, we estimate the security of the construction of encryption keys and show that by balancing lattice reduction costs and a MITM search cost, one can achieve better performance than using any of these methods on their own. Unlike previous studies, we found the way to ignore polynomial impact 22-24 from BKZ loops with multiple shortest vector problem (SVP) and the factor of 27 was omitted from the cost of one step in guessing the SVP.

Keywords

• BKZ algorithm
• cryptography
• ideals
• lattices
• LLL algorithm
• NTRU