[Ajt96] Generating Hard Instances of Lattice Problems

Authors: Miklós Ajtai | Venue: STOC 1996 | Source

Abstract

We give a random class of lattices in ${\mathbb{Z}}^n$ so that, if there is a probabilistic polynomial time algorithm which finds a short vector in a random lattice from this class with noticeable probability, then there is also a probabilistic polynomial time algorithm which solves several classical lattice problems (including the shortest vector problem) in the worst case. We also show that the same random class of lattices can be used to construct a one-way function and a collision-free hash function family.

BibTeX

Copy

@Inproceedings{STOC:Ajtai96,
  author = {Mikl{\'o}s Ajtai},
  title = {Generating Hard Instances of Lattice Problems (Extended Abstract)},
  pages = {99--108},
  booktitle = {28th Annual {ACM} Symposium on Theory of Computing},
  address = {Philadephia, PA, USA},
  month = {may~22--24},
  publisher = {{ACM} Press},
  year = {1996},
  doi = {10.1145/237814.237838},
}