Paper 2024/1282

NTRU+PKE: Efficient Public-Key Encryption Schemes from the NTRU Problem

Abstract

We propose a new NTRU-based Public-Key Encryption (PKE) scheme called $\mathsf{NTRU}\mathsf{+}\mathsf{PKE}$, which effectively incorporates the Fujisaki-Okamoto transformation for PKE (denoted as ${\mathsf{FO}}_{\mathsf{PKE}}$) to achieve chosen-ciphertext security in the Quantum Random Oracle Model (QROM). While $\mathsf{NTRUEncrypt}$, a first-round candidate in the NIST PQC standardization process, was proven to be chosen-ciphertext secure in the Random Oracle Model (ROM), it lacked corresponding security proofs for QROM. Our work extends the capabilities of the recent $$ transformation, proposed by Kim and Park in 2023, by demonstrating that an $$-transformed scheme can serve as a sufficient foundation for applying $$. Specifically, we show that the $$-transformed scheme achieves (weak) $$-spreadness, an essential property for constructing an IND-CCA secure PKE scheme. Moreover, we provide the first proof of the security of $$ in the QROM. Finally, we show that $$ can be further optimized into a more efficient transformation, $$, which eliminates the need for re-encryption during decryption. By instantiating an $$-transformed scheme with appropriate parameterizations, we construct $$, which supports 256-bit message encryption. Our implementation results demonstrate that at approximately a classical 180-bit security level, $$ is about 2 times faster than \textsc{Kyber} + AES-256-GCM in AVX2 mode.