Generating Shorter Bases for Hard Random Lattices

By Joël Alwen, Chris Peikert. Theory of Computing Systems, 2009

570 citations recorded by the source corpus.

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

View Paper: https://www.semanticscholar.org/paper/ccef36e8155db9cdc3355729698f159916332c50

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

Trapdoors for Lattices: Simpler, Tighter, Faster, Smaller (2012, methodology): “Our construction also greatly improves the quality s of the trapdoor.”
On Ideal Lattices and Learning with Errors over Rings (2010, background): “cedure of [5] to the ring setting, which was done in [32].”
Homomorphic Signatures for Polynomial Functions (2011, background): “Ideal lattices also appear in the lattice-based public key encryption schemes of Stehle et al. [37] and Lyubashevsky, Peikert, and Regev [26] and in the hash functions of Lyubashevsky and Micciancio [25].”
An Efficient and Parallel Gaussian Sampler for Lattices (2010, methodology): “We show that with a minor modification, one of the algorithms from [4] outputs (with overwhelming probability) a basis B for which s1(B) is only an O( √ log q) factor larger than ‖B̃‖ (which itself is asymptotically optimal, as shown in [4]).”
Lattice Basis Delegation in Fixed Dimension and Shorter-Ciphertext Hierarchical IBE (2010, methodology): “…an arbitrary basis of Λ and a full-rank set S = { s 1 , . . . , s m } in Λ , returns a basis T of Λ satisfying Ajtai [Ajt99] and later Alwen and Peikert [AP09] show how to sample an essentially uniform matrix A ∈ Z n × m q with an associated basis S A of Λ ⊥ q ( A ) with low Gram-Schmidt norm.”
A Toolkit for Ring-LWE Cryptography (2013, unknown): “, [2, 28].”
Efficient Public Key Encryption Based on Ideal Lattices (2009, methodology): “We thank Chris Peikert and Oded Regev for helpful discussions.”
Efficient Lattice (H)IBE in the Standard Model (2010, methodology): “The algorithm uses the basis growth method of Peikert [33, Sec.”
Lattice Signatures Without Trapdoors (2012, methodology): “Regev [39] showed that there is a quantum reduction from approximating SIVP in all lattices to solving random instances of LWE when the errors e i come from the discrete Normal distribution D ψ , and Peikert later showed a classical reduction to LWE from some different lattice problems [35].”
Fully Key-Homomorphic Encryption, Arithmetic Circuit ABE and Compact Garbled Circuits (2014, background): “There are polynomial time algorithms with the properties below: AP09, MP12]) : a randomized algorithm that, when m = Θ( n log q ) , outputs a full-rank matrix A ∈ Z n × m q and basis T A ∈ Z m × m for Λ ⊥ q ( A ) such that A is negl ( n ) -close to uniform and (cid:107) T GS = O ( √ n log q ) ,…”
Simultaneous Hardcore Bits and Cryptography against Memory Attacks (2009, methodology): “We use here a modification of the procedure due to Ajtai [3] (and its recent improvement due to Alwen and Peikert [5]) which generates a pair (A,S) such that A ∈ Zm×nq is statistically close to uniform and S ∈ Zm×m is a short basis for Λ⊥(A).”
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.”
Bonsai Trees, or How to Delegate a Lattice Basis (2010, methodology): “One notable recent work in this area is due to Gentry, Peikert, and Vaikuntanathan [GPV08], who constructed an efﬁcient ‘hash-and-sign’ signature scheme and an identity-based encryption (IBE) scheme.”