Trapdoors for hard lattices and new cryptographic constructions

By Craig Gentry, Chris Peikert, Vinod Vaikuntanathan. 2008

2,665 citations recorded by the source corpus.

Subfields: Artificial Intelligence, Computational Theory and Mathematics, Computer Networks and Communications

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

In Computer Networks and Communications

Citations in the corpus

Pure Differentially Private Summation from Anonymous Messages (2020, methodology): “(For reference, please refer to [GPV08, Lemma 2.6] which states a more general version of the statement that also works for higher-dimensional lattices.)”
Dual System Encryption: Realizing Fully Secure IBE and HIBE under Simple Assumptions (2009, background): “Other Related Work We note that there are remarkable IBE systems of Cocks [13] and Boneh, Gentry, and Hamburg [6] based on the quadratic residuosity assumption and Gentry, Peikert, and Vaikuntanathan [17] based on lattice assumptions.”
A Toolkit for Ring-LWE Cryptography (2013, methodology): “Such a lemma is needed for porting many applications of standard SIS and LWE to the ring setting, including SIS-based signature schemes [19, 10, 7, 28], the “primal” [31] and “dual” [19] LWE cryptosystems, chosen ciphertext-secure encryption schemes [29, 28], and (hierarchical) identity-based encryp”
Identity-Based Encryption with Outsourced Revocation in Cloud Computing (2015, background): “Recently, there have been multiple lattice-based constructions for IBE systems [20]–[22].”
Lattice-Based Cryptography (2006, methodology): “As most schemes based on general lattices, the signatures of [17] have quadratic complexity both in terms of key size and signing and verification times.”
Efficient Fully Homomorphic Encryption from (Standard) LWE (2011, neutral): “, [33], [19], [4], [5], [10], [1] and many others).”
Candidate Indistinguishability Obfuscation and Functional Encryption for all Circuits (2013, methodology): “(We refer the reader to [GGH13a] for details on a [GPV08] based more sophisticated sampling procedure.)”
Hardness of SIS and LWE with Small Parameters (2013, methodology): “Our new proof combines ideas from [19, 12] and Proposition 3.”
Efficient Public Key Encryption Based on Ideal Lattices (2009, methodology): “[9] give a construction of a trapdoor signature (in the random oracle model) from any family of collision-resistant preimage sampleable functions (PSFs).”
An Efficient and Parallel Gaussian Sampler for Lattices (2010, methodology): “The cornerstone of many of these schemes (particularly, but not exclusive to, those that ‘answer queries’) is the polynomial-time algorithm of [8] that samples from a so-called discrete Gaussian probability distribution over a lattice Λ.”
Discrete Gaussian Leftover Hash Lemma over Infinite Domains (2013, methodology): “Discrete Gaussian samplers have been studied by [6] (who use an algorithm by [7]) and [13].”
Functional Encryption: Definitions and Challenges (2011, background): “Recently, there have been multiple lattice-based constructions of IBE systems [ GPV08 , CHKP10, ABB10].”
A Simple Provably Secure Key Exchange Scheme Based on the Learning with Errors Problem (2012, background): “Many lattice-based primitives based on LWE have been discovered, such as public-key encryption [25,16,20], (hierarchical) identity-based encryption [16,1,12], functional encryption [3,2,5,17] and fully homomorphic encryption [9,7,6,10].”
On lattices, learning with errors, random linear codes, and cryptography (2005, background): “Third, Gentry, Peikert, and Vaikuntanathan [16] constructed an identitybased encryption (IBE) scheme.”
Key Homomorphic PRFs and Their Applications (2013, background): “We need the following two facts [4, 21]: There is an efficient randomized algorithm TrapGen(1, k, q) that given integers n, q ≥ 2 and k ≥ 6n log q, outputs a matrix M ∈ Zn×k q and a ‘trapdoor’ TM ∈ Zk×k such that M is negl(n)-close to uniform.”
Predicting Lattice Reduction (2008, background): “This sheds new lights on the practical hardness of the main lattice problems, and allows to compare the various computational assumptions (Unique-SVP, Approximate-SVP) used in theoretical lattice-based cryptography [33,11,35,34,3].”