Trapdoors for Lattices: Simpler, Tighter, Faster, Smaller

By Daniele Micciancio, Chris Peikert. IACR Cryptology ePrint Archive, 2012

1,302 citations recorded by the source corpus.

Subfields: Artificial Intelligence, Computational Theory and Mathematics

View Paper: https://www.semanticscholar.org/paper/988ba838c2a4d601a5af5c06f73ee16bb32395ea

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

Practical Lattice-Based Cryptography: A Signature Scheme for Embedded Systems (2012, positive): “Provably-secure digital signatures were finally constructed in 2008, by Gentry, Peikert, and Vaikuntanathan [13], and, using different techniques, by Lyubashevsky and Micciancio [24].”
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”
Pseudorandom Functions and Lattices (2012, background): “, [35, 31, 4, 26], and [27] for the mildest known requirements on q, which include the case where q is a power of 2).”
Improved Discrete Gaussian and Subgaussian Analysis for Lattice Cryptography (2020, methodology): “The concrete parameters for optimized SIS-and LWE-based trapdoor cryptosystems following [MP12] depend on the largest singular value of a subgaussian random matrix with independent rows, columns, or entries, which serves as the trapdoor.”
Faster Bootstrapping with Polynomial Error (2014, neutral): “, [18] for further details).”
TFHE: Fast Fully Homomorphic Encryption Over the Torus (2019, methodology): “A more correct approach would be to use a truncated distribution (as suggested in [43]) in order to avoid all the negligible amounts appearing in the probability formulas.”
Fully Key-Homomorphic Encryption, Arithmetic Circuit ABE and Compact Garbled Circuits (2014, methodology): “We note that the matrix R f in KeyGen FKHE can alternatively be generated using a sampling method from [MP12].”
Lattice Signatures Without Trapdoors (2012, methodology): “On the practical side, however, the bit-length of our signature and keys (see Figure 2) are approximately two orders of magnitude smaller for the same security level (see [40] and also Figure 2 in [30]).”
Worst-case to average-case reductions for module lattices (2014, methodology): “…of LWE have been shown as hard as Regev’s original LWE: These variants may consist in sampling the secret vector s from the same distribution as the errors [2], in sampling the error vectors from other distributions [25,10] and in relaxing the conditions on the factorisation of the modulus [19, Se.”
Hardness of SIS and LWE with Small Parameters (2013, methodology): “In order to conclude that the LWE function is pseudorandom (under worstcase lattice assumptions) for uniformly random small errors, we combine Theorem 5 with previous hardness results [26,23,7] and search-to-decision reductions [18,19].”
Homomorphic Encryption (2017, background): “Moreover, for many parameter regimes, the search problem of computing ~s can be further reduced to the problem of distinguishing the pair (A,~b) from uniform [8, 81, 71].”
Lattice-based FHE as secure as PKE (2014, background): “The (one-dimensional, integer-coset) discrete Gaussian D − c,r is the discrete distribution supported on Z − c for c ∈ R , whose probability mass function is proportional to ρ r .”
Lattice Signatures and Bimodal Gaussians (2013, background): “Among known provably-secure signature schemes, [11,23], [24,27], the most efficient seems to be that of [24] whose most efficient instantiation has both signature and key size of the order of 9kb [15] for approximately 80 bits of security.”
Compressible FHE with Applications to PIR (2019, methodology): “Many lattice cryptosystems (including GSW [GSW13]) use a rectangular gadget matrix [MP12], G ∈ R n × m q to add redundancy.”