Hardness of SIS and LWE with Small Parameters

By Daniele Micciancio, Chris Peikert. Annual International Cryptology Conference, 2013

340 citations recorded by the source corpus.

Subfields: Artificial Intelligence, Computational Theory and Mathematics, Information Systems

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

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 Information Systems

Citations in the corpus

ALITHEIA: Towards Practical Verifiable Graph Processing (2014, background): “The first constraint guarantees that the security reduction from a hard lattices problem to breaking the security of the vector commitment scheme will be successful [25].”
Key Homomorphic PRFs and Their Applications (2013, background): “Similarly, the noise distribution χ can be a simple low-norm distribution [27].”
Speeding up the Number Theoretic Transform for Faster Ideal Lattice-Based Cryptography (2016, methodology): “samples from a Gaussian distribution [25], for example, the number of R-LWE samples per secret can be bounded, or one can use the Kullback-Leibler or Renyi divergences [3].”
Frodo: Take off the Ring! Practical, Quantum-Secure Key Exchange from LWE (2016, background): “LWE is a mature and wellstudied [7, 44, 47, 16] cryptographic primitive that relies only on the worst-case hardness of a shortest vector problem in generic lattices.”
Improved Discrete Gaussian and Subgaussian Analysis for Lattice Cryptography (2020, background): “For any rank-n lattice Λ and ε > 0 , we have Lemma 5 ([MP13, Corollary 2.7]).”
On the concrete hardness of Learning with Errors (2015, background): “On the one hand, theoretical results show that for an LWE instance with a binary secret to be as hard as general LWE in dimension n a dimension of n log q is su cient [18, 57].”
Post-quantum Key Exchange - A New Hope (2016, background): “As for LWE, we do not know any attacks exploiting non-Gaussianity, and several works have established its hardness for other distributions, like uniform in a small interval [30,64], but such proofs do not carry over to Ring-LWE.”
Worst-case to average-case reductions for module lattices (2014, background): “Peikert [24] described an SIVP to SIS reduction that handles all ‘ p norms.”