Paper 2024/732

Compact Encryption based on Module-NTRU problems

Abstract

The Module-NTRU problem, introduced by Cheon, Kim, Kim, Son (IACR ePrint 2019/1468), and Chuengsatiansup, Prest, Stehlé, Wallet, Xagawa (ASIACCS ’20), generalizes the versatile NTRU assump- tion. One of its main advantages lies in its ability to offer greater flexibil- ity on parameters, such as the underlying ring dimension. In this work, we present several lattice-based encryption schemes, which are IND-CPA (or OW-CPA) secure in the standard model based on the Module-NTRU and Module-LWE problems. Leveraging the Fujisaki-Okamoto transfor- mations, one can obtain IND-CCA secure key encapsulation schemes. Our first encryption scheme is based on the Module-NTRU assumption, which uses the determinant of the secret matrix over the underlying ring for the decryption. Our second scheme is analogue to the Module-LWE encryption scheme, but uses only a matrix as the public key, based on a vectorial variant of the Module-NTRU problem. In the end, we conduct comprehensive analysis of known attacks and propose concrete parame- ters for the instantiations. In particular, our ciphertext size is about 614 (resp. 1228) bytes for NIST Level 1 (resp. Level 5) security and small decryption failure, placing it on par with the most recent schemes such as the one proposed by Zhang, Feng and Yan (ASIACRYPT ’23). We also present several competitive parameters for NIST Level 3, which has a ci- phertext size of 921 bytes. Moreover, our schemes do not require specific codes for plaintext encoding and decoding.