3
$\begingroup$

I am currently writing a seminar paper on Kyber and other lattice-based methods. I was so excited about the lattice-based methods that I also currently searched quantum algorithms to solve the methods.

In the process, I came across this paper: https://www.mdpi.com/1099-4300/24/10/1428/pdf, called "Using Variational Quantum Algorithm to Solve the LWE Problem." by Lihui Lv et. al. There, the authors claim to have developed an algorithm that takes just 25.482, QBits to crack Kyber1024. That is less than for RSA encryption.

I am not an expert on quantum computing. What I have been able to determine is that there are no comparable papers that indicate such a rapid improvement in quantum algorithms.

$\endgroup$
1
  • 1
    $\begingroup$ I don't see where in the paper they discuss the time complexity, in fact, at one point, they say (in section 5) "Since it is difficult to estimate the computing complexity of QAOA, the QAOA process is regarded as a black box...". Without knowing how long the algorithm takes, it is hard to say whether it has any impact on security (even if the algorithm is correct, which I cannot say) $\endgroup$
    – poncho
    Dec 12, 2022 at 18:36

2 Answers 2

3
$\begingroup$

While I'm not a quantum computing expert, typical estimates for RSA/DLOG are on the order of ~2k (logical) qbits, so depending on whether you mean physical/logical your numbers might be off. Their claimed techniques of reducing to BDD or uSVP are standard in the field though. They also don't seem to cite state-of-the-art on quantum algorithms for structured lattice problems, namely this work by Cramer, Ducas, and Wesolowski, which was initially published in 2017. That work was limited to lattice problems for module rank 1, while you need module rank $\geq 2$ to break (R/M)LWE, and Kyber is based on MLWE (might need module rank ~3-5 to break it? idk)

Overall I doubt this paper is particularly useful to look into compared to something like the work I linked above if you want to understand the state of the art for quantum algorithms for structured lattice problems. If it is claiming efficient quantum attacks on Kyber (I have not carefully read it), it would need two simultaneous breakthroughs

  1. reduction of the approximation factor for CDW (from sub-exponential to probably some polynomial)
  2. generalization of CDW from module rank 1 to module rank $\geq 2$.

I don't personally expect the paper to contain solutions to both of these problems (especially as it doesn't even cite CDW!), as it seems to be reanalyzing standard classical algorithms in a particular quantum computing framework, and seems mainly concerned with bounding the space complexity of representing various reduced lattice basis. Specifically, section 4.2 bounds

$$qbits = \sum_{i = 1}^{m'} (\lfloor \log_2 d_i\rfloor + 1)$$

where $d_i$ looks to be $\ell_\infty$ bounds on the size of the $i$th coefficient of an $m'$ dimensional matrix $B$ (this isn't a typo --- they parameterize their matrix $B$ by a single dimension parameter for some reason, which is non-standard). Classically, this would simply correspond to a space complexity bound to represent $B$ with (classical) bits, as poncho suggests in the comments, i.e. nothing really related to bounding the time complexity itself.

$\endgroup$
1
$\begingroup$

The idea behind this paper (and other previous work on "NISQ"-y quantum lattice algorithms) is to translate a hard lattice problem into a binary optimization problem. To show how this works for SVP, let $B$ be a matrix of the basis vectors of an $n$-dimensional lattice $L$. Suppose we want to find the shortest vector $v$. Being shortest is equivalent to being the $v\in L$ which minimizes $v^Tv$. We can further decompose $v=Bx$ for some integer $x$, so we want to find the $x\in \mathbb{Z}^n$ which minimizes $x^TB^TBx$. Even more, we can decompose each component of $x=(x_1,\dots, x_n)$ into binary, as $x_i = x_{i0}+x_{i1}2^1 + x_{i2}2^2 + \dots + x_{im}2^m$ for some $m$, where each $x_{ij}\in \{0,1\}$. Thus, we can rewrite $$ v^Tv = x^TB^TBx = \sum_{ijk\ell st} x_{ij}2^jB_{si}B_{tk}x_{k\ell}s^\ell = \sum_{ij k\ell} x_{ij}x_{k\ell} C_{ijk\ell}$$ where $C_{ijk\ell}:= \sum_{st} 2^{j+\ell}B_{si}B_{tK}$.

Minimizing $v^Tv$ for $v\in\ell$ is equivalent to minimizing the expression above over all possible binary choices of $\{x_{ij}\}$.

Actually, binary optimization problems are also extremely hard, so this isn't really helpful classically (we've basically thrown away all the geometric lattice structure!). But the helpful fact here is that evaluating this cost function is actually fairly straightforward on a quantum computer.

Once you can evaluate a cost function on a quantum computer, you can try any number of quantum optimization techniques (such asQAOA as in the linked paper, or a variational quantum eigensolver). The details of these aren't important; the relevant fact is that in terms of queries (so, roughly equivalent to runtime), they can't outperform Grover's algorithm. Looking at the above, we have $nm$ binary variables, so the search space is $2^{nm}$ and that means a runtime of $O(2^{nm/2})$. Here they analyze carefully and bound $m= O(\log n)$ (meaning the coefficients don't need to be larger than $O(n)$ for the shortest vector, if the basis is preprocessed). Thus, the runtime is at best $2^{O(n\log n)}$: asymptotically the same as quantum enumeration, worse than quantum sieving (though without the memory requirements).

So if variational/approximate algorithms don't offer an asymptotic improvement on previous algorithms, why do we care? Because these algorithms require only short quantum computations before a classical measurement. Thus, the fault-tolerance overhead can be much lower and hence the qubit requirements of the algorithm are also much lower. Thus, it might be easier to build a huge array of quantum computers that could run a NISQ-y quantum algorithm, rather than the fully fault-tolerant quantum enumeration or lattice sieving.

More precisely, you say "just 25.482, QBits to crack Kyber1024. That is less than for RSA encryption.", which isn't quite right. RSA encryption takes only a few thousand logical qubits, which are high-fidelity qubits with error correction overhead. The best estimates today say that this will need several million physical qubits (the actual components of the quantum computer). In contrast, we might be able to run these NISQ lattice solvers directly on the physical qubits, or with less error correction so that they use fewer than a million physical qubits.

But overall I'm quite skeptical. We have no runtime guarantees on these algorithms, noise can be a big problem, and we just have to hope that the classical optimizer can do a good enough job to find the right solution. It's interesting and worthwhile for quantum cryptanalysts to consider, but I don't think it has any impact on lattice security estimates.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.