Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

Lecture notes in computer science

Making NTRU as Secure as Worst-Case Problems over Ideal Lattices

Damien Stehlé, Ron Steinfeld

Published Jan 1, 2011• 444 citations
Publisher
DOI
10.1007/978-3-642-20465-4_4

Related papers

Making NTRUEncrypt and NTRUSign as Secure as Standard Worst-Case Problems over Ideal Lattices.

Damien Stehlé, Ron Steinfeld

•Jan 1, 2013•43 citations

Concurrently Secure Identification Schemes Based on the Worst-Case Hardness of Lattice Problems

Akinori Kawachi, Keisuke Tanaka, Keita Xagawa

Lecture notes in computer science•Jan 1, 2008•217 citations

Concurrently Secure Identification Schemes Based on the Worst-Case Hardness of Lattice Problems

亮周 河内, Akinori Kawachi, KEISUKE TANAKA +2 more

•Dec 1, 2008•0 citations

Lattice signatures using NTRU on the hardness of worst‐case ideal lattice problems

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.

IET Information Security•Jun 2, 2020•5 citations

Towards Efficient Lattice-Based Cryptography

Richard Lindner

One essential quest in cryptography is the search for hard instances of a given computational problem that is known to be hard in the worst-case. In lattice cryptography we are in the unique situation that we have found a way of picking random instances which are at least as hard as well-studied lattice problems in the worst-case. At the same time, no attack running in subexponential time is known to break these problems, even for an adversary using quantum computers. Virtually all public-key schemes in use today are subject to such attacks, and the development of quantum computers is actively pursued, so it is prudent to investigate lattice-based alternatives. There are two fundamental open problems in lattice cryptography today and this thesis contributes to solving them. First, there exists a widely used efficiency improvement that allows for trapdoors whose asymptotic keysize and evaluation time are both quasilinear in the dimension of an associated lattice. This is accomplished by restricting oneself to lattices with special structure, so-called ideal lattices. This entails the use of newer security assumptions, but these have not been analyzed thoroughly so far. We start this work by comparing the class of ideal lattice problems with its general counterpart in terms of size. Affirming folklore, we find the number of restricted instances among all instances to be asymptotically negligible for those classes of lattices suggested for practical use. The second open problem is that while the connection to worst-case problems is well understood, the practical hardness of the related average-case problems is not. Specifically, there have been parameters suggested for practical usage, where current lattice basis reduction algorithms can solve these worst-case problems, but the related average-case problems, which these are reduced to and which represent the basis of practical security of the cryptosystems, are completely infeasible. In most cases, this lack of understanding has lead either to a very conservative choice of parameters, or none at all. This in turn makes it impossible for the resulting lattice schemes to compete with their counterparts based on other paradigms. We further the understanding of this practical security and at the same time improve the efficiency of several common related cryptographic schemes. Among other things, we find that for the SWIFFT compression function, solving certain problems closely related to finding collisions is easier than previously thought and we suggest efficient replacement parameters. We propose a novel zero-knowledge identification scheme that, to our knowledge, beats all competing post-quantum schemes, even those based on other paradigms. Possibly most important, we help to tighten the efficiency gap between lattice encryption schemes that are provably secure and the acclaimed ad-hoc encryption scheme NTRU. This is done by unifying many recent developments into a new provably secure design and providing a comprehensive analysis of practical security, which together results in a great leap of efficiency.

•Jan 1, 2011•0 citations

On the Efficiency of Provably Secure NTRU

Daniel Cabarcas, Patrick Weiden, Johannes A Buchmann

Lecture notes in computer science•Jan 1, 2014•14 citations
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.
One essential quest in cryptography is the search for hard instances of a given computational problem that is known to be hard in the worst-case. In lattice cryptography we are in the unique situation that we have found a way of picking random instances which are at least as hard as well-studied lattice problems in the worst-case. At the same time, no attack running in subexponential time is known to break these problems, even for an adversary using quantum computers. Virtually all public-key schemes in use today are subject to such attacks, and the development of quantum computers is actively pursued, so it is prudent to investigate lattice-based alternatives. There are two fundamental open problems in lattice cryptography today and this thesis contributes to solving them. First, there exists a widely used efficiency improvement that allows for trapdoors whose asymptotic keysize and evaluation time are both quasilinear in the dimension of an associated lattice. This is accomplished by restricting oneself to lattices with special structure, so-called ideal lattices. This entails the use of newer security assumptions, but these have not been analyzed thoroughly so far. We start this work by comparing the class of ideal lattice problems with its general counterpart in terms of size. Affirming folklore, we find the number of restricted instances among all instances to be asymptotically negligible for those classes of lattices suggested for practical use. The second open problem is that while the connection to worst-case problems is well understood, the practical hardness of the related average-case problems is not. Specifically, there have been parameters suggested for practical usage, where current lattice basis reduction algorithms can solve these worst-case problems, but the related average-case problems, which these are reduced to and which represent the basis of practical security of the cryptosystems, are completely infeasible. In most cases, this lack of understanding has lead either to a very conservative choice of parameters, or none at all. This in turn makes it impossible for the resulting lattice schemes to compete with their counterparts based on other paradigms. We further the understanding of this practical security and at the same time improve the efficiency of several common related cryptographic schemes. Among other things, we find that for the SWIFFT compression function, solving certain problems closely related to finding collisions is easier than previously thought and we suggest efficient replacement parameters. We propose a novel zero-knowledge identification scheme that, to our knowledge, beats all competing post-quantum schemes, even those based on other paradigms. Possibly most important, we help to tighten the efficiency gap between lattice encryption schemes that are provably secure and the acclaimed ad-hoc encryption scheme NTRU. This is done by unifying many recent developments into a new provably secure design and providing a comprehensive analysis of practical security, which together results in a great leap of efficiency.