Paper 2023/1298

NEV: Faster and Smaller NTRU Encryption using Vector Decoding

Jiang Zhang, State Key Laboratory of Cryptology, P.O. Box 5159, Beijing 100878, China.
Dengguo Feng, State Key Laboratory of Cryptology, P.O. Box 5159, Beijing 100878, China.
Di Yan, State Key Laboratory of Cryptology, P.O. Box 5159, Beijing 100878, China.

In this paper, we present NEV -- a faster and smaller NTRU Encryption using Vector decoding, which is provably IND-CPA secure in the standard model under the decisional NTRU and RLWE assumptions over the cyclotomic ring $R_q = \mathbb{Z}_q[X]/(X^n+1)$. Our main technique is a novel and non-trivial way to integrate a previously known plaintext encoding and decoding mechanism into the provably IND-CPA secure NTRU variant by Stehl\'e and Steinfeld (Eurocrypt 2011). Unlike the original NTRU encryption and its variants which encode the plaintext into the least significant bits of the coefficients of a message polynomial, we encode each plaintext bit into the most significant bits of multiple coefficients of the message polynomial, so that we can use a vector of noised coefficients to decode each plaintext bit in decryption, and significantly reduce the size of $q$ with a reasonably negligible decryption failure. Concretely, we can use $q = 769$ to obtain public keys and ciphertexts of 615 bytes with decryption failure $\leq 2^{-138}$ at NIST level 1 security, and 1229 bytes with decryption failure $\leq 2^{-152}$ at NIST level 5 security. By applying the Fujisaki-Okamoto transformation in a standard way, we obtain an IND-CCA secure KEM from our basic PKE scheme. Compared to NTRU and Kyber in the NIST Round 3 finalists at the same security levels, our KEM is 33-48% more compact and 5.03-29.94X faster than NTRU in the round-trip time of ephemeral key exchange, and is 21% more compact and 1.42-1.74X faster than Kyber. We also give an optimized encryption scheme NEV' with better noise tolerance (and slightly better efficiency) based on a variant of the RLWE problem, called Subset-Sum Parity RLWE problem, which we show is polynomially equivalent to the standard decisional RLWE problem (with different parameters), and maybe of independent interest.

Available format(s)
Public-key cryptography
Publication info
A minor revision of an IACR publication in ASIACRYPT 2023
LatticesPost-quantum cryptographyPKEKEMNTRU
Contact author(s)
zhangj @ sklc org
fengdg @ 263 net
yand @ sklc org
2023-09-02: approved
2023-08-31: received
See all versions
Short URL
Creative Commons Attribution-NonCommercial


      author = {Jiang Zhang and Dengguo Feng and Di Yan},
      title = {{NEV}:  Faster and Smaller {NTRU} Encryption using Vector Decoding},
      howpublished = {Cryptology ePrint Archive, Paper 2023/1298},
      year = {2023},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.