Paper 2022/579

Compact and Efficient KEMs over NTRU Lattices

Abstract

The NTRU lattice is a promising candidate to construct practical cryptosystems, in particular key encapsulation mechanism (KEM), resistant to quantum computing attacks. Nevertheless, there are still some inherent obstacles to NTRU-based KEM schemes in having integrated performance, taking security, bandwidth, error probability, and computational efficiency {as a whole}, that is as good as and even better than their \{R,M\}LWE-based counterparts. In this work, we solve this problem by presenting a new family of NTRU-based KEM schemes, referred to as CTRU and CNTR. By bridging low-dimensional lattice codes and high-dimensional NTRU-lattice-based cryptography with careful design and analysis, to the best of our knowledge CTRU and CNTR are the first NTRU-based KEM schemes with scalable ciphertext compression via only one {single} ciphertext polynomial, and are the first that could outperform \{R,M\}LWE-based KEM schemes in integrated performance. For instance, compared to Kyber that is currently the only standardized KEM by NIST, on the recommended parameter set CNTR-768 has about $12\%$ smaller ciphertext size while encapsulating 384-bit keys compared to the fixed 256-bit key size of Kyber, security strengthened by $(8,7)$ bits for classical and quantum security respectively, and significantly lower error probability ($2^{-230}$ of CNTR-768 vs. $2^{-164}$ of Kyber-768). In particular, CTRU and CNTR admit more flexible key sizes to be encapsulated, specifically $\frac{n}{2}$ where $n\in \{512,768,1024\}$ is the underlying polynomial dimension. In comparison with the state-of-the-art AVX2 implementation of Kyber-768, CNTR-768 is faster by 1.9X in KeyGen, 2.6X in Encaps, and 1.2X in Decaps, respectively. When compared to the NIST Round 3 finalist NTRU-HRSS, our CNTR-768 has about $15\%$ smaller ciphertext size, and the security is strengthened by $(55,49)$ bits for classical and quantum security respectively. As for the AVX2 implementation, CNTR-768 is faster than NTRU-HRSS by 19X in KeyGen, 2.3X in Encaps, and 1.6X in Decaps, respectively. Along the way, we develop new techniques for more accurate error probability analysis, as well as unified implementations with respect to multiple dimensions with unified NTT methods, for NTRU-based KEM schemes over the polynomial ring $\mathbb{Z}_q[x]/(x^n-x^{n/2}+1)$, which might be of independent interest.