6.876J (Fall 2017)
Advanced Topics in Cryptography: Lattices
Open Problems
Mathematics of Lattices
(Added 9/9/2015) Find an explicitly constructible family of lattices $L =\{L_n\}_{n \in \naturals}$ for which there is a constant $c > 0$ such that for every large enough $n$, $\lambda_1(L_n) >= c \cdot \sqrt{n} \cdot \mathsf{det}(L)^{1/n}$.
By explicitly constructibe, I mean that there should be an algorithm that, on input $n$, runs in time $\mathsf{poly}(n)$ and outputs a basis of $L_n$.
Algorithms and Complexity
(Added 9/23/2015) Show a rank-preserving, deterministic, Karp reduction from $\mathsf{SVP}_{\gamma}$ to $\mathsf{CVP}_{\gamma}$ for any $\gamma$.
(What's known: there is a rank-preserving deterministic, Cook reduction shown in class -- that is, the SVP algorithm makes many queries to the CVP oracle. there is also a rank-preserving, randomized, Karp reduction which we did not see in class)
(Added 9/23/2015) Show a reduction from (search) $\mathsf{SVP}_{\gamma'}$ to $\mathsf{gapSVP}_{\gamma}$ for $\gamma', \gamma > 1$, and similarly for CVP.
(What's known: we stated -- but did not prove -- in class that there is such a reduction with $\gamma' = \gamma = 1$.
Also, since gapSVP_{\gamma} is NP-hard* for $\gamma = 2^{(\log n)^{1-\epsilon}}$ for arbitrary constants \epsilon, we know such a reduction* for these values of \gamma. So, really, the question is for factors \gamma = poly(n)).
Here, * refers to the fact that these NP-hardness reductions run in super-polynomial time.
(Added 9/15/2015) Show that CVP in the $\ell_2$ norm is SETH-hard. That is, there is are universal constants $c, c'$ such that if there is a $2^{cn}$-time algorithm for CVP in the $\ell_2$ norm for $n$-dimensional lattices, then there is a $2^{c'n}$-time algorithm for SAT on n variables.
Your goal is to make $c$ as large as possible and $c'$ as small as possible (This will give you a stronger theorem). Bonus points if you can make $c$ and $c'$ approximately equal.
Update (5/30/2017): See the paper of Bennett, Golovnev and Stephens-Davidowitz which shows the statement for all odd norms. The problem as stated above remains open.
(Added 9/15/2015) Show that SVP in the $\ell_2$ norm is SETH-hard. The paper of Stephens-Davidowitz et al. mentioned above solves this problem for the $\ell_\infty$ norm. All other norms remains open.
(Added 8/26/2017) Show ETH/SETH-hardness for approximation of lattice problems. This is open for both CVP and SVP for essentially any non-trivial approximation factor.
One possibility is to start from the so-called gap-SETH assumption (see Dinur's recent work).
(Added 8/26/2017) The best algorithms known for SVP and CVP in the $\ell_2$ norm run in time $2^{n+o(n)}$ and $2^{n+o(n)}$ space. This suggests many open questions:
(a) can we make the space requirement less than $2^n$ (this is important in practice as well as theory)? $2^{n/2}$ space seems achievable;
(b) can we make the algorithm deterministic? A potential idea is to use hardness/randomness tradeoffs. That is, show that if the lattice problem is hard for EXP, we can design an appropriate pseudorandom generator and derandomize the $2^n$-time randomized algorithm. If not, there is a faster algorithm, period. Win-win! We note that the best deterministic algorithm (for CVP and SVP) is the Voronoi cell algorithm of Micciancio and Voulgaris which runs in time $2^{2n}$ and space $2^n$.
(c) how about algorithms for norms other than $\ell_2$? here, the best known is still $n^n$.
(Added 8/26/2017) Find complexity-theoretic implications of approximating lattice problems to within $poly(n)$ factor. (Recall that these are the relevant parameter settings for cryptography).
A possibility is to show that such an approximation algorithm implies a way to factor numbers faster than currently known; however, we warn that this is a notorious open problem that has stumped researchers for a long time.
(Added 8/26/2017)
The current status of closest vector approximation is similar to shortest vectors except that we know real NP-hardness to within $2^{(log n)^{1-eps}}$ factor (see this paper for the latest result). This is not known for SVP. Can you show it?
(Added 8/26/2017)
Relatedly, hardness of CVP within $n^{\epsilon}$ factors (for some unspecified constant $\epsilon$) is known under the so-called projection games conjecture, but nothing similar is known for SVP. Can you show it?
(Added 8/26/2017)
There are other interesting lattice problems whose hardness landscape is not well known. For example, the problem of finding a Minkowski-short vector, defined as a vector whose length is below the Minkowski bound. Such a vector exists by the Minkowski theorem, so the problem is in total NP (TFNP). It is in fact even in the class PPP (polynomial pigeonhole principle), a subclass of TFNP.
The question is: can you show that Minkowski is hard for PPP?
Cryptography, Worst-case to Average-case Reductions, and More
(Added 8/26/2017)
In the $k$-SUM problem, you are given $n$ numbers mod $p$ (think of $p$ as a $O(\log n)$-bit number) and are asked to find a subset of size at most $k$ whose sum is zero mod $p$.
I think of the $k$-SUM problem as one of finding a short vector in a lattice. Inspired by Ajtai's worst-case to average-case reduction for lattice problems, I ask if you can show a worst-case to average-case reduction for the $k$-SUM problem.
(Added 8/26/2017)
Recall the short integer solutions (SIS) problem defined in class. We showed that solving the SIS problem modulo $p$ is as hard as worst-case lattice problems as long as $p$ is large.
The general consensus is that SIS modulo small $p$ is hard as well, the simplest setting being $p=3$ (when $p$ is hard, SIS as stated in class, namely, given a matrix A, find a 0-1 vector x such that $Ax = 0 \pmod{p}$ is easy!) Can you find complexity-theoretic evidence for hardness of SIS mod 3? how about mod 4? failing which, find better algorithms.
(Added 8/26/2017)
Show the security of the k-LWE problem when $k$ is close to the rank $m$. I expect that $k = m - O(n \log q)$ should be achievable.