6 problems

Quantum closest-vector approximation conjecture. There is no polynomial time quantum algorithm which can approximate the closest vector problem within a polynomial factor.

Let $L$ be a lattice and let its flatness factor be denoted by $\mathcal{E}_L(\sigma)$. Say that a lattice is stable when it satisfies the stability condition used in the source. S…

Shortest vector problem NP-hardness conjecture. The shortest vector problem is $\mathcal{NP}$-hard.

Let CLWE denote learning with errors based on cyclic algebras, and let RLWE denote ring learning with errors. The CLWE construction uses the non-commutative multiplication of a cyc…

GapSVP hardness conjecture. No polynomial-time algorithm exists for ${\mathsf{GapSVP}}_{\mathrm{poly}(n_t)}$ in dimension $n_t$. Consequently, under this conjecture and the hardnes…

Let $n_t$ be the number of transmit antennas, and let $\mathsf{GapSVP}_{\mathrm{poly}(n_t)}$ denote the approximate shortest vector problem on lattices of dimension $n_t$ with appr…