Discrete Gaussian Sampling
Sample lattice vectors according to a discrete Gaussian.
Classical · supplied basis · Gram–Schmidt width
Shifted discrete Gaussian sampling above a supplied-basis width
Results
| # | PUBLICATION / AUTHORS | DATE | TIME BOUND | SPACE BOUND | EVIDENCE |
|---|---|---|---|---|---|
| — | Trapdoors for Hard Lattices and New Cryptographic ConstructionsSTOC 2008SourceBibTeX / detailsclassical provable worst case trapdoor basis relative shifted DGS | 25 Aug 2008 | Probabilistic polynomial time | Polynomial space (polynomial-time algorithm) | PublishedSource checked |
Comparison definition & assumptions
- Regime
- Shifted discrete Gaussian sampling above a supplied-basis width
- Computation
- Classical
- Rigor
- Provable
- Instances
- Worst case
- Cost scale
- Polynomial time
- Parameter
- n
- Description
- Polynomial-time sampling with width controlled by the longest Gram–Schmidt vector.
- Comparison rules
- The basis is part of the input. Require s >= ||B_tilde|| omega(sqrt(log n)); the cost of obtaining a short basis is excluded. This is not arbitrary-width DGS from an arbitrary lattice description.
- Tags
- trapdoor, basis relative, shifted