Lossy trapdoor functions and their applications

By Chris Peikert, Brent Waters. SIAM journal on computing (Print), 2008

631 citations recorded by the source corpus.

View Paper: https://www.semanticscholar.org/paper/0695cf9615862cb0a5db9301b7221bfced4f9980

How researchers see this paper

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

Citations in the corpus

Fully homomorphic encryption using ideal lattices (2009, background): “Some additively homomorphic encryption schemes use lattices or linear codes [22, 50 , 27, 36, 37, 4]. ElGamal [20] is multiplicatively homomorphic.”
On the concrete hardness of Learning with Errors (2015, background): “One lattice problem on whose hardness several cryptographic constructions are based is the learning with errors (LWE) problem [65, 67, 69].”
Classical hardness of learning with errors (2013, background): “serving as the basis for a multitude of cryptographic constructions: secure public-key encryption under both chosenplaintext [44, 40, 26] and chosen-ciphertext [41, 37, 33] attacks, oblivious transfer [40], identity-based encryption [18, 15, 1, 2], various forms of leakage-resilient cryptography (e.”
Pseudorandom Functions and Lattices (2012, unknown): “, [35, 33, 15, 14, 13, 1] and many more.”
Faster exponential time algorithms for the shortest vector problem (2010, methodology): “Enumeration algorithms , given a lattice basis B , systematically explore a region of space (centered around the origin) that is guaranteed to contain the shortest lattice vector.”
Lattice-Based Cryptography (2006, background): “In a recent breakthrough, Peikert and Waters [66] showed for the first time how to construct CCA-secure cryptosystems based on a general primitive which they call lossy trapdoor functions.”
On lattices, learning with errors, random linear codes, and cryptography (2009, background): “A much more signiﬁcant improvement is described by Peikert, Vaikuntanathan, and Waters in [34].”
Trapdoors for Lattices: Simpler, Tighter, Faster, Smaller (2012, methodology): “Our method for adding tags to the trapdoor is very similar to a technique for doing the same with the lossy TDF of [PW08], and is identical to the method used in [ABB10a] for constructing compact (H)IBE. Finally, in our preimage sampling algorithm for f A , we use the “convolution” technique from…”
Efficient Public Key Encryption Based on Ideal Lattices (2009, methodology): “Most of the cryptosystems based on general lattices [33,30,31,9,28] rely on the average-case hardness of the Learning With Errors (LWE) problem introduced in [33].”
On Ideal Lattices and Learning with Errors over Rings (2010, background): “The LWE problem has proved to be amazingly versatile for encryption schemes, serving as the basis for secure public-key encryption under both chosen-plaintext [31, 29] and chosen-ciphertext [30, 26] attacks, oblivious transfer [29], identity-based encryption [13, 8, 1], various forms of leakage-resi”
Hardness of SIS and LWE with Small Parameters (2013, methodology): “Lossy functions, introduced in [23], are usually defined in the context of trapdoor function families, where the functions are efficiently invertible with the help of some trapdoor information, and therefore injective (at least with high probability over the choice of the key).”
Fast Cryptographic Primitives and Circular-Secure Encryption Based on Hard Learning Problems (2009, background): “The problem of “learning a linear function with errors” (LWE) has found many interesting cryptographic and complexity-theoretic applications in the last few years (see [32,36,46,37,45,25], to name a few).”
Computational Differential Privacy from Lattice-Based Cryptography (2017, methodology): “…LWE problem where the errors are taken from the discrete Gaussian distribution D ν with parameter ν . p q Variants of lossy codes were ﬁrst used in [29] and since then had applications in diﬀerent hardness reductions, such as the reduction from the LWE problem to the Learning with Rounding problem…”
Better Key Sizes (and Attacks) for LWE-Based Encryption (2011, methodology): “In the realm of encryption alone, for example, we now have public-key cryptosystems [3, 32, 33] with chosen-ciphertext security [ 31 , 28], identity-based encryption [17, 13, 1], and a fully homomorphic cryptosystem [16].”
Simultaneous Hardcore Bits and Cryptography against Memory Attacks (2009, methodology): “Together with the construction of deterministic encryption schemes from lossy trapdoor functions [36] (based on DDH and LWE), this gives us trapdoor functions based on DDH and LWE with many simultaneous hardcore bits.”