On the hardness of NTRU problems

Daniel Cabarcas, Patrick Weiden, Johannes A Buchmann

Wenjuan Jia, Jiang Zhang, Baocang Wang

The module learning with errors (MLWE) problem has attracted significant attention and has been widely used in building a multitude of lattice‐based cryptographic primitives. The hardness of the MLWE problem has been established for several variants, but most of the known results require the seed distribution (i.e., the distribution of matrix A ) to be the uniform distribution. In this paper, we show that under the Module‐N‐th degree Truncated polynomial Ring Units (NTRU) (MNTRU) assumption, the search MLWE problem can still be hard for some distributions that are not (even computationally indistinguishable from) the uniform distribution. Specifically, we show that if the seed distribution is a semiuniform distribution (namely, the seed distribution can be publicly derived from and has a “small difference” to the uniform distribution), then for appropriate settings of parameters, the search MLWE problem is hard under the MNTRU assumption. Moreover, we also show that under the appropriate settings of parameters, the search learning with errors over rings problem with semiuniform seeds can still be hard under the NTRU assumption due to our results for the search MLWE problem with semiuniform seeds being rank‐preserving.

Dipayan Das, Vishal Saraswat, Kajla Basu

Recently, lattice signatures based on the Fiat‐Shamir framework have seen a lot of improvements which are efficient in practice. The security of these signature schemes depends mainly on the hardness of solving short integer solutions (SIS) and/or learning with errors problem in the random oracle model. The authors propose an alternative lattice‐based signature scheme on the Fiat‐Shamir framework over the ring . The key generation in the signature scheme is based on the combination of NTRU and Ring SIS like key generation. Both the signature and the verification are done efficiently by doing polynomial convolutions in the ring . The proposed signature scheme is provably secure based on the hardness of the Ring SIS problem in the random oracle model. The scheme is also efficient up to constant factors as the highly practical schemes which have provable secure instantiation.

Julien Duman, Kathrin Hövelmanns, Eike Kiltz +3 more

Henry C. Ukwuoma, Arome Junior Gabriel, Aderonke Favour-Bethy Thompson +1 more

The safety and security of various cryptosystems are related to the hardness of the integer factorization problem and discrete logarithm problem, most cryptosystems will be rendered vulnerable to attack and outdated as quantum computers become more advanced.This study examines lattice-based cryptography (the NTRU cryptosystem), compares the suggested variation to other cryptosystems by simulation and presents the execution time for key generation, encryption, and decryption procedures, as well as to highlight the benefits and drawbacks of the proposed cryptosystem.A variant of the NTRU cryptosystem is developed with the purpose of improving the cryptosystem's security by allowing it to withstand attacks in both classical and quantum computing.The simulation revealed that the existing NTRU cryptosystem has a better time complexity compared to the proposed NTRU cryptosystem.The existing NTRU cryptosystem has a time complexity of O(n 2 ) while the proposed variant has O(n 3 ).Though had a better capacity of handling large data because of the introduction of lattice multiplication.