International Association for Cryptologic Research

International Association
for Cryptologic Research


NEV: Faster and Smaller NTRU Encryption using Vector Decoding

Jiang Zhang , State Key Laboratory of Cryptology
Dengguo Feng , State Key Laboratory of Cryptology
Di Yan , State Key Laboratory of Cryptology
Search ePrint
Search Google
Presentation: Slides
Conference: ASIACRYPT 2023
Abstract: 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 = \ZZ_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. \qquad 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.
  title={NEV: Faster and Smaller NTRU Encryption using Vector Decoding},
  author={Jiang Zhang and Dengguo Feng and Di Yan},