Implications of the Proposed Quantum Attack on LWE

On April 10th 2024 Yilei Chen published a paper on ePrint entitled Quantum Algorithms for Lattice Problems. In it he proposes a "polynomial time" quantum algorithm for certain parameters sets for the Learning-With-Errors (LWE) problem. This is important as LWE forms the basis of the majority of the post-quantum algorithms selected by NIST, and it also forms the basis of a number of cryptographic constructions which offer advanced functionalities such as Fully Homomorphic Encryption (FHE). In this note I try to work out what the implications of this work are.

Updates to this post are at the bottom


The following should be read with a number of caveats in the back of ones mind. The most notable of these are:
  1. I am not an expert in quantum algorithms.
  2. The paper of Chen has not yet been peer reviewed, so it may contain some errors.
  3. Quantum computers may never be built. Indeed it is a running joke that quantum computers are always ten years in the future!

The LWE Problem

So we are all on the same page let us define the LWE problem itself. This is a noisy version of linear algebra. It is (in its most basic form) parametrized by four values $n, m, q \in \mathbb{N}$, $\alpha \in [0,1]$.

The value $q$ is used to define the modulus in modular reduction. In what follows we assume that we represent $\mathbb{Z}_q$ as the integer values in the range $(-q/2,\ldots,q/2]$, i.e. we take a centered reduction in all modular operations.

The value $\alpha$ is used to define a distribution $D$. Usually this is chosen to be a Gaussian like distribution on $\mathbb{Z}$ with standard deviation $\alpha \cdot q/\sqrt{2 \pi}$, although other distributions (such as a uniform distribution with roughly the same standard deviation) could also be used. In any case the distribution $D$ produces an integer value in the range $[-c \cdot \alpha \cdot q, \ldots, c \cdot \alpha \cdot q]$ with overwhelming probability for some small constant $c$. One can think of this $c$ as say $10$ in what follows.

The LWE problem is defined by a secret vector $\mathbf{s} \in \mathbb{Z}_q^n$ and a secret vector $\mathbf{e} \in D^m$, i.e. we select $\mathbf{e}$ from the product of $m$ copies of the distribution $D$. Thus $\mathbf{e}$ contains $m$ "small" values.

Then a public matrix $A$ of dimension $m \times n$ is selected with entries selected in $\mathbb{Z}_q$, and the value $$\mathbf{y} = A \cdot \mathbf{s} + \mathbf{e} \pmod{q} $$ is computed.

The (computational) LWE problem is to recover $\mathbf{s}$ from the pair $(A, \mathbf{y})$. There is also a decisional variant, which is more used in cryptographic definitions, but it is essentially as hard as the computational version and so we will not consider it further here.

A key point to note, from a complexity point of view, is the following. In complexity theory usually looks at complexity as a function of the size of the input to the problem. The size of the input problem in LWE is $$ n \cdot (m+1) \cdot \log_2 q \approx n \cdot m \cdot \log_2 q. $$ Thus the size does not depend on $\alpha$. When talking about a polynomial time algorithm to solve LWE (in the normal complexity theoretic sense) we should only consider algorithms whose complexity is a polynomial function of $ n \cdot m \cdot \log_2 q$.

The value $n$ is called the LWE dimension and the value $m$ denotes the number of "LWE samples". Just as in normal linear algebra one requires at least as many equations as variables in order to fix the solution, one requires $m \ge n$ here in order to fix $\mathbf{s}$. This means we require the number of samples to be $m \ge \Omega(n \cdot \log q)$. See update from April 16th below for a note on this

But $\alpha$ is crucial to the hardness of LWE:

The value of $\alpha$ is important in applications:
  1. For applications such as traditional Public Key Encryption (as in Kyber) the standard deviation of the distribution $D$ is chosen to be the fixed value of $\sqrt{(3+1)/2}=2$ (since the distribution is the NewHope distribution with parameter $B=3$). Thus we have $\alpha \cdot q = 2 \cdot \sqrt{2 \cdot \pi} = \sqrt{8 \cdot \pi}$, i.e. $\alpha \cdot q$ is constant. However, we have $q$ as the fixed value of $q=3329$, and so $\alpha = 0.0015 \approx q^{-0.801}$. So $\alpha \cdot q \approx q^{0.1987}$. In Kyber we have $n \approx q$.
  2. For Public Key Signatures (as in Dilithium) the distribution $D$ (in the Dilithium secret key) is a uniform distribution in the range $[-\eta,\ldots,\eta]$, where $\eta$ is $2$ or $4$. However the modulus $q$ in Dilithium is much larger than in Kyber, being $q=8380417$. Thus we have a standard deviation of $D$ of at most $\sqrt{(2 \cdot \eta)^2/12} = 4/\sqrt{3}$, and so $\alpha \cdot q = \sqrt{64 \cdot \pi/3} \approx q^{0.1318}$. In Dilthium we have $n = 5 \cdot 256$ for the Level 3 parameters.
  3. For applications such as levelled FHE (as typified by the BGV and BFV FHE schemes) the depth of the supported homomorphic operations is governed by the gap between the values $q$ and $\alpha \cdot q$, i.e. a very very small value of $\alpha$ is desired. For such schemes one can think of $\alpha \cdot q$ as being a small constant. Indeed one can think of $\alpha \cdot q$ as being the same value as in Kyber, i.e. $\sqrt{8 \cdot \pi}$. But then one then picks $n, m$ and $q$ to obtain both security and homomorphic depth. This results in very large values of $q$ indeed, for example one could have $q \approx 2^{1024}$, in which case $\alpha \cdot q \approx q^{0.00227}$. For BGV typical values of $n$, with $q \approx 2^{1024}$, are of the order of $2^{15}$ or $2^{16}$. (See Bootstrapping for HElib for a discussion of parameters for BGV which support bootstrapping).
  4. For applications such as FHE schemes which support efficient bootstrapping (as typified by TFHE and FHEW), one does not need a huge gap between $q$ and $\alpha \cdot q$. Indeed for these one can think of $\alpha$ (for the purposes of this post we think of TFHE with $q=2^{64}$) as being of the order of $1/\sqrt{q}$, and so $\alpha \cdot q \approx \sqrt{q}$. For such TFHE parameters the dimension $n$ is under $2^{11}$.

This importance of the value of $\alpha \cdot q$ has been known for a long time Regev's original hardness result for LWE only holds when $\alpha \cdot q > 2 \sqrt{n}$. Interestingly this inequality is only satisfied for the TFHE style parameters above, it does not hold for the parameter sets for Kyber, Dilithium or BGV.

The classical manner to determine parameters for the LWE problem is to use the lattice-estimator. This runs all known lattice algorithms against a given parameter set, and tries to determine the number of classical operations needed to solve the LWE problem. If it comes up with a value of more than $2^{128}$ then usually one considers the parameters to be secure.

Intuition though can be a bit strange. For example if one keeps $m, n$ and $\alpha \cdot q$ constant, but one just increases $q$, then the LWE problem becomes easier! This is unlike (say) RSA or DLP were to make things more secure we just increase the modulus.

When looking at quantum complexity intuition can also be a bit strange. For example Grover's algorithm should imply that AES-128 is not considered secure in a post-quantum world, as the attack via Grover's algorithm on AES-128 would require $2^{64}$ quantum "operations". However, most people think AES-128 will still remain secure in a post-quantum world as the overall complexity of Grover's algorithm when applies to AES-128 would be way beyond any feasible quantum computer.

LWE Problem Summary

The key take away points:
  1. Polynomial time should be measured in terms of the input problem size.
  2. The $\alpha$ value is important, both for security and applications.
  3. The $\alpha$ value is significantly different in different practical applications of LWE.
  4. A "low" complexity quantum attack may not actually translate into a practical quantum attack (as in AES-128), even when/if a quantum computer is built.

The Proposed Algorithm

The algorithm of Chen uses a quantum subroutine, which is called $O(n)$ times, in order to generate a system of linear equations which can then be solved by classical means. The quantum subroutine is called as many times as is needed in order to obtain a full rank linear system.

The algorithm is only given for when $D$ is a Gaussian-like distribution, but let us assume that this restriction can be removed (so we can apply it to the distributions used in practical schemes based on LWE).

As said earlier I am not an expert on quantum algorithms, so I will not discuss the quantum subroutine, but we can discuss the theorem statement given by Chen. This is

Theorem: Let $n,m,q \in \mathbf{N}$, $\alpha \in (0,1)$ be such that

There is then a quantum algorithm that solves LWE in time $\mathsf{poly}(m, \log q, \alpha \cdot q)$.

Now let us consider this statement in more detail.

The Conditions

The first thing one needs to consider are the conditions.

We have already discussed that we need more samples $m$ than variables $n$ in our secret, so the first condition should not be a surprise.

We now need to look at the second condition, i.e. $q \in \tilde{\Omega}((\alpha \cdot q)^4 \cdot m^2)$. The key point is the dependence of $q$ on $\alpha \cdot q$. Let us map these to our four cases considered above.

  1. Kyber: Here, recall, $\alpha \cdot q \approx q^{0.1987}$ so the condition is that $$ q \in \tilde{\Omega}(q^{0.7948} \cdot m^2). $$ However, we also have for Kyber that $m > n \approx q$. Thus, we do not have $$ q \in \tilde{\Omega}(n^{2.7948}).$$ Of course the proposed attack (if correct) could be improved possibly, but it would seem highly unlikely that it could be applied to Kyber as is.

  2. Dilithium: Here, recall, $\alpha \cdot q \approx q^{0.1318}$. But now we have the dimension $n = 5 \cdot 256$ (for the Level 3 parameters) with $q=8380417$, thus $q \approx n^{2.22}$. This means $\alpha \cdot q \approx n^{0.2925}$, and the second condition becomes $$ q \in \tilde{\Omega}(n^{3.170}).$$ Thus less of an improvement is needed in the attack for it to apply to Dilithium.

  3. BGV: Recall, we have $\alpha \cdot q \approx q^{0.00227}$ and $n$ could be around $2^{15}$ or $2^{16}$, with $q \approx 2^{1024}$. Thus we have $\alpha \cdot q \approx n^{.1550}$. Our second condition then becomes $$ q \in \tilde{\Omega}(n^{2.620}).$$ But for BGV we have $q \approx n^{68.266}$. So it would appear that the attack should apply to BGV.

  4. TFHE: In this case, recall, we have $\alpha \cdot q \approx \sqrt{q}$. We also have that $q =2^{64}$ and $n \le 2048$ and so $q \approx n^{5.818}$, and so we have that $\alpha \cdot q$ can approximated by $n^{2.909}$. The second condition of the theorem then becomes $$ q \in \tilde{\Omega}( n^{13.636} ).$$ Yet we have $q \approx n^{5.818}$! Thus the attack would need to improve quite a bit to apply to TFHE.

The Complexity

Having discussed the conditions under which the theorem applies we can now turn to the conclusion. Here we need to consider the algorithm complexity, i.e. $$\mathsf{poly}(m, \log q, \alpha \cdot q).$$ Alas, the theorem does not give any implied constants or the polynomial degrees.

Schor's algorithm is devasting against RSA and ECDLP because the quantum complexity is really not that large. So if a quantum computer was ever built then it is plausible that RSA and ECDLP would be broken. On the other hand the quantum complexity of Grover's algorithm against AES-128 is really high, and so it would take a huge quantum computer in order to dent the security of AES-128. From these two examples we can conclude that constants matter.

We note, however, that the complexity depends on $\alpha \cdot q$, i.e. it depends on a parameter which is not specified by the input problem size. Thus we have to look at each scheme in turn, where different values of $\alpha \cdot q$ are given.

The following is a very crude examination, but it shows why the constants matter here. And we can have a view as to whether the complexity is going to be feasible or infeasible to launch an attack on an early stage quantum computer.

What I do is replace the terms $m$, $\log q$ and $\alpha \cdot q$ in the complexity estimate by the powers of two of these values for the four schemes being discussed (I approximate $m$ with $n \cdot \log q$). One then make ones own guess as to the implied constants, and decide on which scheme one needs to worry about.

  1. Kyber: $\mathsf{poly}(2^{13.87}, 2^{3.55}, 2^{2.32}).$
  2. Dilithium: $\mathsf{poly}(2^{14.84}, 2^{4.52}, 2^{3.03}).$
  3. BGV: $\mathsf{poly}(2^{25.00}, 2^{10.00}, 2^{2.32}).$
  4. TFHE: $\mathsf{poly}(2^{17.00}, 2^{6.00}, 2^{32.00}).$
For Kyber and Dilithium we see that, assuming the implied constants and degree are relatively small, the attack may be feasible, if the conditions of the theorem can be improved.

For BGV we already noted that the conditions of the theorem are satisfied, thus whether the attack is practical (on a future quantum computer) depends on the dependence of the attack on the value of $m$.

    I suspect the dependence on $m$ is quite mild, as it probably related to the repetition of the quantum sub-routine and not the complexity of the sub-routine itself. But that is a pure guess on my part at this point.

For TFHE we see that, assuming the conditions of the theorem can be improved in order to bring TFHE into scope, the complexity would also need to not depend on too high a polynomial in $\alpha \cdot q$, as this is already $2^{32}$ for standard TFHE parameters.


One should not necessarily throw the baby out with the bathwater over this new paper. There are extra caveats as well as my earlier ones of it not yet being peer reviewed, or a quantum computer not yet being built.
  1. The theorem pre-conditions do not apply to Kyber, Dilithium or TFHE as currently proposed; they do however apply to BGV.
  2. Even if the pre-conditions were improved, the importance of the complexity estimate on the noise term $\alpha \cdot q$ needs to be considered as to whether any attack is feasible.
  3. Even a low quantum complexity value of the form of $2^x$ quantum operations, for $30 \le x \le 100$, may not result in a viable quantum algorithm (as per Grover applied to AES-128).
  4. The attack only defeats quantum adversaries, if no large scale quantum computer is ever built then we can still happily use (any form of) FHE.
  5. Companies are happily deploying SNARKs based on pairing based crypto, even though pairing based crypto will fall long before LWE to any quantum computer; simply due to the complexity of the different quantum algorithms.

Nigel Smart
April 15th 2024.

Update April 16th

I give two updates
  1. One from reading the paper
  2. One from discussion with Vadim Lyubashevksy

Update From Reading the Paper

Today I had a more detailed look at Section 3 of the paper where the parameters of the attack are given in more detail.

Section 3.1

This section maps the input LWE problem (now the LWE dimension is referred to as $\ell$ instead of $n$ and the author sets $\beta=\alpha \cdot q$ to make things easier to parse) with uniform secret into a problem with a secret chosen from the error distribution, but with $\kappa$ values chosen to be of the attackers choice.

Basically there is a map between the input problem $$ \mathsf{LWE}_{\ell-(\kappa-1),m+\ell-(\kappa-1),q,U(\mathbb{Z}_q),\chi} $$ for error distribution $\chi$ with parameter $\beta$, to the problem $$ \mathsf{LWE}^{\kappa-1 \mathsf{\ chosen\ secret}}_{\ell,m,q,\chi,\chi}. $$

Section 3.2

Then odd coprime values $p_1,\ldots,p_\kappa$ are picked so that $$ p_2,\ldots,p_\kappa \le \frac{\log n}{p_1}, $$ where $n = 1+\ell+m$. It would appear for the small values of $\ell$ one would expect $\kappa$ therefore to be equal to one or two, unless $m$ (and hence $n$) is selected to be huge. So the selection of $\kappa$ is going to also affect how many LWE samples, i.e. $m$, we need to start with (see below for a comment on what increasing $m$ means for concrete LWE problem instances).

The $\kappa-1$ chosen parts of the secret key are selected to be $p_2,\ldots,p_\kappa$. The key aspect now is we are solving a equation $$ A \cdot \mathbf{b} =0 \pmod{q} $$ where the vector $\mathbf{b}$ is of the special form $$ \mathbf{b} = [-1,2 p_1 p_2, \ldots, 2 p_2 p_\kappa, 2 p_1 \mathbf{s}_{[\kappa,\ldots,\ell]}, 2 p_1 \mathbf{e}]. $$ The algorithm works by guessing the value of $b_2 = \Vert \mathbf{b} \Vert^2$. Lemma 3.6 tells us that there are at least $\beta^2$ such choices for $\Vert \mathbf{b} \Vert^2$. Indeed we have, with high probability $$ b_2 \in 1+4 p_1^2 (p_2^2+\ldots+p_\kappa^2) + [0.04,0.27] \cdot 4 p_1^2 \beta^2 (n-\kappa). $$

First Main Point: This means the complexity seems at this point to be at least $\beta^2$, as we need to guess $b_2$ from a range of size roughly $p_1^2 \beta^2 (n-\kappa)$.

Section 3.3

Section 3.3 then defines a bunch of constants and constraints which enable the main quantum subroutine to work, and be successfull in solving the underlying LWE problem.

Constraint C.3 seems to be an issue. For the guessed value of $b_2$ we need to find a value $c \in 4 \mathbb{Z}$ such that $$ (c+1) b_2 = p_1 p_2 \cdots p_\kappa, $$ and we need to select the $p_i$ so that $$ p_2 \cdots p_\kappa = -1 \pmod{p_1}.$$

The only way I can get things to work out in order would be as follows (which is almost what the author suggests):

  1. Pick a value for $c \in 4 \mathbb{Z}$.
  2. Set $p_1 = c+1$.
  3. Use the bound from Lemma 3.6 $\sqrt{b_2} \le 3 p_1 \beta \sqrt{n}$ to guess a value for $b_2$, i.e. $0 \le b_2 \le 9 p_1^2 \beta^2 n$. We have the constraint $b_2 = 1 \pmod{4 p_1^2}$, so we only need to consider roughly $2 \beta^2 n$ values for $b_2$.
  4. Now factor $b_2$ into coprimes $p_2,\ldots,p_\kappa$ for some $\kappa$ value.
  5. Set $A = b_2 - 1 - 4 p_1^2 (p_2^2+\ldots+p_\kappa^2)$.
  6. Reject if $A \not\in [0.04,0.27] \cdot 4 p_1^2 \beta^2 (n-\kappa)$. Maybe we dont even bother rejecting such values?
I cannot get the $p_2 \cdots p_\kappa = -1 \pmod{p_1}$ condition to hold though using this method. Note, the authors example in the paper has $p_2 \cdots p_\kappa=1 \pmod{p_1}$ and not $-1 \pmod{p_1}$. So perhaps this is a typo!

Suppose our guess for $b_2$ is a prime, and that this is the correct value. Then we would have to have $\kappa=2$ and $p_2 = b_2$. There seems no reason why we should have $p_2 = -1 \pmod{p_1}$ at this point. We would also have $$ p_2 = 1+p_1^2 p_2^2 + [0.04,0.27] \cdot 4 p_1^2 \beta^2 (n-\kappa). $$ Which obviously cannot hold. Thus for this factorization into $p_2 \cdots p_\kappa$ to make sense we really need a special value of $b_2$. So something seems very weird!

Update in Relation to $m \ge \Omega(n \cdot \log q)$

As Vadim Lyubashevksy has pointed out to me that the problem considered in the paper is really for generic LWE, i.e. for a potentially unlimited or large number of samples. In real world cryptosystems one has a fixed number of basic samples, in particular normally we are only given $m=n$ such samples.

If the attack requires more samples then we need to generate these from the samples we have been given. This is done by combining small linear combinations of the existing samples. But we cannot use too small values in the linear combinations, otherwise you introduce known small vectors into the resulting lattice, which the algorithm then solves for; i.e. it ends up solving for vectors which you already know. Thus we need to pick combinations for which the multipliers are small, but not too small. But this itself blows up the noise (i.e. the $\alpha$ value). Which makes the attack less practical.

For example suppose our input LWE samples are $$\mathbf{y} = A \cdot \mathbf{s} + \mathbf{e} \pmod{q} $$ for an $n \times n$ square matrix $A$. Then to generate new samples one would multiply the equation on the right by a matrix $R$ which contains small values, is not too sparse, but the small values are not too small. i.e. we would form the system $$\mathbf{z} = R \cdot \mathbf{y} = (R \cdot A) \cdot \mathbf{s} + R \cdot \mathbf{e} \pmod{q}. $$ But now the noise values have gone up from $\Vert\mathbf{e}\Vert_\infty$ to $\Vert R \cdot \mathbf{e}\Vert_\infty$. This increases the value of $\alpha$, and hence the $\beta$ value above, and hence the attack complexity.

Nigel Smart
April 16th 2024.

Update April 17th

So yesterday I had two problems with the Condition C.3. These have been somewhat solved via communication with Yilei.

Revisiting Condition C.3

With these points in mind let us revisit C.3 and come up with an algorithm taking into account the two fixes of either assuming $p_i \le 10 \log n$, or assuming $\kappa$ is fixed.

Option A: Setting $p_i \le 10 \log n$

  1. Pick a value for $\kappa$ (to be determined).
  2. Pick a value for $c \in 4 \mathbb{Z}$, say $c=4$.
  3. Set $p_1 = c+1$, i.e. $p_1=5$.
  4. Pick odd coprime values $p_2,\ldots,p_\kappa$ (coprime also to $p_1$) subject to $p_i \approx 10 \log n$.
The question is, how big should we pick $\kappa$?

Again, we know $b_2 = p_2 \cdots p_\kappa$ and we also know that (assuming $\kappa>4$) that the size of $b_2$ will dominated by the term $p_1^2 \beta^2 (n-\kappa)$. Since $\kappa$ is tiny compared to $n$ we basically get something like $$ p_i^{\kappa-1} \approx p_1^2 n \beta^2. $$ Recall, we have $\beta = \sqrt{8 \pi}$ for Kyber and BGV, $\beta = \sqrt{64 \pi/3}$ for Dilithium, and $\beta =2^{32}$ for TFHE. This is assuming $\beta$ has not needed to be increased due to the need to generate more samples as explained above, so these assumptions on $\beta$ are the best possible scenario.

When $\beta = \sqrt{8 \pi}$ we see we need $$ (\kappa-1) \log ( 10 \log n) \approx 2 \log (p_1 \beta) + \log n \approx 6.443 + \log n. $$ i.e. $$ \kappa \approx \frac{6.443+\log n}{\log (10 \log n)}+1. $$ Note, to get $\kappa>4$ this means we need an $n$ bigger than $2^{29}$ here. This is a lot of LWE samples by any stretch of the imagination.

When $\beta=2^{32}$ we obtain $$ (\kappa-1) \log ( 10 \log n) \approx 2 \log (p_1 \beta) + \log n \approx 47.58 + \log n. $$ i.e. $$ \kappa \approx \frac{47.58 + \log n}{\log (10 \log n) }+1. $$ Note, we always obtain $\kappa>4$ here, irrespective of the value of $n$.

Option B: Setting $\kappa=10$

  1. Pick $\kappa=10$. In any case pick $\kappa > 4$.
  2. Pick a value for $c \in 4 \mathbb{Z}$, say $c=4$.
  3. Set $p_1 = c+1$, i.e. $p_1=5$.
  4. Pick odd coprime values $p_2,\ldots,p_\kappa$ (coprime also to $p_1$).
Now the question is, how big should we pick the coprime values $p_2,\ldots,p_\kappa$?

Again, we know $b_2 = p_2 \cdots p_\kappa$ and we also know that (assuming $\kappa>4$) that the size of $b_2$ will dominated by the term $p_1^2 \beta^2 (n-\kappa)$. Since $\kappa$ is tiny compared to $n$ we basically get something like $$ p_i^{\kappa-1} \approx p_1^2 n \beta^2. $$ So $$ \log p_i \approx \frac{2 \log (p_1 \beta) + \log n}{\kappa-1}. $$

Using $\beta = \sqrt{8 \pi}$ we see we need $$ \log p_i \approx 0.715 + \frac{\log n}{9}.$$ i.e. $$ p_i \approx 2 n^{1/9}.$$ However to obtain $\kappa=10$ such coprime values we would need $2 n^{1/9} \ge 31$, i.e. $n>2^{35}$. Which again is a large number of samples.

Using $\beta = 2^{32}$ we see we need $$ \log p_i \approx 5.286 + \frac{\log n}{9}.$$ i.e. $$ p_i \approx 198 n^{1/9}.$$ Any value of $n$ would result in such coprime values existing.

Summary of C.3

By weakening the approximation factors we can select kind of practical values for the coprimes $p_1,\ldots,p_\kappa$ and the value $\kappa$. We see that for Kyber, Dilthium and BGV the number of samples $m$ required is going to be very large to enable a choice of such coprimes, however for TFHE the $\beta$ value is so large that the existing of such coprimes is immediate, since this forces $b_2$ to be very large indeed.

Second Main Point: For small values of $\beta$ the number of samples required to enable the attack to work is going to be very large indeed.

Continueing with Section 3.3

Having picked our values for $p_1,\ldots,p_\kappa$ we have fixed our guess for $b_2$. But this guess may be wrong. Indeed it's probability of being correct is around $$ \frac{1}{\beta^2 p_1^2 (n-k)}. $$ So we need to keep performing the attack, tweaking the parameters via randomizing the input samples (as described above. Until the attack works.

So we reiterate our first main point from above

First Main Point (Recap): The complexity is at least $\beta^2$.

So if $\beta^2$ is large, as it is in TFHE this is already a no-go.

Let us continueing assuming $b_2$ is correct.

So having picked our coprime values we need to pick a value for $D$, which the paper says should be odd and $O((\log n)^2)$. For the moment let us assume this is picked.

We then set $$ M = 2 (c+1) D^2 b_2$$ $$ P = M^2/2$$ $$ u^2 = D^2 b_2$$

Now we need to fix $t^2$ which is defined as $$ t^2 = \frac{M}{2}-u^2.$$ This ensures that Condition C.2 is satisfied.

Note $$ \frac{t^2}{u^2} = \frac{M}{2 u^2}-1 = \frac{2 (c+1) D^2 b_2}{2 u^2}-1 = \frac{2 (c+1) D^2 b_2}{2 D^2 b_2}-1 = (c+1)-1 = c. $$ So Condition C.1 is satisfied already. The only thing in Condition C.1 we have not satisfied is having $\sqrt{c} \in (64 (\log n)^3, 65 (\log n)^3)$.

We then need to pick a value for $r$ from Condition C.4. The relevant inequalies are $$ M \le r \le \frac{P}{2 \log n} = \frac{M^2}{4 \log n} $$ and $$ r \le \frac{D q}{2 (\log n)^3}. $$ Note the second inequality imples the following $$ \frac{D q}{2 (\log n)^3} \ge M = 2 (c+1) D^2 b_2 $$ i.e. $$ q \ge 4 (c+1) D b_2 (\log n)^3 \approx 4 (c+1) D (\log n)^3 p_1^2 n \beta^2. $$ Plugging in our values above we see that we have $$ q \ge c' n \beta^2, $$ for some value $c'$ which we can ignore.

Third Main Point: Note, that this means the attack does not apply to TFHE's standard parameters, since we have $\beta \approx \sqrt{q}$, and the multiplication by $n$ results in $q$ being too small in TFHE for the attack to apply.

Fourth Main Point: The attack does not apply to Kyber, Dilithium or BGV as here the large value of $n$ needed (discussed above) implies the used value of $q$ used in these schemes is also too small.

In Condition C.7 the value of $r$ is actually chosen to be $$ r = \frac{u t^3}{4 \log n}. $$

The final parameter to pick is $s^2$, which is chosen from Condition C.5 by $$ s^2 = 2 u^2 t^2 + \epsilon. $$

There are then some extra conditions, Condition C.6 and C.7, which define ranges for various parameters. My understanding is that these impact the approximation factors which the algorithm obtains.

Summary from April 17th

  1. The algorithm definitely requires $O(\beta^2)$ repetitions. Thus for large $\beta^2$ (TFHE) this is infeasible. (First Main Point)
  2. For small $\beta$ values (Kyber, Dilithium, BGV) the algorithm requires a huge number of LWE samples $m$. (Second Main Point)
  3. The algorithm requires $q > c' n \beta^2$, which is either too high because $\beta$ is big (TFHE), or it is too high because $n = \ell+m+1$ is big (Kyber, Dilithium) (because $\beta$ is small due to the previous point). (Third/Fourth Main Points)
  4. Generating large numbers of samples from the fixed number of samples we have in public key schemes, creates larger values of $\beta$ than considered here. This makes the attack less practical.

Nigel Smart
April 17th 2024.

Update April 18th

Dave Archer asked me some questions related to BGV stlye FHE so I decided to have a more detailed look at this. For the description of BGV and the noise equations I refer to the relatively old paper of Gentry, Halevi and myself (called the GHS paper below) where we evaluate the AES circuit using BGV. However GHS only looks at plaintext modulus $p=2$, the extension of these formulae for other plaintext spaces was done in another paper of Costache and myself (called the CS paper below).

I use these papers as these are the ones I know best, so it is quicker to use them to do a quick-and-dirty analysis. More modern papers, with more tuned noise equations, will have a similar analysis, so the overall conclusions should roughly be the same.

The main difference between GHS/CS and perhaps more modern papers is that the secret key is given with a fixed hamming weight in GHS, whereas more modern papers performs rejection sampling on the secret key in order to obtain a secret key with low canonical norm. For both methods we can assume that they produce secret keys with the same low canonical norm, they just do it in different ways.

Recall the key points above:

Now in the GHS/CS papers the noise formulae for producing new encryptions are given, after all it is vital to understand how BGV operates in order to give these formulae.

The method for public key encryption produces ciphertexts whose noise term has canonical norm bounded by a constant called $B_{\mathsf{clean}}$. Roughly speaking we have $$ B_{\mathsf{clean}} = O(p \cdot \ell). $$ However, we can then perform a modulus switch to obtain a ciphertext, with a smaller ciphertext modulus $q$, whose noise term has canonical norm bounded by $2 B_{\mathsf{scale}}$. Roughly speaking we have $$ B_{\mathsf{scale}} = O(p \cdot \sqrt{\ell}). $$ The implied constants here in the big-Oh's are small integers (think fifty or less). When performing the modulus switch the smallest modulus we can use is something of size slightly roughly $4 \cdot B_{\mathsf{scale}}$.

This would result in a BGV scheme with

i.e. the $\alpha$ value would be the constant value of about $1/40$.

Recall the complexity of the attack is at least $O(\beta^2)$ so we would have a complexity of at least $O(p^2 \cdot \ell)$.

Fifth Main Point: BGV with large plaintext modulus (as used for example in the SPDZ protocol) is immune from the attack it seems.

Nigel Smart
April 18th 2024.

Update April 19th

The author published an update to his paper overnight:
Step 9 of the algorithm contains a bug, which I don’t know how to fix. 
See the updated version of eprint/2024/555 - Section 3.5.9 (Page 37) for details. 
I sincerely thank Hongxun Wu and (independently) Thomas Vidick for finding the bug today.
So the panic in lattice quarters is now over.
Nigel Smart
April 19th 2024.