lattices.bib

@InProceedings{10.1007/978-3-642-13190-5_1,
  author="Lyubashevsky, Vadim and Peikert, Chris and Regev, Oded",
  editor="Gilbert, Henri",
  title="On Ideal Lattices and Learning with Errors over Rings",
  booktitle="Advances in Cryptology -- EUROCRYPT 2010",
  year="2010",
  publisher="Springer Berlin Heidelberg",
  address="Berlin, Heidelberg",
  pages="1--23",
  abstract="The ``learning with errors'' (LWE) problem is to distinguish random linear equations, which have been perturbed by a small amount of noise, from truly uniform ones. The problem has been shown to be as hard as worst-case lattice problems, and in recent years it has served as the foundation for a plethora of cryptographic applications. Unfortunately, these applications are rather inefficient due to an inherent quadratic overhead in the use of LWE. A main open question was whether LWE and its applications could be made truly efficient by exploiting extra algebraic structure, as was done for lattice-based hash functions (and related primitives).",
  isbn="978-3-642-13190-5"
}

@InProceedings{10.1007/978-3-642-38348-9_3,
  author="Lyubashevsky, Vadim and Peikert, Chris and Regev, Oded",
  editor="Johansson, Thomas and Nguyen, Phong Q.",
  title="A Toolkit for Ring-LWE Cryptography",
  booktitle="Advances in Cryptology -- EUROCRYPT 2013",
  year="2013",
  publisher="Springer Berlin Heidelberg",
  address="Berlin, Heidelberg",
  pages="35--54",
  abstract="Recent advances in lattice cryptography, mainly stemming from the development of ring-based primitives such as ring-LWE, have made it possible to design cryptographic schemes whose efficiency is competitive with that of more traditional number-theoretic ones, along with entirely new applications like fully homomorphic encryption. Unfortunately, realizing the full potential of ring-based cryptography has so far been hindered by a lack of practical algorithms and analytical tools for working in this context. As a result, most previous works have focused on very special classes of rings such as power-of-two cyclotomics, which significantly restricts the possible applications.",
  isbn="978-3-642-38348-9"
}

@article{10.1145/1568318.1568324,
  author = {Regev, Oded},
  title = {On Lattices, Learning with Errors, Random Linear Codes, and Cryptography},
  year = {2009},
  issue_date = {September 2009},
  publisher = {Association for Computing Machinery},
  address = {New York, NY, USA},
  volume = {56},
  number = {6},
  issn = {0004-5411},
  url = {https://doi.org/10.1145/1568318.1568324},
  doi = {10.1145/1568318.1568324},
  abstract = {Our main result is a reduction from worst-case lattice problems such as GapSVP and SIVP to a certain learning problem. This learning problem is a natural extension of the “learning from parity with error” problem to higher moduli. It can also be viewed as the problem of decoding from a random linear code. This, we believe, gives a strong indication that these problems are hard. Our reduction, however, is quantum. Hence, an efficient solution to the learning problem implies a quantum algorithm for GapSVP and SIVP. A main open question is whether this reduction can be made classical (i.e., nonquantum).We also present a (classical) public-key cryptosystem whose security is based on the hardness of the learning problem. By the main result, its security is also based on the worst-case quantum hardness of GapSVP and SIVP. The new cryptosystem is much more efficient than previous lattice-based cryptosystems: the public key is of size \~{O}(n2) and encrypting a message increases its size by a factor of \~{O}(n) (in previous cryptosystems these values are \~{O}(n4) and \~{O}(n2), respectively). In fact, under the assumption that all parties share a random bit string of length \~{O}(n2), the size of the public key can be reduced to \~{O}(n).},
  journal = {J. ACM},
  month = {sep},
  articleno = {34},
  numpages = {40},
  keywords = {average-case hardness, Lattice, quantum computation, public key encryption, cryptography}
}

@InProceedings{10.1007/3-540-48329-2_24,
  author="Blum, Avrim and Furst, Merrick and Kearns, Michael and Lipton, Richard J.",
  editor="Stinson, Douglas R.",
  title="Cryptographic Primitives Based on Hard Learning Problems",
  booktitle="Advances in Cryptology --- CRYPTO' 93",
  year="1994",
  publisher="Springer Berlin Heidelberg",
  address="Berlin, Heidelberg",
  pages="278--291",
  abstract="Modern cryptography has had considerable impact on the development of computational learning theory. Virtually every intractability result in Valiant's model [13] (which is representation-independent in the sense that it does not rely on an artificial syntactic restriction on the learning algorithm's hypotheses) has at its heart a cryptographic construction [4, 9, 1, 10]. In this paper, we give results in the reverse direction by showing how to construct several cryptographic primitives based on certain assumptions on the difficulty of learning. In doing so, we develop further a line of thought introduced by Impagliazzo and Levin [6].",
  isbn="978-3-540-48329-8"
}

@inproceedings{10.1145/1536414.1536461,
  author = {Peikert, Chris},
  title = {Public-Key Cryptosystems from the Worst-Case Shortest Vector Problem: Extended Abstract},
  year = {2009},
  isbn = {9781605585062},
  publisher = {Association for Computing Machinery},
  address = {New York, NY, USA},
  url = {https://doi.org/10.1145/1536414.1536461},
  doi = {10.1145/1536414.1536461},
  abstract = {We construct public-key cryptosystems that are secure assuming theworst-case hardness of approximating the minimum distance on n-dimensional lattices to within small Poly(n) factors. Prior cryptosystems with worst-case connections were based either on the shortest vector problem for a special class of lattices (Ajtai and Dwork, STOC 1997; Regev, J. ACM 2004), or on the conjectured hardness of lattice problems for quantum algorithms (Regev, STOC 2005). Our main technical innovation is a reduction from variants of the shortest vector problem to corresponding versions of the "learning with errors" (LWE) problem; previously, only a quantum reduction of this kind was known. As an additional contribution, we construct a natural chosen ciphertext-secure cryptosystem having a much simpler description and tighter underlying worst-case approximation factor than prior schemes.},
  booktitle = {Proceedings of the Forty-First Annual ACM Symposium on Theory of Computing},
  pages = {333–342},
  numpages = {10},
  keywords = {cryptography, lattices},
  location = {Bethesda, MD, USA},
  series = {STOC '09}
}

@inproceedings{10.1145/2488608.2488680,
  author = {Brakerski, Zvika and Langlois, Adeline and Peikert, Chris and Regev, Oded and Stehl\'{e}, Damien},
  title = {Classical Hardness of Learning with Errors},
  year = {2013},
  isbn = {9781450320290},
  publisher = {Association for Computing Machinery},
  address = {New York, NY, USA},
  url = {https://doi.org/10.1145/2488608.2488680},
  doi = {10.1145/2488608.2488680},
  abstract = {We show that the Learning with Errors (LWE) problem is classically at least as hard as standard worst-case lattice problems. Previously this was only known under quantum reductions.Our techniques capture the tradeoff between the dimension and the modulus of LWE instances, leading to a much better understanding of the landscape of the problem. The proof is inspired by techniques from several recent cryptographic constructions, most notably fully homomorphic encryption schemes.},
  booktitle = {Proceedings of the Forty-Fifth Annual ACM Symposium on Theory of Computing},
  pages = {575–584},
  numpages = {10},
  keywords = {learning with errors, lattices},
  location = {Palo Alto, California, USA},
  series = {STOC '13}
}