Algorithms for lattice problems in NP \(\cap\) CoNP

1. Given \(\pB\) for \(\pL\), compute \(\perL\), and the finite abelian group rank \(\fgr\), and change the basis to have the generators of that group.
2. Run LLL on \(\pB\). Now \(\frac{\lambda_1(\pL)}{2^{\sqrt{\fgr \log \perL}}} \leq \min_i \|\vb_i^*\|\), the \(\BDD\) decoding radius, so \(\BDD\) can be solved with approximation factor \(\frac{1}{2^{\sqrt{\fgr \log \perL}}}\).
3. Use the \(\GapSVL_\gamma\) to \(\BDD_{\frac{1}{\gamma}\sqrt{\frac{n}{\log n}}}\) reduction of Pei09/LM09, resulting in an approximation factor of \(\gamma(n) = 2^{\sqrt{\fgr \log \perL}} \cdot \sqrt{\frac{\log n}{n}}\) for \(\GapSVL\).

Because of the particular basis dependence algorithm, it also means that sampling from the Gaussian weighted dual lattice is possible out to some related bound.

1. Break RSA mod \(N\) \(\leq\) factor \(N\). Therefore, if there is an algorithm for factoring then there is an algorithm to break RSA.
2. Solve SVP \(\leq_Q\) break LWE. Therefore, if there is no quantum algorithm for SVP, then there is no quantum algorithm for breaking LWE.
3. \(\BDD \leq \SVP\) when the approximation factor is something.

One might say that \(\BDD \leq \LWE \leq \BDD\) to have a high-level understanding of the relationship, but what's missing in that statement are the parameters and problem definitions that give the relationships the necessary meaning.

1. The theoretical connection \(\BDD \leq \LWE\) is used to conclude that an algorithm for \(\LWE\) can be used to construct a quantum algorithm for \(\BDD\).
2. Concrete security involves choosing key sizes for implementations. This uses the more the direct \(\LWE\) \(\leq\) \(\BDD\) reduction, similar to Break RSA \(\leq\) Factoring. In this case a \(\BDD\) algorithm of the right parameters can be used to solve LWE, because after an \(\LWE\) instance is chosen and fixed, it is then a \(\BDD\) instance. Running \(\BDD\) algorithms on those instances is used to understand how well algorithms perform on LWE.

The first step of the worst-case to average-case reduction in Reg09 is a classical reduction from \(\BDD\) to \(\LWE\). Here is a sketch.

Let \(\qqn\) and \(\alpha(n)\) be functions such that \(2\sqrt{n} \leq \qqn\alpha(n)\).
Let \(m(n)\) be a polynomial in \(n\).
Input: \(\pB\) for lattice \(\pL\) of dimension \(n\), target vector \(\vt = \pB\cdot \vs + \vD\), \(\|\vD\| \leq \alpha(n) \lambda_1(\pL)\).

1. Repeat until \(\vs\) is computed:
   1. Sample \(\dv_1,\ldots, \dv_{m(n)} \in \dL\) according to a Gaussian with parameter \(\varphi_{3n}(\dL)\).
   2. For \(i = 1, \ldots , m(n)\):
      1. Compute \(\va_i = \dv_i \cdot \pB \bmod \qqn\).
      2. Compute \(b_i = \dv_i \cdot \vt \bmod \qqn\).
   3. Call the \(\LWE_{n,\qqn,\alpha}\) oracle with \((\va_1,b_1), \ldots, (\va_{m(n)}, b_{m(n)})\) and get the low-order bits the secret coefficient vector, namely \(\vs_\ell = \vs \bmod \qqn\), where \(\vs = \vs_h \qqn + \vs_\ell\).
   4. Set \(\vt := \frac{\vt - \pB\cdot \vs_\ell}{\qqn} = \frac{\pB\cdot(\vs_h \qqn + \vs_\ell - \vs_\ell) + \vD}{\qqn} = \frac{\pB \cdot\vs_h\qqn}{\qqn} + \frac{\vD}{\qqn}\).

Some differences between \(\BDD\) and \(\LWE\) can be seen in this reduction. The lattice given as part of the \(\BDD\) input is any lattice. The input to the \(\LWE\) problem has an associated random lattice that can be computed from the \(\va_i\)'s. The classical hardness result for \(\LWE\) uses this part of the reduction and shows that if \(\LWE\) is solvable then it is possible to approximate length of a shortest vector of an arbitrary lattice. In contrast, the length of a shortest vector in the associated \(\LWE\) lattice is easy to compute. It ends up being long, which is can be useful.

• Some notation for quantum samples

  To describe the steps of the quantum reduction in a somewhat concise way the notion of quantum sampling can be used to replace the classical samples. For a given distribution, a quantum sample is a quantum state whose measurement results in a sample from the same distribution.

  For this reduction, let \(\Gdist{\dL,r}\) be the discrete gaussian distribution on \(\dL\) with standard deviation \(r\). This is called \(D_{\dL,r}\) in Reg09. A quantum sample of this distribution is the superposition \(\Gsup{\dL,r} = \sum_{\dv\in\dL} \sqrt{p_\dv} |\dv\>\), where \(p_\dv\) is the probability of measuring \(\dv\) from \(\Gdist{\dL,r}\). Measuring \(\Gsup{\dL,r}\) destroys the state, so the algorithm will need to create a quantum sample in each of \(m(n)\) registers, resulting in the state \(\Gsup{\dL,r}^{\otimes m(n)}\). This is tensor product notation for the state \(\Gsup{\dL,r}\Gsup{\dL,r} \cdots \Gsup{\dL,r}\), \(m(n)\) times. To summarize the notation, given the state \(\Gsup{\dL,r}^{\otimes m(n)}\), it can be measured any time to produce \(m(n)\) independent samples from \(\Gdist{\dL,r}\).

• For \(\SIVP\) the reduction will compute \(\Gsup{\dL, \varphi_0(\dL)}^{\otimes m(n)}\), where \(\varphi_0(\dL) = \frac{\sqrt{2n}}{\alpha(n)}\eta_\epsilon(\dL)\). The approximation factor is therefore not just a function of the dimension \(n\) but also of the input lattice itself. This quantum sample is enough to solve \(\SIVP\). Measuring the state will result in samples where \(n\) can be selected such that the length is at most \(\sqrt{n} \varphi_0(\dL)\).

• Reduction sketch

  Let \(\qqn\) and \(\pfactor(n)\) be functions.
  Let \(m(n)\) be a polynomial in \(n\).
  Input: \(\pB\) for lattice \(\pL\) of dimension \(n\), target vector \(\vt = \pB\cdot \vs + \vD\), \(\|\vD\| \leq \pfactor(n) \lambda_1(\pL)\)

  1. Compute \(\Gsup{\dL,\varphi_{3n}(\dL)}^{\otimes m(n)}\).
  2. for \(i = 3n-1, 3n-2, \ldots, 0\):
     1. Measure the state \(\Gsup{\dL,\varphi_{i+1}^{}(\dL)}^{\otimes m(n)}\) to generate \(m(n)\) samples \(\dv_1, \ldots, \dv_{m(n)}\) from \(\Gdist{\dL, \varphi_{i+1}(\dL)}\).
     2. For \(i = 1,\ldots, m(n)\):
        1. Compute \(\va_i = \dv_i \cdot \pB \bmod \qqn\).
        2. For \(j = 1, \ldots, m(n)\):
           1. In new registers, compute \(\sum_{\pv \in \pL} \rho_?(\pv) \sum_{\vt} \rho_?(\vt)|\pv+\vt\>|\vt\>|0\>^{\otimes m(n)}\).
           2. Compute each \(b_i^{(\vt)} = \dv_i \cdot \vt \bmod 1\), giving \[\sum_{\pv \in \pL} \rho_?(\pv) \sum_{\vt} \rho_?(\vt)|\pv+\vt\> |\vt\>|b_1^{(\vt)},\ldots,b_{m(n)}^{(\vt)}\>.\]
           3. Compute \(\pfactor\)-\(\BDD\) using \(\LWE\) on \((\va_1, b_1^{(\vt)}), \ldots,(\va_{m(n)}, b_{m(n)}^{(\vt)})\) to erase \(\vt\), giving \[\sum_{\pv \in \pL} \rho_?(\pv) \sum_{\vt} \rho_?(\vt)|\pv+\vt\>|0\>|b_1^{(\vt)},\ldots,b_{m(n)}^{(\vt)}\>.\]
           4. Uncompute each \(b_i^{(\vt)}\) by computing \(\dv_i \cdot (\pv+\vt) = \dv_i \cdot \pv + \dv_i \cdot \vt \bmod 1 = b_i^{(\vt)}\), subtracting, and running backwards to get \[\sum_{\pv \in \pL} \rho_?(\pv) \sum_{\vt} \rho_?(\vt)|\pv+\vt\>|0\>|0\>^{\otimes m(n)}.\]
           5. Compute \(F_{q(n)}\) to get \(\Gsup{\dL,\varphi_i(\dL)}\).
  3. Output \(\Gsup{\dL,\varphi_0(\dL)}^{\otimes m(n)}\).

Running times and approximation factors for lattices have typically been measured as a function of their dimension \(n\). It makes for nice, clean statements. For example, LLL is a polynomial-time algorithm to compute vectors within a \(2^n\) factor of the shortest vector. Babai's algorithm takes also takes a vector in space and computes a close lattice vector that is within a \(2^n\) factor of the closest. These approximation factors are exponential in the dimension \(n\). It can be said that there is no efficient algorithm known to achieve subexponential or polynomial approximation factors. See, for example Remark 2 and Page 8, Algorithms and Complexity. Furthermore, this has been the case for decades. There are also classes of lattice problems that are NP-hard but are not relevant here because they are not in CoNP.

The typical way to handle being stuck is to break the problem down into special cases to try to make progress. For lattices, perhaps measuring everything in terms of the dimension is preventing progress. For example, there might be an efficient algorithm for problems with a subexponential approximation factor, like \(2^\sqrt{n}\), but it's too hard to find it all at once, just like it's too hard to climb a mountain in one giant step.

As one of the L's in LLL once told me, when everyone is stuck on a problem, it is a form of art to back off the full problem and solve a subcase that is both nontrivial and solvable.

Without loss of generality, a lattice can be specified by a basis \(\matB\) and numbers \(\per_1(L),\cdots,\per_n(L)\) with the following properties. Let \(\perL\) be the minimum number such that \(\perL \Z^n \leq L\).

1. For each \(i\), \(\per_i(L)\cdot \vb_i\) is a multiple of \(\perL\),
2. \(1= \per_{n}(L)\ \big|\ \per_{n-1}(L)\ \big|\ \cdots\ \big|\ \per_1(L)\ \big|\ \perL\).

In particular, \(L \bmod \perL\) is a finite abelian group, and columns \(\vb_{\fgrL+1},\ldots,\vb_n\) are \(\vzero \bmod \perL\). For \(\SVP\) and \(\CVP\) those columns do not provide extra information.

1. Using FHE, given \(\matA, \matA\vs+\ve\), compute \(\matA', \matA'(q/2)\vs+\ve'\).