Cryptology ePrint Archive: Report 2019/1468

A New Trapdoor over Module-NTRU Lattice and its Application to ID-based Encryption

Jung Hee Cheon and Duhyeong Kim and Taechan Kim and Yongha Son

Abstract: A trapdoor over NTRU lattice proposed by Ducas, Lyubashevsky and Prest~(ASIACRYPT 2014) has been widely used in various crytographic primitives such as identity-based encryption~(IBE) and digital signature, due to its high efficiency compared to previous lattice trapdoors. However, the most of applications use this trapdoor with the power-of-two cyclotomic rings, and hence to obtain higher security level one should double the ring dimension which results in a huge loss of efficiency.

In this paper, we give a new way to overcome this problem by introducing a generalized notion of NTRU lattices which we call \emph{Module-NTRU}~(MNTRU) lattices, and show how to efficiently generate a trapdoor over MNTRU lattices. Moreover, beyond giving parameter flexibility, we further show that the Gram-Schmidt norm of the trapdoor can be reached to about $q^{1/d},$ where MNTRU covers $d \ge 2$ cases while including NTRU as $d = 2$ case. Since the efficiency of trapdoor-based IBE is closely related to the Gram-Schmidt norm of trapdoor, our trapdoor over MNTRU lattice brings more efficient IBE scheme than the previously best one of Ducas, Lyubashevsky and Prest, while providing the same security level.

Category / Keywords: public-key cryptography / SIS trapdoor, Module-NTRU lattice, Identity-based encryption

Date: received 18 Dec 2019, last revised 18 Dec 2019

Contact author: jhcheon at snu ac kr,doodoo1204@snu ac kr,taechan kim ym@hco ntt co jp,emsskk@snu ac kr

Available format(s): PDF | BibTeX Citation

Version: 20191223:152213 (All versions of this report)

Short URL:

[ Cryptology ePrint archive ]