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

ACM Symposium on Theory of Computing (STOC)

Trapdoors for hard lattices and new cryptographic constructions

Craig Gentry, Chris Peikert, Vinod Vaikuntanathan

Published May 17, 2008• 2,568 citations
Publisher

Abstract

We show how to construct a variety of "trapdoor" cryptographic tools assuming the worst-case hardness of standard lattice problems (such as approximating the length of the shortest nonzero vector to within certain polynomial factors). Our contributions include a new notion of trapdoor function with preimage sampling, simple and efficient "hash-and-sign" digital signature schemes, and identity-based encryption. A core technical component of our constructions is an efficient algorithm that, given a basis of an arbitrary lattice, samples lattice points from a discrete Gaussian probability distribution whose standard deviation is essentially the length of the longest Gram-Schmidt vector of the basis. A crucial security property is that the output distribution of the algorithm is oblivious to the particular geometry of the given basis.

DOI
10.1145/1374376.1374407

Related papers

Lattice-based identity-based ring signature without trapdoors

Yongxuan Sang, Zhongwen Li, Lili Zhang +2 more

So far, most ring signature schemes rely on hard number theory problems, such as discrete logarithm, bilinear pairings and so on. Unfortunately, the above underlying number theory problems will be solvable in the post quantum era. Lattice-based cryptography is a hotspot of research recently, due to its implementation simplicity and provable security reductions. When the hash-and-sign signature scheme was constructed based on the hardness of worst-case lattice problems, provably secure lattice-based ring signature schemes were finally constructed. However, the hash-and-sign ring signatures were rather inefficient (with megabytes long signatures). In this paper, we propose an alternative method for constructing lattice-based and identity-based ring signature scheme which does not use the hash-and-sign methodology. In the random oracle model, the proposed signature scheme based on the problem in general lattices is unforgeable and holds anonymity. Compared with the previous instantiations of the hash-and-sign ring signature schemes, the lengths of secret key, public key and signatures in the proposed scheme are much shorter. The signing algorithm is quite simple, with matrix-vector multiplications and rejection samplings.

International Journal of Embedded Systems•Jan 1, 2019•5 citations

New lattice-based cryptographic constructions

Oded Regev

We introduce the use of Fourier analysis on lattices as an integral part of a lattice-based construction. The tools we develop provide an elegant description of certain Gaussian distributions around lattice points. Our results include two cryptographic constructions that are based on the worst-case hardness of the unique shortest vector problem. The main result is a new public key cryptosystem whose security guarantee is considerably stronger than previous results ( O ( n 1.5 ) instead of O ( n 7 )). This provides the first alternative to Ajtai and Dwork's original 1996 cryptosystem. Our second result is a family of collision resistant hash functions with an improved security guarantee in terms of the unique shortest vector problem. Surprisingly, both results are derived from one theorem that presents two indistinguishable distributions on the segment [0, 1). It seems that this theorem can have further applications; as an example, we use it to solve an open problem in quantum computation related to the dihedral hidden subgroup problem.

arXiv:cs/0309051•Journal of the ACM•Nov 1, 2004•299 citations

New lattice based cryptographic constructions

Oded Regev

We introduce the use of Fourier analysis on lattices as an integral part of a lattice based construction. The tools we develop provide an elegant description of certain Gaussian distributions around lattice points. Our results include two cryptographic constructions which are based on the worst-case hardness of the unique shortest vector problem. The main result is a new public key cryptosystem whose security guarantee is considerably stronger than previous results (O(n1.5) instead of O(n7)). This provides the first alternative to Ajtai and Dwork's original 1996 cryptosystem. Our second result is a collision resistant hash function which, apart from improving the security in terms of the unique shortest vector problem, is also the first example of an analysis which is not based on Ajtai's iterative step. Surprisingly, the two results are derived from the same tool which presents two indistinguishable distributions on the segment [0,1]. It seems that this tool can have further applications and as an example we mention how it can be used to solve an open problem related to quantum computation.

ACM Symposium on Theory of Computing (STOC)•Jun 9, 2003•87 citations

New lattice based cryptographic constructions

Oded Regev

We introduce the use of Fourier analysis on lattices as an integral part of a lattice based construction. The tools we develop provide an elegant description of certain Gaussian distributions around lattice points. Our results include two cryptographic constructions which are based on the worst-case hardness of the unique shortest vector problem. The main result is a new public key cryptosystem whose security guarantee is considerably stronger than previous results (O(n1.5) instead of O(n7)). This provides the first alternative to Ajtai and Dwork's original 1996 cryptosystem. Our second result is a collision resistant hash function which, apart from improving the security in terms of the unique shortest vector problem, is also the first example of an analysis which is not based on Ajtai's iterative step. Surprisingly, the two results are derived from the same tool which presents two indistinguishable distributions on the segment [0,1]. It seems that this tool can have further applications and as an example we mention how it can be used to solve an open problem related to quantum computation.

ACM Symposium on Theory of Computing (STOC)•Jan 1, 2003•17 citations

Lattice-based identity-based ring signature without trapdoors

Lili Zhang, Zhongwen Li, Yongxuan Sang

So far, most ring signature schemes rely on hard number theory problems, such as discrete logarithm, bilinear pairings and so on. Unfortunately, the above underlying number theory problems will be solvable in the post quantum era. Lattice-based cryptography is a hotspot of research recently, due to its implementation simplicity and provable security reductions. When the hash-and-sign signature scheme was constructed based on the hardness of worst-case lattice problems, provably secure lattice-based ring signature schemes were finally constructed. However, the hash-and-sign ring signatures were rather inefficient (with megabytes long signatures). In this paper, we propose an alternative method for constructing lattice-based and identity-based ring signature scheme which does not use the hash-and-sign methodology. In the random oracle model, the proposed signature scheme based on the problem in general lattices is unforgeable and holds anonymity. Compared with the previous instantiations of the hash-and-sign ring signature schemes, the lengths of secret key, public key and signatures in the proposed scheme are much shorter. The signing algorithm is quite simple, with matrix-vector multiplications and rejection samplings.

International Journal of High Performance Computing and Networking•Jan 1, 2018•0 citations

Lattice-based digital signatures

Vadim Lyubashevsky

Digital signatures and key exchange protocols are the two most important public key cryptographic primitives used in the electronic transmission of data. The goal of key exchange is to preserve the secrecy of the communication, while the goal of digital signatures is to guarantee the authenticity of the exchanged messages. Constructions of digital signature schemes based on classical mathematical assumptions appeared shortly following the invention of public key cryptography in the late 1970s. And just like with key exchange, the most efficient variants are based on number-theoretic problems that are believed to be (sub)-exponentially hard for classical machines, but are solved in polynomial time by Shor’s algorithm on a powerful-enough quantum computer. Also, like for key exchange, the most efficient constructions that we believe to be quantum safe are based on the presumed hardness of lattice problems over polynomial rings. One interesting difference between key exchange and digital signatures is that key exchange appears to inherently require that some mathematical problem be computationally hard. Digital signatures, on the other hand, can be generically constructed from any one-way function [1,2]. So even though they certainly fall into the category of public key primitives based on their usage, their existence requires much weaker assumptions. Additionally, the transformation from a one-way function to a digital signature is not too inefficient. For example, the total parameter size (public key + signature) of the SPHINCS+ scheme [3] is around 40 kB. While these sizes are larger, and signing times considerably longer, than those of signatures based on factoring or discrete log, it is still a usable scheme for many applications. And being only based on symmetric assumptions (e.g. one wayness and collision resistance of cryptographic hash functions), its security is very attractive. In order to be considered an interesting alternative to the above-mentioned signature, a scheme based on a mathematical assumption would need to have significant performance advantages. Schemes based on factoring and the discrete logarithm problem were significantly shorter and faster, and so the generic approach lay dormant for over four decades. The new quantum-safe schemes will need to have similar performance advantages if they are to be used in lieu of this safe approach. Below, we describe two techniques for constructing lattice-based digital signatures with output sizes being just a few kilobytes. On a very high level, lattice-based signature constructions follow the two known approaches for constructing classical signatures. In the first approach, the signer outputs a function f and an image y = f(x) as his public key and keeps x as his secret key. To sign a message μ, he gives a non-interactive zero-knowledge proof that he knows an x satisfying y = f(x), using the message μ to create the ‘challenge’ H(μ) for the proof (where H is a public function that maps μ to something ‘random looking’). If the function f is one way then the verifier should be convinced that the proof could have only been created by the entity who knows x. A classic example of this type of scheme is the Schnorr signature scheme [4] based on the hardness of the discrete logarithm problem. The second approach is to create a function f together with a trapdoor f−1, output f as the public key and keep f−1 as the secret key. A message μ is signed by using the secret trapdoor to create a pre-image x such that f(x) = H(μ). Again, if the function f is one way then only someone in possession of a trapdoor should be able to invert it. An example of such a construction based on a ‘factoring-like’ assumption is the RSA signature scheme [5]. The high-level ideas for lattice-based signatures follow the above blueprints, but the technical details are significantly more involved. The main reason for the complications is the different algebraic structure of the hard one-way function underlying lattice cryptography. While the domain of the function in discrete log and RSA-based one-way functions are groups, the domains in lattice-based signatures are sets that are not closed under any operation—in particular, they are elements in a group that have small norms. This crucial small norm requirement precludes us from using uniformly random masking as in Schnorr signatures or having a trapdoor for a bijective one-way function as in RSA signatures. These barriers have, nevertheless, been overcome and the resulting digital signatures are quite practical. In 2017, the US National Institute of Standards and Technology (NIST) began a ‘competition’ for a quantum-safe key exchange and digital signatures standard. At the time of this writing, this process is in the third round and there are two lattice-based signatures remaining—each following one of the above high-level designs. The CRYSTALS-Dilithium [6] scheme follows the Schnorr framework, but adds a crucial rejection-sampling step to keep the size of the coefficients small. The FALCON scheme [7] utilizes a randomized trapdoor sampling technique that uses a secret trapdoor for f−1 to produce random pre-images from a particular distribution. Because there is no longer a bijection, it is crucial to also have the property that the distribution of the outputted pre-images does not leak information about the trapdoor. Both schemes are relatively fast and their parameters (public key + signature size) are the shortest of all quantum-safe signature schemes. While both schemes are based on lattices, they have rather different characteristics. FALCON has very short parameters (see Table 1), but entails a rather complicated procedure for signature generation. In particular, it uses (an optimized version of) the GPV sampler [8], which requires floating-point arithmetic with approximately 64 bits of precision. Requiring such high precision means that subtle implementation errors may not get detected even with rigorous testing. Dilithium, on the other hand, has larger parameters but a very simple implementation where all the sampling in the signing is done in a power-of-2 range; it is thus much less prone to implementation errors. It is quite possible that in the future both schemes will be used for different applications. Approximate parameter sizes (in bytes) for the CRYSTALS-Dilithium and FALCON digital signature schemes at approximately 128-bit security levels. Approximate parameter sizes (in bytes) for the CRYSTALS-Dilithium and FALCON digital signature schemes at approximately 128-bit security levels. Conflict of interest statement. None declared.

National Science Review•Apr 28, 2021•9 citations
We show how to construct a variety of "trapdoor" cryptographic tools assuming the worst-case hardness of standard lattice problems (such as approximating the length of the shortest nonzero vector to within certain polynomial factors). Our contributions include a new notion of trapdoor function with preimage sampling, simple and efficient "hash-and-sign" digital signature schemes, and identity-based encryption. A core technical component of our constructions is an efficient algorithm that, given a basis of an arbitrary lattice, samples lattice points from a discrete Gaussian probability distribution whose standard deviation is essentially the length of the longest Gram-Schmidt vector of the basis. A crucial security property is that the output distribution of the algorithm is oblivious to the particular geometry of the given basis.
So far, most ring signature schemes rely on hard number theory problems, such as discrete logarithm, bilinear pairings and so on. Unfortunately, the above underlying number theory problems will be solvable in the post quantum era. Lattice-based cryptography is a hotspot of research recently, due to its implementation simplicity and provable security reductions. When the hash-and-sign signature scheme was constructed based on the hardness of worst-case lattice problems, provably secure lattice-based ring signature schemes were finally constructed. However, the hash-and-sign ring signatures were rather inefficient (with megabytes long signatures). In this paper, we propose an alternative method for constructing lattice-based and identity-based ring signature scheme which does not use the hash-and-sign methodology. In the random oracle model, the proposed signature scheme based on the problem in general lattices is unforgeable and holds anonymity. Compared with the previous instantiations of the hash-and-sign ring signature schemes, the lengths of secret key, public key and signatures in the proposed scheme are much shorter. The signing algorithm is quite simple, with matrix-vector multiplications and rejection samplings.
We introduce the use of Fourier analysis on lattices as an integral part of a lattice-based construction. The tools we develop provide an elegant description of certain Gaussian distributions around lattice points. Our results include two cryptographic constructions that are based on the worst-case hardness of the unique shortest vector problem. The main result is a new public key cryptosystem whose security guarantee is considerably stronger than previous results ( O ( n 1.5 ) instead of O ( n 7 )). This provides the first alternative to Ajtai and Dwork's original 1996 cryptosystem. Our second result is a family of collision resistant hash functions with an improved security guarantee in terms of the unique shortest vector problem. Surprisingly, both results are derived from one theorem that presents two indistinguishable distributions on the segment [0, 1). It seems that this theorem can have further applications; as an example, we use it to solve an open problem in quantum computation related to the dihedral hidden subgroup problem.
We introduce the use of Fourier analysis on lattices as an integral part of a lattice based construction. The tools we develop provide an elegant description of certain Gaussian distributions around lattice points. Our results include two cryptographic constructions which are based on the worst-case hardness of the unique shortest vector problem. The main result is a new public key cryptosystem whose security guarantee is considerably stronger than previous results (O(n1.5) instead of O(n7)). This provides the first alternative to Ajtai and Dwork's original 1996 cryptosystem. Our second result is a collision resistant hash function which, apart from improving the security in terms of the unique shortest vector problem, is also the first example of an analysis which is not based on Ajtai's iterative step. Surprisingly, the two results are derived from the same tool which presents two indistinguishable distributions on the segment [0,1]. It seems that this tool can have further applications and as an example we mention how it can be used to solve an open problem related to quantum computation.
We introduce the use of Fourier analysis on lattices as an integral part of a lattice based construction. The tools we develop provide an elegant description of certain Gaussian distributions around lattice points. Our results include two cryptographic constructions which are based on the worst-case hardness of the unique shortest vector problem. The main result is a new public key cryptosystem whose security guarantee is considerably stronger than previous results (O(n1.5) instead of O(n7)). This provides the first alternative to Ajtai and Dwork's original 1996 cryptosystem. Our second result is a collision resistant hash function which, apart from improving the security in terms of the unique shortest vector problem, is also the first example of an analysis which is not based on Ajtai's iterative step. Surprisingly, the two results are derived from the same tool which presents two indistinguishable distributions on the segment [0,1]. It seems that this tool can have further applications and as an example we mention how it can be used to solve an open problem related to quantum computation.
So far, most ring signature schemes rely on hard number theory problems, such as discrete logarithm, bilinear pairings and so on. Unfortunately, the above underlying number theory problems will be solvable in the post quantum era. Lattice-based cryptography is a hotspot of research recently, due to its implementation simplicity and provable security reductions. When the hash-and-sign signature scheme was constructed based on the hardness of worst-case lattice problems, provably secure lattice-based ring signature schemes were finally constructed. However, the hash-and-sign ring signatures were rather inefficient (with megabytes long signatures). In this paper, we propose an alternative method for constructing lattice-based and identity-based ring signature scheme which does not use the hash-and-sign methodology. In the random oracle model, the proposed signature scheme based on the problem in general lattices is unforgeable and holds anonymity. Compared with the previous instantiations of the hash-and-sign ring signature schemes, the lengths of secret key, public key and signatures in the proposed scheme are much shorter. The signing algorithm is quite simple, with matrix-vector multiplications and rejection samplings.
Digital signatures and key exchange protocols are the two most important public key cryptographic primitives used in the electronic transmission of data. The goal of key exchange is to preserve the secrecy of the communication, while the goal of digital signatures is to guarantee the authenticity of the exchanged messages. Constructions of digital signature schemes based on classical mathematical assumptions appeared shortly following the invention of public key cryptography in the late 1970s. And just like with key exchange, the most efficient variants are based on number-theoretic problems that are believed to be (sub)-exponentially hard for classical machines, but are solved in polynomial time by Shor’s algorithm on a powerful-enough quantum computer. Also, like for key exchange, the most efficient constructions that we believe to be quantum safe are based on the presumed hardness of lattice problems over polynomial rings. One interesting difference between key exchange and digital signatures is that key exchange appears to inherently require that some mathematical problem be computationally hard. Digital signatures, on the other hand, can be generically constructed from any one-way function [1,2]. So even though they certainly fall into the category of public key primitives based on their usage, their existence requires much weaker assumptions. Additionally, the transformation from a one-way function to a digital signature is not too inefficient. For example, the total parameter size (public key + signature) of the SPHINCS+ scheme [3] is around 40 kB. While these sizes are larger, and signing times considerably longer, than those of signatures based on factoring or discrete log, it is still a usable scheme for many applications. And being only based on symmetric assumptions (e.g. one wayness and collision resistance of cryptographic hash functions), its security is very attractive. In order to be considered an interesting alternative to the above-mentioned signature, a scheme based on a mathematical assumption would need to have significant performance advantages. Schemes based on factoring and the discrete logarithm problem were significantly shorter and faster, and so the generic approach lay dormant for over four decades. The new quantum-safe schemes will need to have similar performance advantages if they are to be used in lieu of this safe approach. Below, we describe two techniques for constructing lattice-based digital signatures with output sizes being just a few kilobytes. On a very high level, lattice-based signature constructions follow the two known approaches for constructing classical signatures. In the first approach, the signer outputs a function f and an image y = f(x) as his public key and keeps x as his secret key. To sign a message μ, he gives a non-interactive zero-knowledge proof that he knows an x satisfying y = f(x), using the message μ to create the ‘challenge’ H(μ) for the proof (where H is a public function that maps μ to something ‘random looking’). If the function f is one way then the verifier should be convinced that the proof could have only been created by the entity who knows x. A classic example of this type of scheme is the Schnorr signature scheme [4] based on the hardness of the discrete logarithm problem. The second approach is to create a function f together with a trapdoor f−1, output f as the public key and keep f−1 as the secret key. A message μ is signed by using the secret trapdoor to create a pre-image x such that f(x) = H(μ). Again, if the function f is one way then only someone in possession of a trapdoor should be able to invert it. An example of such a construction based on a ‘factoring-like’ assumption is the RSA signature scheme [5]. The high-level ideas for lattice-based signatures follow the above blueprints, but the technical details are significantly more involved. The main reason for the complications is the different algebraic structure of the hard one-way function underlying lattice cryptography. While the domain of the function in discrete log and RSA-based one-way functions are groups, the domains in lattice-based signatures are sets that are not closed under any operation—in particular, they are elements in a group that have small norms. This crucial small norm requirement precludes us from using uniformly random masking as in Schnorr signatures or having a trapdoor for a bijective one-way function as in RSA signatures. These barriers have, nevertheless, been overcome and the resulting digital signatures are quite practical. In 2017, the US National Institute of Standards and Technology (NIST) began a ‘competition’ for a quantum-safe key exchange and digital signatures standard. At the time of this writing, this process is in the third round and there are two lattice-based signatures remaining—each following one of the above high-level designs. The CRYSTALS-Dilithium [6] scheme follows the Schnorr framework, but adds a crucial rejection-sampling step to keep the size of the coefficients small. The FALCON scheme [7] utilizes a randomized trapdoor sampling technique that uses a secret trapdoor for f−1 to produce random pre-images from a particular distribution. Because there is no longer a bijection, it is crucial to also have the property that the distribution of the outputted pre-images does not leak information about the trapdoor. Both schemes are relatively fast and their parameters (public key + signature size) are the shortest of all quantum-safe signature schemes. While both schemes are based on lattices, they have rather different characteristics. FALCON has very short parameters (see Table 1), but entails a rather complicated procedure for signature generation. In particular, it uses (an optimized version of) the GPV sampler [8], which requires floating-point arithmetic with approximately 64 bits of precision. Requiring such high precision means that subtle implementation errors may not get detected even with rigorous testing. Dilithium, on the other hand, has larger parameters but a very simple implementation where all the sampling in the signing is done in a power-of-2 range; it is thus much less prone to implementation errors. It is quite possible that in the future both schemes will be used for different applications. Approximate parameter sizes (in bytes) for the CRYSTALS-Dilithium and FALCON digital signature schemes at approximately 128-bit security levels. Approximate parameter sizes (in bytes) for the CRYSTALS-Dilithium and FALCON digital signature schemes at approximately 128-bit security levels. Conflict of interest statement. None declared.