Bonsai Trees, or How to Delegate a Lattice Basis

By David Cash, Dennis Hofheinz, Eike Kiltz, Chris Peikert. Journal of Cryptology, 2010

949 citations recorded by the source corpus.

Subfields: Artificial Intelligence, Computer Vision and Pattern Recognition

View Paper: https://www.semanticscholar.org/paper/82e0fb98fe9b25b85b6d623a6ad7e1c0ef42e805

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 Computer Vision and Pattern Recognition

Citations in the corpus

Witness encryption and its applications (2013, neutral): “(LWE) parameters [6, 1], or RSA modulus [8].”
Fully Key-Homomorphic Encryption, Arithmetic Circuit ABE and Compact Garbled Circuits (2014, methodology): “Before giving the complete proof we ﬁrst brieﬂy sketch the main proof idea which hinges on the properties of algorithms ( Eval pk , Eval ct , Eval sim ) and also employs ideas from [CHKP10, ABB10].”
Lattice Signatures Without Trapdoors (2012, methodology): “Subsequently, lattice-based signature schemes without random oracles were also constructed [11, 8], but they are all much less efficient in practice than their random oracle-using counterparts.”
An Efficient and Parallel Gaussian Sampler for Lattices (2010, background): “1 These include digital signatures (both 'tree-based' [LM08] and 'hash-and-sign' [GPV08, CHKP10]), identity-based encryption [GPV08] and hierarchical IBE [CHKP10, ABB10], noninteractive zero knowledge [PV08], and even a fully homomorphic cryptosystem [Gen09].”
Unbounded HIBE and Attribute-Based Encryption (2011, methodology): “In the random oracle model, additional schemes were provided by Boneh, Gentry, and Hamburg [13] under the quadratic residuosity assumption and by Gentry, Peikert, and Vaikuntanathan [25] under lattice-based 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”
Efficient Fully Homomorphic Encryption from (Standard) LWE (2011, neutral): “, [33], [19], [4], [5], [10], [1] and many others).”
New Proof Methods for Attribute-Based Encryption: Achieving Full Security through Selective Techniques (2012, background): “Subsequent constructions of IBE and HIBE can be found in [11] [6] [7] [8] [15] [16] [24] [1] [12] [26].”
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].”
Identity-Based Encryption with Outsourced Revocation in Cloud Computing (2015, background): “Recently, there have been multiple lattice-based constructions for IBE systems [20]–[22].”
Frodo: Take off the Ring! Practical, Quantum-Secure Key Exchange from LWE (2016, background): “Constructions based on LWE have led to a large variety of public-key cryptosystems [38, 52, 31, 18, 3, 2, 17].”
Lattice Basis Delegation in Fixed Dimension and Shorter-Ciphertext Hierarchical IBE (2010, methodology): “Table 1 shows that the construction is only competitive with existing HIBEs [CHKP10,ABB10] in applications where k < (cid:96) (such as [CHK07] where k = 1).”
On Ideal Lattices and Learning with Errors over Rings (2010, methodology): “This scheme and its security proof are a direct translation of the ‘dual’ scheme from [13] based on the standard LWE problem, and similarly direct adaptations are possible for most other LWE-based schemes, including Regev’s original ‘primal’ cryptosystem [31], Peikert’s CCA-secure cryptosystem [26],”
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].”
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.”
Attribute-based encryption for circuits (2013, methodology): “In this section, we present an instantiation of TOR from LWE, building upon ideas in [1, 2, 16, 23].”
Functional Encryption: Definitions and Challenges (2011, background): “Recently, there have been multiple lattice-based constructions of IBE systems [GPV08, CHKP10 , ABB10].”