Paper 2019/1468

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

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


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.

Available format(s)
Public-key cryptography
Publication info
Preprint. Minor revision.
SIS trapdoorModule-NTRU latticeIdentity-based encryption
Contact author(s)
jhcheon @ snu ac kr
doodoo1204 @ snu ac kr
taechan kim ym @ hco ntt co jp
emsskk @ snu ac kr
2019-12-23: received
Short URL
Creative Commons Attribution


      author = {Jung Hee Cheon and Duhyeong Kim and Taechan Kim and Yongha Son},
      title = {A New Trapdoor over Module-NTRU Lattice and its Application to ID-based Encryption},
      howpublished = {Cryptology ePrint Archive, Paper 2019/1468},
      year = {2019},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.