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

Journal of the ACM

New lattice-based cryptographic constructions

Oded Regev

Published Nov 1, 2004• 296 citations
Publisher

Abstract

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.

DOI
10.1145/1039488.1039490

Related papers

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•16 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(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 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, both results are derived from one theorem which presents two indistinguishable distributions on the segment $[0,1)$. It seems that this theorem can have further applications and as an example we mention how it can be used to solve an open problem related to quantum computation.

arXiv:cs/0309051•Sep 28, 2003•0 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•84 citations

Public-Key Cryptosystems from the Worst-Case Shortest Vector Problem

Chris Peikert

We construct public-key cryptosystems that are secure assuming the *worst-case* hardness of approximating the shortest vector problem on lattices. Prior cryptosystems with worst-case connections (e.g., the Ajtai-Dwork system) were based either on a *special case* of the shortest vector problem, or on the conjectured hardness of lattice problems for *quantum* algorithms. Our main technical innovation is a reduction from certain variants of the shortest vector problem to corresponding versions of the "learning with errors" (LWE) problem; previously, only a quantum reduction of this kind was known. In addition, we construct new cryptosystems based on LWE, including a very natural chosen ciphertext-secure system that has a much simpler description and tighter underlying worst-case approximation factor than prior constructions. (Duration: 30 minutes, on or before Wednesday.)

Dagstuhl Seminar Proceedings•Jan 1, 2009•192 citations

Trapdoors for hard lattices and new cryptographic constructions

Craig Gentry, Chris Peikert, Vinod Vaikuntanathan

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.

ACM Symposium on Theory of Computing (STOC)•May 17, 2008•2,498 citations

Public-key cryptosystems from the worst-case shortest vector problem

Chris Peikert

We construct public-key cryptosystems that are secure assuming theworst-case hardness of approximating the minimum distance on n-dimensional lattices to within small Poly(n) factors. Prior cryptosystems with worst-case connections were based either on the shortest vector problem for a special class of lattices (Ajtai and Dwork, STOC 1997; Regev, J. ACM 2004), or on the conjectured hardness of lattice problems for quantum algorithms (Regev, STOC 2005). Our main technical innovation is a reduction from variants of the shortest vector problem to corresponding versions of the "learning with errors" (LWE) problem; previously, only a quantum reduction of this kind was known. As an additional contribution, we construct a natural chosen ciphertext-secure cryptosystem having a much simpler description and tighter underlying worst-case approximation factor than prior schemes.

ACM Symposium on Theory of Computing (STOC)•May 31, 2009•822 citations
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)O(n^{1.5})O(n1.5) instead of O(n7)O(n^7)O(n7)). This provides the first alternative to Ajtai and Dwork's original 1996 cryptosystem. Our second result is a family of collision resistant hash functions 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, both results are derived from one theorem which presents two indistinguishable distributions on the segment [0,1)[0,1)[0,1). It seems that this theorem 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.
We construct public-key cryptosystems that are secure assuming the *worst-case* hardness of approximating the shortest vector problem on lattices. Prior cryptosystems with worst-case connections (e.g., the Ajtai-Dwork system) were based either on a *special case* of the shortest vector problem, or on the conjectured hardness of lattice problems for *quantum* algorithms. Our main technical innovation is a reduction from certain variants of the shortest vector problem to corresponding versions of the "learning with errors" (LWE) problem; previously, only a quantum reduction of this kind was known. In addition, we construct new cryptosystems based on LWE, including a very natural chosen ciphertext-secure system that has a much simpler description and tighter underlying worst-case approximation factor than prior constructions. (Duration: 30 minutes, on or before Wednesday.)
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.
We construct public-key cryptosystems that are secure assuming theworst-case hardness of approximating the minimum distance on n-dimensional lattices to within small Poly(n) factors. Prior cryptosystems with worst-case connections were based either on the shortest vector problem for a special class of lattices (Ajtai and Dwork, STOC 1997; Regev, J. ACM 2004), or on the conjectured hardness of lattice problems for quantum algorithms (Regev, STOC 2005). Our main technical innovation is a reduction from variants of the shortest vector problem to corresponding versions of the "learning with errors" (LWE) problem; previously, only a quantum reduction of this kind was known. As an additional contribution, we construct a natural chosen ciphertext-secure cryptosystem having a much simpler description and tighter underlying worst-case approximation factor than prior schemes.