Implications of the Proposed Quantum Attack on LWE

Updates to this post are at the bottom

• Update on April 16th
• Update on April 17th
• Update on April 18th
• Update on April 19th

Caveats

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

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:

• If $\alpha=0$ then one can interpret this as there being no error vector $\mathbf{e}$. Thus in such a situation the LWE problem is just normal linear algebra and naive algorithms can solve it in (essentially) quadratic time complexity.
• If $\alpha \approx 1$ then the equations are basically random, and no algorithm will be able to recover $\mathbf{s}$, as the equations contain essentially no information about $\mathbf{s}$ to aid in the recovery.

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

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 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

• $m \ge \Omega(n \cdot \log q)$,
• $q \in \tilde{\Omega}((\alpha \cdot q)^4 \cdot m^2)$.

Now let us consider this statement in more detail.

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

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 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.

Conclusion

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.

Update April 16th

1. One from reading the paper
2. One from discussion with Vadim Lyubashevksy

Update From Reading the Paper

Section 3.1

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

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

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?

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)$

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.

Update April 17th

• The first was the issue of having $p_2 \cdots p_\kappa = -1 \pmod{p_1}$. It turns out this was only done to avoid having to carry around another variable of $c' = p_2 \cdots p_\kappa \pmod{p_1}$. So we can ignore this.
• The second problem was the bound of $p_i \le (\log n)/p_1$ for $i>2$. If you impose this condition then there is simply not enough odd coprime $p_i$'s to make the algorithm work unless $n$ is super big, think $2^{10^x}$ for some largish $x$. Thus if you keep this condition then the algorithm is certainly not practically feasible in any sense of the word. Yilei pointed out to me that this condition is also not needed (except to get a nice approximation factor) and one can replace it with $p_i = O(\log n)$ and perhaps even $p_i \le 10 \log n$. In another direction one could take $\kappa = O(1)$ and perhaps $\kappa = 10$.

Revisiting Condition C.3

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$.

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$).

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

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

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.

Update April 18th

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.

• The canonnical norm bounds give us high probability bounds on the canonical norm of the noise term, these are roughly speaking (upto a small constant, a product of something called the ring constant in GHS and the inverse of the small constant obtained from the $\mathsf{erfc}$ function) the same as the $\beta$ values given above. So in what follows we will just assume the canonical norm bounds correspond to $10 \cdot \beta$, which equates to an error probability of around $2^{-80}$. This can be made more precise, but again with little change to the overall analysis.

Recall the key points above:

• If $\beta$ is small we need a lot of LWE samples $m$ to make the attack work, and in BGV the public key has a very small $\beta$, i.e. $\beta = \sqrt{8 \pi}$.
• But recall the discussion arising from a discussion with Vadim Lyubashevksy. To generate these extra samples itself increaes the noise value $\beta$.

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

• $\beta \approx 2 \cdot 50 p \sqrt{\ell}/10 = 10 p \sqrt{\ell} = O(p \cdot \sqrt{\ell})$.
• $q \approx 400 p \sqrt{\ell} = O(p \cdot \sqrt{\ell})$.

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.

Update April 19th

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.