Simons Institute Wiki

Site Tools

lat22:start

$\def\Z{\mathbb{Z}} \def\BDD{\mathrm{BDD}} \def\SVP{\mathrm{SVP}} \def\SVP{\mathrm{SVP}} \def\CVP{\mathrm{CVP}} \def\SIVP{\mathrm{SIVP}} \def\GapSVP{\mathrm{GapSVP}} \def\GapCVP{\mathrm{GapCVP}} \def\GapSIVP{\mathrm{GapSIVP}} \def\lat{\mathcal{L}} \def\poly{\mathrm{poly}} \def\vec#1{\mathbf{#1}}$

Welcome to the Simons Lattices '22 Wiki Homepage!

Top 10 Problems on Algorithms and Complexity Aspects of Lattices

The following problems were collected on June 6th, 2022 by members of the Lattices Program.

We denote the (exact, search) versions of the Shortest Vector Problem, Closest Vector Problem, and Shortest Independent Vectors Problem as $\SVP$, $\CVP$, and $\SIVP$, respectively. We denote the decision versions of these problems by $\GapSVP$, $\GapCVP$, and $\GapSIVP$, respectively. We denote the Bounded Distance Decoding Problem by $\BDD$. We represent the approximate versions of all of these problems (except $\BDD$) with a preceding approximation factor $\gamma \geq 1$ and the versions in $\ell_p$ norms with a subscript $p$. By default, we consider these problems in the Euclidean ($\ell_2$) norm and on lattices of rank $n$.

In most cases, partial progress or progress on a variant of the questions stated below would still be very interesting. For example, it would still be very interesting to solve Problems 1-3 for $\SVP$ instead of $\CVP$ or for small approximation factors $\gamma > 1$. For simplicity, we have dropped some lower-order terms and dependence on the input length when discussing asymptotic complexity of these problems.

The Problems

1. CVP in $2^{O(n)}$ time and $\poly(n)$ space. Give an algorithm for $\CVP$ running in $2^{O(n)}$ time and using $\poly(n)$ space. The fastest enumeration algorithms take $n^{O(n)}$ time and $\poly(n)$ space [Kan87], while the overall fastest algorithms based on sieving (which solve exact $\SVP$ but only $(1+\varepsilon)$-$\CVP$) [AKS01], Voronoi cell computations [MV10], and discrete Gaussian sampling [ADS15] take $2^{O(n)}$ time and space. Recent work gave a time-space tradeoff between these regimes for $\SVP$ [ACKS21].
2. CVP in $\ell_p$ norms in $2^{O(n)}$ time. Give an algorithm for $\CVP_p$ for all $p \geq 1$ running in $2^{O(n)}$ time. The fastest-known algorithm for general $p$ is again Kannan's algorithm [Kan87]. Recent work gave a constant-factor approximation algorithm for $\CVP_p$ running in $2^{0.802n}$ time [EV20].
3. CVP in $2^{cn}$ time for smaller $c > 0$. Give a (classical or quantum) algorithm for $\CVP$ running in $2^{cn}$ time for constant $c$ satisfying $c < 1$ (classical) or $c \leq 1/2$ (quantum). The fastest classical algorithm for $\CVP$ (and hence $\SVP$) runs in $2^n$ time [ADS15], while the fastest quantum algorithm for $\SVP$ runs in $2^{0.835n}$ time [ACKS21].
4. SVP in rotations of $\Z^n$. Give a polynomial-time algorithm for $\SVP$ on rotations of $\Z^n$. A lattice $\lat$ is said to be a rotation of $\Z^n$'' if it has an orthonormal basis $O$, i.e., a basis $O$ satisfying $O^T O = I_n$. This problem also has an elegant and essentially equivalent formulation in terms of quadratic forms. Namely, given $Q = U^T U$ for unimodular $U$, find $\vec{x} \in \Z^n$ such that $\vec{x}^T Q \vec{x} = 1$. The fastest known algorithm for this problem runs in $2^{0.802n}$ time [BGPS21]. Polynomial-time algorithms are known when the lattice is presented with additional information about its symmetries [LS17].
5. Better polynomial-time approximation for $\SVP$. Give a polynomial-time algorithm for $\gamma$-$\SVP$ with $\gamma = 2^{O(n/\log n)}$. The current best polynomial-time algorithms are based on more general basis-reduction algorithms with block size $k$. These algorithms solve $k^{n/k}$-approximate $\SVP$ given an oracle for exact $\SVP$ in $k$ dimensions. Invoking the oracle with a $2^{O(k)}$-time algorithm for $\SVP$ in lattices of rank $k$ and setting $k = \log n$ leads to a $2^{O(n \log n/ \log \log n)}$-time algorithm for $\SVP$ in lattices of rank $n$.
6. Search-to-decision reductions for approximate lattice problems. Give a dimension-preserving search-to-decision reduction from $\gamma$-$\CVP$ to $\Omega(\gamma)$-$\GapCVP$. Such a reduction is known in the exact case, i.e., when $\gamma' = 1$ [Reg04].
7. Reductions from approximate $\SVP$ to approximate $\SIVP$. Give a dimension-preserving reduction from $\poly(\gamma, n)$-$\SVP$ to $\gamma$-$\SIVP$.
8. Classical search-to-decision reduction for $\SIVP$. Give a classical reduction from $\poly(\gamma, n)$-$\SIVP$ to $\gamma$-$\GapSIVP$. A quantum such reduction is known (with polynomial loss in the approximation factor) by combining three other reductions. Indeed, the worst-case to average-case reduction showing hardness of Learning With Errors gives a quantum reduction from $\SIVP$ to $\BDD$ [Reg09], a classical reduction from $\BDD$ to $\GapSVP$ appears in [LM09], and the transference theorems in [B93] imply a classical reduction from $\GapSVP$ to $\GapSIVP$.
9. Approximate Ideal $\SVP$ in power-of-2 cyclotomics in $\poly(n)$ time. Solve $\gamma$-$\SVP$ on ideal lattices corresponding to rings $\Z[x]/(x^n + 1)$ with $n$ a power of $2$ and $\gamma = \poly(n)$ in $\poly(n)$ time. Such an algorithm is known for "Principal Ideal" $\SVP$ when $\gamma$ is subexponential (more specifically, $\gamma = 2^{\tilde{O}(\sqrt{n})}$) [CDPR16].
10. Solving problems on tensored lattices using oracles for problems on base lattices. Given lattices $\lat_1$ and $\lat_2$ of rank $n$, solve $\CVP$ on $\lat_1 \otimes \lat_2$ efficiently using $\poly(n)$ queries to oracles for solving $\CVP$ on $\lat_1$ and $\lat_2$.

References

• [ACKS21] Aggarwal, Divesh, Yanlin Chen, Rajendra Kumar, and Yixin Shen. Improved Classical and Quantum Algorithms for the Shortest Vector Problem via Bounded Distance Decoding. STACS, 2021.
• [ADS15] Aggarwal, Divesh, Daniel Dadush, and Noah Stephens-Davidowitz. Solving the Closest Vector Problem in $2^n$ Time— The Discrete Gaussian Strikes Again! FOCS, 2015.
• [AKS01] Ajtai, Miklós, Ravi Kumar, and D. Sivakumar. A sieve algorithm for the shortest lattice vector problem. STOC, 2001.
• [B93] Banaszczyk, W. New bounds in some transference theorems in the geometry of numbers. Mathematische Annalen, 1993.
• [BGPS21] Bennett, Huck, Atul Ganju, Pura Peetathawatchai, and Noah Stephens-Davidowitz. Just how hard are rotations of $\Z^n$? Algorithms and cryptography with the simplest lattice. ePrint, 2021.
• [CDPR16] Cramer, Ronald, Léo Ducas, Chris Peikert, and Oded Regev. Recovering Short Generators of Principal Ideals in Cyclotomic Rings. Eurocrypt, 2016.
• [EV20] Eisenbrand, Friedrich and Moritz Venzin. Approximate $\CVP_p$ in time $2^{0.802n}$. ESA, 2020.
• [Kan87] Kannan, Ravi. Minkowski's Convex Body Theorem and Integer Programming. Mathematics of Operations Research, 1987.
• [LS17] Lenstra, H. W., and Alice Silverberg. Journal of Cryptology, 2017.
• [[LM09] Lyubashevsky, Vadim and Daniele Micciancio. On Bounded Distance Decoding, Unique Shortest Vectors, and the Minimum Distance Problem. CRYPTO, 2009.
• [MV10] Micciancio, Daniele and Panagiotis Voulgaris. A Deterministic Single Exponential Time Algorithm for Most Lattice Problems based on Voronoi Cell Computations. SIAM J. Comput., 2013. Preliminary version in STOC 2010.
• [Reg04] Regev, Oded. Some basic complexity results. Course notes from "Lattices in Computer Science," 2004.
• [Reg09] Regev, Oded. On Lattices, Learning with Errors, Random Linear Codes, and Cryptography. Journal of the ACM, 2009. Preliminary version in STOC 2005.