NTWE: A Natural Combination of NTRU and LWE

Joel Gärtner

Paper 2023/663

NTWE: A Natural Combination of NTRU and LWE

Joel Gärtner

, Royal Institute of Technology

Abstract

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.

Metadata

Available format(s): PDF
Category: Public-key cryptography
Publication info: Published elsewhere. Minor revision. PQCrypto 2023
DOI: 10.1007/978-3-031-40003-2_12
Keywords: Lattice-based cryptography Post-quantum cryptography Public Key Encryption NTRU Learning With Errors
Contact author(s): jgartner @ kth se
History: 2024-12-20: revised; 2023-05-10: received; See all versions
Short URL: https://ia.cr/2023/663
License: CC BY

BibTeX

@misc{cryptoeprint:2023/663,
      author = {Joel Gärtner},
      title = {{NTWE}: A Natural Combination of {NTRU} and {LWE}},
      howpublished = {Cryptology {ePrint} Archive, Paper 2023/663},
      year = {2023},
      doi = {10.1007/978-3-031-40003-2_12},
      url = {https://eprint.iacr.org/2023/663}
}