New lattice based cryptographic constructions

By Oded Regev. 2003

338 citations recorded by the source corpus.

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.

Subfields: Artificial Intelligence, Computational Theory and Mathematics

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Computational Theory and Mathematics

Citations in the corpus

XPIR : Private Information Retrieval for Everyone (2016, methodology): “A noteworthy exception to this list of schemes is the cPIR scheme of Gasarch and Yerukhimovich [23] which relies on a lattice-based standard encryption scheme [24].”
On the Computational Practicality of Private Information Retrieval (2006, methodology): “In promising ongoing work [33, 34] a method replacing modular multiplication with modular addition (based on novel security results [66, 67]), has been proposed.”
On lattices, learning with errors, random linear codes, and cryptography (2009, methodology): “Our proof is based on the Fourier transform of Gaussian measures, a technique that was developed in previous papers [36, 29, 1].”
Worst-case to average-case reductions based on Gaussian measures (2004, methodology): “2 The main result of [17] is a lattice based encryption scheme.”
Lossy trapdoor functions and their applications (2008, methodology): “On the other hand, when working with lattice-based cryptosystems [1, 36, 37], many additional technical difficulties arise.”
Predicting Lattice Reduction (2008, background): “There are cryptosystems [3,34] based on the worst-case hardness of Unique-SVP with polynomial gap: n for [34] and n(7) for [3].”
Fully Homomorphic Encryption over the Integers (2010, background): “It is left to analyze the probability (over B’s choice of public key) with which the procedure Learn-LSB(z,pk) from above is indeed such a reliable oracle.”
Trapdoors for hard lattices and new cryptographic constructions (2008, methodology): “” Until very recently, the known constructions of such primitives were limited mainly to one-way and collision-resistant hash functions [3, 27, 17, 37, 40] and public-key encryption [5, 51, 52].”
CRYSTALS - Kyber: A CCA-Secure Module-Lattice-Based KEM (2017, methodology): “This scheme was later simplified and improved upon by Regev in [65, 66].”
Efficient Collision-Resistant Hashing from Worst-Case Assumptions on Cyclic Lattices (2006, background): “Public-key cryptosystems [12, 3, 20, 21] soon followed, based on presumably stronger worst-case assumptions.”
Fully Homomorphic Encryption without Modulus Switching from Classical GapSVP (2012, methodology): “After L levels of multiplication, the noise will grow from B/q to ( B/q ) · p ( n ) L , which means that we only need to use Interestingly, the idea of working modulo 1 goes back to the early works of Ajtai and Dwork [AD97], and Regev [Reg03], and to the ﬁrst formulation of LWE [Reg05].”
Better Key Sizes (and Attacks) for LWE-Based Encryption (2011, methodology): “(Our attack also does not seem immediately applicable to other lattice problems, such as the unique shortest vector problem, that have been used for public-key encryption [3, 32 , 4].) Therefore, we believe that our analysis gives a more accurate assessment of LWE ’s concrete hardness than estimate”
Lattice-Based Cryptography (2006, methodology): “Several improvements were given in subsequent works [29, 30].”
On lattices, learning with errors, random linear codes, and cryptography (2005, methodology): “REFERENCES [1] D. Aharonov and O. Regev.”
Classical hardness of learning with errors (2013, methodology): “It is also essentially equivalent to the Ajtai-Dwork-type [4] cryptosystem in [42], as follows from simple reductions similar to the one in the appendix of [45].”
Lattice-based FHE as secure as PKE (2014, methodology): “…procedure of [7] to obtain our ﬁnal FHE scheme that is secure under the hardness of DLWE n,q,α with α ≤ 1 / (cid:101) O κ ( n (cid:15) · n log( q )) which is weakest LWE hardness assumption that underlies the (non-homomorphic) lattice-based public key encryption schemes [1, 17, 18, 16, 6].”
Fiat-Shamir with Aborts: Applications to Lattice and Factoring-Based Signatures (2009, background): “required Õ(n(2)) time and space [2,24], and in public-key cryptosystems, the keys were on the order of megabytes [3,33,34,28] (also see [25] for concrete parameter proposals for the scheme in [34]).”
Multi-bit Cryptosystems Based on Lattice Problems (2006, methodology): “We can sample values according to this distribution by using samples from Φα, as shown in [34]: (1) We samplex ∈ {0, .”