Shortest Vector Problem
Find a shortest nonzero lattice vector.
Ideal lattices · heuristic
Exact Euclidean SVP in cyclotomic ideal lattices
Results
| # | PUBLICATION / AUTHORS | DATE | TIME BOUND | SPACE BOUND | EVIDENCE |
|---|---|---|---|---|---|
| 1 | Efficient (ideal) lattice sieving using cross-polytope LSHAfricacrypt 2016SourceBibTeX / detailsSVP classical heuristic structured lattices ideal lattices cyclotomic LSH | 24 Aug 2015 | 20.2972 n + o(n) | — | PublishedSource checked |
Comparison definition & assumptions
- Regime
- Exact Euclidean SVP in cyclotomic ideal lattices
- Computation
- Classical
- Rigor
- Heuristic
- Instances
- Ideal lattices
- Cost scale
- 2^{c n + o(n)}
- Parameter
- n
- Description
- Structured-lattice sieve improvements, with polynomial and exponential gains kept separate.
- Comparison rules
- State the ideal/ring family and norm. A linear factor gained from rotational symmetry does not by itself change the leading n-normalized exponent. Do not claim a lower exponent merely from a polynomial speedup. These bounds still use sieve heuristics.
- Tags
- SVP, classical, heuristic, structured lattices, ideal lattices, cyclotomic, LSH