Does Schnorr's 2021 factoring method show that the RSA cryptosystem is not secure?

Question

Claus Peter Schnorr recently posted a 12-page factoring method by SVP algorithms. Is it correct?

It says that the algorithm factors integers $N \approx 2^{400}$ and $N \approx 2^{800}$ by $4.2 \cdot 10^{9}$ and $8.4 \cdot 10^{10}$ arithmetic operations.

Does this lead to the conclusion that the RSA cryptosystem is no longer secure in some sense?

---

Moderator note: a new paper was published 2021-07-08, replacing an earlier, withdrawn paper.

Answer 1

No.

If the claim was true, then there would be an extremely simple way to prove it: $10^{10}$ arithmetic operations is nothing. There are tons of 800-bit factoring challenges available online. The author could just solve them and include the factorization in the submission; the lack of such a straightforward validation should be taken as empirical evidence that the claim is, as of today, unsubstantiated at best.

Leo Ducas, one of the top experts in lattice-based cryptography (and especially in its cryptanalysis) has implemented the March 3 version of the paper. The preliminary experimental evaluations seem to indicate that the method cannot outperform the state of the art (quoted from here):

This suggest that the approach may be sensible, but that not all short vectors give rise to factoring relations, and that obtaining a sufficient success rate requires much larger lattice dimension than claimed in [Sch21].

Personnal study (unfortunately, never written down cleanly) of this approach suggested me that this approach requires solving SVP in dimensions beyond reasonable, leading to a factorization algorithm much slower than the state of the art. My impression is that this is the consensus among experts having spent some time on it as well.

The corresponding Twitter thread is here.

Furthermore, this Twitter thread points to what seems to be a fatal mistake in Schnorr's paper.

(Warning: personal view) I'm also basing my conclusion on the fact that several top experts on SVP and CVP algorithms have looked at the paper and concluded that it is incorrect (I cannot provide names, since it was in the context of anonymous reviews). Of course, the latter should not be treated as clear evidence, since I'm not providing proof of this statement - please treat it simply as it is, a claim I'm making.

(This statement refers to the version of the paper which was initially uploaded, and whose eprint extracted abstract contained a claim that RSA was "destroyed", together with the sample running times given in OP's question. Schnorr himself still claimed, after being asked by mail about the paper, that the latest version breaks RSA - and so does its abstract; with respect to this claim and given the lack of solved RSA challenge, I stand by my statement that it should be regarded as essentially unsubstantiated).

Among the potential issues (again to be treated with care, as pointers to help people willing to look further into where the paper might fail):

• The proof of (5.8) does only show the existence of many smooth triples, but says nothing about the probability of successfully finding factoring relations.
• The paper relies on the Schnorr-Hörner pruning strategy, which is known to be flawed.
• No justification is given for the cost indicated for (3.2)

Answer 2

Big issue at the bottom of page 2 where the determinant is quoted as $N^{n+1}\frac{n(n+1)}2 \ln n$ when it should be $N^{n+1} n! \ln n$. If this formula is used directly in the numerical estimates then are likely to be highly inaccurate.

UPDATE (5th March): I've taken a bit more time to work through the paper in detail. There's no asymptotic analysis of the complexity of the overall method and the striking claim seems to be based on a faulty numerical calculation that I cannot account for even with the corrected determinant expression. The calculation in question is at the bottom of page 3. In the sentence beginning "By theorem 6.2..." a bound is given for a vector $|\mathbf b_1|^2$ of the form $\gamma_k(\alpha\gamma_k^2)^{\frac{h-1}2}\mathrm {det}(\mathcal L(\mathbf R_{95,f}))^{\frac 2{96}}$ this formula is correct. However by the parameters of this section $k=24$ and so the Hermite constant $\gamma_{24}=4$, $\alpha=4/3$, $h=4$, $N\approx 2^{800}$, $n=95$ and so our determinant is roughly $2^{800*96}95!(800\ln 2)$. The quoted estimate for this bound in 0.8408696 whereas I estimate it to be greater than $10^{486}$, giving a bound for $\mathbf b_1$ of around $10^{243}$ and hence a bound for $|u-vN|$ of a similar order of magnitude. The ensuing input for the Dickman $\rho$ function is then around 90 and $\rho(90)\approx 10^{-202}$ and so this process would have to be repeated about $10^{202}$ times to produce enough fac-relations. The calculation for the $N\approx 2^{400}$ example is less complete, but I suspect a similar error.

The lattice theorems do seem sound and the above does not rule out a part of the parameter space that does perform better.

UPDATE (16 March): The new version now has a different scaling to the lattice ($N'=N^{\frac1{n+1}}$ in place of $N$. This drastically reduces the determinant. However the statement and proof of Lemma 3.1 are no longer clear. It is claimed that bounds on $|u-vN'|$ are produced which in turn makes it likely that numbers of size around $|u-vN'|$ are more likely to be smooth (note $N'$ is roughly 8-bit number in the example). However, to form fac-relations $|u-vN|$ is what needs to be smooth and this is of very different size ($N$ is a 800-bit number in our example). The factorial has been incorporated into the numerical example at the bottom of page 3, but the two figures quoted for $\mathrm{det}(R_{n/f})^{2/96}$ are $6.99\times 10^{10}$ and $2.13\times 10^{-3}$ whereas I calculate $95!^{\frac2{96}}N'^2(\log N)^{\frac2{96}}\approx 1.44\times 10^{8}$ and a corresponding bound on $|\mathbf b_1|^2 of 5.67\times 10^{10}$. If this could be converted into a bound on $|u-vN|$ of a commensurable size then the Dickman calculation is less daunting, however the old version of Lemma 3.1 is then quoted which bounds $|u-vN|$ rather than $|u-vN'|$. In conclusion shorter lattice vectors are being produced, but they don't seem to hold the same meaning as the previous construction.

Answer 3

The error in upper bounding the determinant of the matrix $\mathbf{R}_{n,f}$ by

$$N^{n+1} \frac{n(n+1)}{2} \ln N$$

instead of by $$N^{n+1} n! \ln N$$

seems to lead to an error in upper bounding the initial short vector by

$$\Vert \mathbf{b}_1 \Vert< \exp(2 \ln n/2)$$

instead of by $$\Vert \mathbf{b}_1 \Vert< \exp(\ln n)$$ which is an exponential relative error.

Later on it is stated on page 5 that

For short vectors $\mathbf{b}=\sum_{i=1}^n u_i \mathbf{b}_i \in \mathcal{L} \setminus \mathbf{0}$ the stages $u = (u_t, ..., u_n)$ have large success rate.

Unfortunately the actual initial vector may not be that short due to the indicated error in the bound.

Answer 4

This remark is about the eprint version 20210303:182120 and makes use of the notation defined therein.

Existing answers here have already pointed to the matrix $R_{n,f}$ defined at the bottom of page 2. It is given as

$$R_{n,f}=\begin{pmatrix} N f(1) & 0 & \cdots & 0 & 0 \\ 0 & \ddots & \ddots & \vdots & \vdots \\ \vdots & \ddots & \ddots & 0 & 0 \\ 0 & \cdots & 0 & N f(n) & 0 \\ N\ln p_1 & \cdots & \cdots & N\ln p_n & N\ln N \end{pmatrix} = [b_1,\ldots,b_{n+1}]$$

I would like to add the following observations:

• $N$ is a common factor in that matrix; the shortest vector coefficients $(e_1,\ldots,e_{n+1})$ with respect to that basis $R_{n,f}$ will be the same when that factor is omitted.
• The above suggests that there is a typo in the specification of $R_{n,f}$ or an incomplete simplification.
• Consider the $(n+1)$-th component of a lattice vector. This will be small only if $\prod_{i=1}^n p_i^{e_i} \approx N^{-e_{n+1}}$, thus $u/v\approx N^{-e_{n+1}}$. On the other hand, for $|u-Nv|$ to be small enough to have a reasonable chance of being smooth, we need $u/v\approx N$. This suggests the restriction $e_{n+1}=-1$. I do not find that restriction mentioned anywhere in the paper. Anyway, the only solutions worth considering would be those with $e_{n+1}\in\{\pm 1\}$, which remarkably exclude $e_{n+1}=0$, and if $e_{n+1}=+1$, then all other $e_i$ would need to have their signs flipped.
• Note that previous versions of the paper used a close-vector problem approach with slightly different lattice bases. The previous item suggests that there is an incompletely described attempt to turn a close-vector problem into a short-vector problem.