Paper 2022/579

Compact and Efficient NTRU-based KEM with Scalable Ciphertext Compression

Zhichuang Liang, Boyue Fang, Jieyu Zheng, and Yunlei Zhao


Post-quantum cryptography (PQC) is critical to the next generation of network security. The NTRU lattice is a promising candidate to construct practical cryptosystems resistant to quantum computing attacks, and particularly plays a leading role in the ongoing NIST post-quantum cryptography standardization. On the one hand, it is benefited from a strong security guarantee since it has essentially not been broken over 24 years. On the other hand, all the known patent threats against NTRU have expired, which is deemed a critical factor for consideration when deploying PQC algorithms in reality. Nevertheless, there are still some obstacles to the computational efficiency and bandwidth complexity of NTRU-based constructions of key encapsulation mechanisms (KEM). To address these issues, we propose a compact and efficient KEM based on the NTRU lattice, called CTRU, by introducing a scalable ciphertext compression technique. It demonstrates a new approach to decrypting NTRU ciphertext, where the plaintext message is recovered with the aid of our decoding algorithm in the scalable $\text{E}_8$ lattice (instead of eliminating the extra terms modulo $p$ in traditional NTRU-based KEM schemes). The instantiation of CTRU is over the NTT-friendly rings of the form $\mathbb{Z}_q[x]/(x^{n}-x^{n/2}+1)$. We remark that the scalable ciphertext compression technique can also be applied to NTRU-based KEM schemes over other polynomial rings. In order to deal with the inconvenient issue that various NTT algorithms are needed for different $n$'s, we present a unified NTT methodology over $\mathbb{Z}_q[x]/(x^n-x^{n/2}+1)$, $n\in \{512,768,1024\}$, such that only one type of NTT computation is required for different $n$'s, which might be of independent interest. To our knowledge, our CTRU is the most bandwidth efficient KEM based on the NTRU lattice up to now. In addition, roughly speaking, compared to other NTRU-based KEM schemes, CTRU has stronger security against known attacks, enjoys more robust CCA security reduction (starting from IND-CPA rather than OW-CPA), and its encapsulation and decapsulation processes are also among the most efficient. For example, when compared to the NIST Round 3 finalist NTRU-HRSS, our CTRU-768 has $15\%$ smaller ciphertext size and its security is strengthened by $(45,40)$ bits for classical and quantum security respectively. When compared to the NIST Round 3 finalist Kyber that is based on the Module-LWE (MLWE) assumption, CTRU has both smaller bandwidth and lower error probabilities at about the same security level.

Available format(s)
Public-key cryptography
Publication info
Preprint. MINOR revision.
Post-quantum cryptographyNTRUBandwidth efficiencyNumber theoretic transform
Contact author(s)
ylzhao @ fudan edu cn
2022-05-16: received
Short URL
Creative Commons Attribution


      author = {Zhichuang Liang and Boyue Fang and Jieyu Zheng and Yunlei Zhao},
      title = {Compact and Efficient NTRU-based KEM with Scalable Ciphertext Compression},
      howpublished = {Cryptology ePrint Archive, Paper 2022/579},
      year = {2022},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.