RSA cracked by SVP algorithms? (claim is disputed)

[kubus]

Claus Peter Schnorr just posted a paper in which he claims to have broken RSA. Has anyone looked into it?
Fast Factoring Integers by SVP Algorithms

[ccorn]

Better look at the more recent draft. I do not consider it likely that Schnorr himself would have posted such an outdated (and apparently haphazardly edited) version.

[R. Gerbicz]

An early slide from him: https://eurocrypt2009rump.cr.yp.to/e...a7ba36cf73.pdf

Forums about these claims:
https://crypto.stackexchange.com/que...m-is-not-secur
https://www.reddit.com/r/math/commen...ithms/gphobll/

[xilman]

Someone whom I respect greatly told me that he had received that information from several others to whom it was new, including me.

His view is that it is unlikely to pan out in reality any time soon, being yet another elaboration of one of Schnorr's ideas.

But who knows?

[ccorn]

Here is my superficial impression, gathered from the PDFs linked at the university's lattice algorithms course page. I might be wrong. Better consult the linked resources directly.

There is a known construction of a close-enough-lattice-vector problem that helps generate smooth integers \(u\) and \(v\) such that \(u/v\) is close to the to-be-factored integer \(N\). Then \(|u-vN|\) is (relatively) small and, if smooth, gives rise to a relation mod \(N\). Enough such relations can be combined in the usual way, using linear algebra over GF(2) on the exponent vectors, to construct congruent squares mod \(N\), which are then used to find a (probably nontrivial) factor of \(N\).

I find it worth remarking that the method does not require proven shortest or closest lattice vectors to be found; in fact it needs to find and examine several close-enough lattice vectors in order to gather enough relations. It does so by looking at many (but not too many) enumerated lattice vectors and by tweaking the lattice.
Thus, keywords like SVP or CVP are a bit misleading; their presence is justified merely by the fact that algorithms for those problems have been adapted to solve a related problem.
Anyway, the factor base size and thus the number of relations needed are claimed to be far lower than for typical NFS scenarios. The crux is then to do the close-vectors search efficiently.

Over the last decade, progress has been made in the lattice methods used, reducing the computational effort per relation found. The latest version of the method is claimed to use far less arithmetic operations than QS or NFS for 400-bit and 800-bit numbers. The abstract says that that means "much faster", but the body text cautions that the bit length of the operands is much larger. If I interpret that correctly, this means that the number of machine-word arithmetic operations is not something to brag about yet.
In any case, I'd like to see the method demonstrated with a solution to some \(n\)-bit factorization challenge with \(n\) between 400 and 800.

There is also a polynomial-complexity claim, but that seems to refer to the part that finds close-enough lattice vectors, subject to some assumptions. If I am not mistaken, that estimate does not cover the smoothness filter that produces relations, so there might still be a more-than-polynomial slowdown (which I consider likely as Dickman's rho function will have a say there).

[CRGreathouse]

I think it's really exciting to see someone trying (slightly) new things in this space -- since the 90s all we've been doing is tweaking the number field sieve. But he's pretty straightforward about the benefits, as corn points put above:

The number of arithmetic steps of our factorisation is quite small compared with QS and NFS factorisation but the bit length of integers is large.

That is, there's no claim that the number of bit operations stays the same let alone decreases. So I think this is better thought of as a jumping-off point for research than as a useable method. But who knows, I could be wrong! Maybe a careful implementation could beat other algorithms in some ranges, perhaps even in a neighborhood including \infty.

[Uncwilly]

Originally Posted by xilman

Someone whom I respect greatly

Agsapiens?

[ThiloHarich]

There is a german statement on heise.de

https://www.heise.de/news/RSA-zersto...t-5071387.html

[jwaltos]

Originally Posted by CRGreathouse

.. since the 90s all we've been doing is tweaking the number field sieve..

No. We've not all been doing that, tweaking a sieving a process then "black-boxing" it..focusing on and optimizing black box processes.

Good thread with good links!

[jwaltos]

Originally Posted by jwaltos

Links

https://www.math.uni-frankfurt.de/~d...ch/papers.html
Here's a link to some older papers. Perhaps some of these may help in correlating past results within the present paper. I'm trying to understand what the breakthrough is. I have some familiarity with
the subset sum problem, LLL and variants and computational complexity. Instead of clarity I'm navigating inscrutability. This paper and its antecedents remind me of some papers regarding the resolution of the abc conjecture by another distinguished professional, Shinichi Mochizuki.

[ThiloHarich]

Somebody tried to implement it

https://github.com/lducas/SchnorrGate