Paper 2023/663

NTWE: A Natural Combination of NTRU and LWE

Joel Gärtner, Royal Institute of Technology

Lattice-based cryptosystems are some of the primary post-quantum secure alternatives to the asymmetric cryptography that is used today. These lattice-based cryptosystems typically rely on the hardness of some version of either the NTRU or the LWE problem. In this paper, we present the NTWE problem, a natural combination of the NTRU and LWE problems, and construct a new lattice-based cryptosystem based on the hardness of the NTWE problem. As with the NTRU and LWE problems, the NTWE problem naturally corresponds to a problem in a $q$-ary lattice. This allows the hardness of the NTWE problem to be estimated in the same way as it is estimated for the LWE and NTRU problems. We parametrize our cryptosystem from such a hardness estimate and the resulting scheme has performance that is competitive with that of typical lattice-based schemes. In some sense, our NTWE-based cryptosystem can be seen as a less structured and more compact version of a cryptosystem based on the module-NTRU problem. Thus, parameters for our cryptosystem can be selected with the flexibility of a module-LWE-based scheme, while other properties of our system are more similar to those in an NTRU-based system.

Available format(s)
Public-key cryptography
Publication info
Lattice-based cryptographyPost-quantum cryptographyPublic Key EncryptionNTRULearning With Errors
Contact author(s)
jgartner @ kth se
2023-05-11: approved
2023-05-10: received
See all versions
Short URL
Creative Commons Attribution


      author = {Joel Gärtner},
      title = {NTWE: A Natural Combination of NTRU and LWE},
      howpublished = {Cryptology ePrint Archive, Paper 2023/663},
      year = {2023},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.