Trapdoors for Hard Lattices and New Cryptographic Constructions

Craig Gentry · Chris Peikert · Vinod Vaikuntanathan

STOC 2008

Time bound

Probabilistic polynomial time

Space bound

Polynomial space (polynomial-time algorithm)

Source / version date

25 Aug 2008

Comparison variant

Classical · supplied basis · Gram–Schmidt width

Cost scale

Polynomial time

Gaussian-width requirement

s >= ||B_tilde|| omega(sqrt(log n)); ||B_tilde||=max_i ||b_tilde_i||

Basis contract

Any supplied lattice basis; obtaining a short basis is excluded

Output

One sample from a distribution close to D_{L,s,c}, arbitrary center c

Distribution error

Statistical closeness; the proof makes it negligible with the stated superlogarithmic margin

Cost model

Probabilistic polynomial time, sequential randomized nearest plane

Assumptions and source notes

The published paper title is retained. The checked full version adds the heading “How to Use a Short Basis”. The November 2007 preliminary manuscript only states a longest-basis-vector width, so the Gram–Schmidt bound is not backdated to 2007.

Source location

Theorem 4.1, printed p. 14; §4
Version: Full author version dated 25 August 2008; STOC 2008 publication

Primary source ↗

@inproceedings{gentry-peikert-vaikuntanathan-2008,
  author = {Craig Gentry and Chris Peikert and Vinod Vaikuntanathan},
  title = {{Trapdoors for Hard Lattices and New Cryptographic Constructions}},
  booktitle = {Proceedings of the Fortieth Annual ACM Symposium on Theory of Computing (STOC 2008)},
  year = {2008},
  pages = {197--206},
  doi = {10.1145/1374376.1374407},
  url = {https://doi.org/10.1145/1374376.1374407},
  cr_date = {2008-05-31},
  cr_status = {published},
  cr_venue = {Proceedings of the Fortieth Annual ACM Symposium on Theory of Computing (STOC 2008)},
  cr_author_ids = {craig-gentry; chris-peikert; vinod-vaikuntanathan}
}