Discrete Gaussian Sampling
Sample lattice vectors according to a discrete Gaussian.
Classical · supplied basis · parallel online
Shifted DGS with width controlled by the basis operator norm
Results
| # | PUBLICATION / AUTHORS | DATE | TIME BOUND | SPACE BOUND | EVIDENCE |
|---|---|---|---|---|---|
| — | An Efficient and Parallel Gaussian Sampler for LatticesCrypto 2010SourceBibTeX / detailsclassical provable worst case trapdoor parallel offline online shifted DGS | 2010 | O(n2) online real operations; O(n2/P) per processor | Offline matrices and fresh perturbation vector | PublishedSource checked |
Comparison definition & assumptions
- Regime
- Shifted DGS with width controlled by the basis operator norm
- Computation
- Classical
- Rigor
- Provable
- Instances
- Worst case
- Cost scale
- Online arithmetic operations
- Parameter
- n
- Description
- Offline/online sampling with explicit parallel online cost.
- Comparison rules
- Record covariance and basis assumptions; exclude offline preparation only when explicit. Real-arithmetic counts are not bit-operation exponents. Operator-norm and Gram–Schmidt width conditions are different contracts.
- Tags
- trapdoor, offline online, parallel, shifted