Discrete Gaussian Sampling
Sample lattice vectors according to a discrete Gaussian.
Classical · q-ary supplied basis · online
Shifted DGS over integral q-ary lattices with integral shift
Results
| # | PUBLICATION / AUTHORS | DATE | TIME BOUND | SPACE BOUND | EVIDENCE |
|---|---|---|---|---|---|
| — | An Efficient and Parallel Gaussian Sampler for LatticesCrypto 2010SourceBibTeX / detailsclassical provable worst case q-ary trapdoor offline online parallel | 2010 | O(n2) integer operations plus n randomized-rounding calls online | O(n2 log q) matrix bits plus O(n log q) bits per fresh perturbation | PublishedSource checked |
Comparison definition & assumptions
- Regime
- Shifted DGS over integral q-ary lattices with integral shift
- Computation
- Classical
- Rigor
- Provable
- Instances
- Worst case
- Cost scale
- Online integer operations
- Parameter
- n
- Description
- Optimized offline/online Gaussian sampling for q Z^n contained in L contained in Z^n.
- Comparison rules
- A supplied basis and q are required; the shift is integral. Retain the rounding calls and width condition. Precomputed perturbation vectors must be refreshed between outputs.
- Tags
- q-ary, trapdoor, offline online