Cryptology - Fast Factoring Integers by SVP Algorithms "destroys RSA"

[bahamagreen]

TL;DR Summary

Claus Peter Schnorr paper
Secret-key cryptography / Primal-dual reduction, SVP, fac-relation
Claims this destroys the RSA cryptosystem

The summary abstract (describes the method) and full paper are linked.

Summary abstract

https://eprint.iacr.org/2021/232.pdf

 

[phyzguy]

Big claims. I'm not knowledgeable enough to know if this really "destroys the RSA cryptosystem", but I'm sure there are people on this forum who can comment. I'm interested to hear what they think.

 

[fresh_42]

If N. Gama and P.Q. Nguyen, Predicting lattice reduction, in Proc. EUROCRYPT 2008, LNCS 4965, Springer-Verlag, pp. 31–51, 2008 did the job and only needed an improvement, then we would have heard about it earlier.

So my personal bet is a flaw, possibly one which isn't easy to find.

 

[bahamagreen]

Me, too.
The abstracts are not just different in what is written... they have different dates.
The linked abstract alone is "Date: received 1 Mar 2021, last revised 3 Mar 2021"
The PDF linked paper with the different abstract is "work in progress 31.10.2019"

 

[PeterDonis]

my personal bet is a flaw

I'm not sure there is necessarily a flaw in the actual math, just in the claim that this result "destroys the RSA cryptosystem". The paper is claiming much shorter times for factoring 400-bit and 800-bit numbers than current methods (looks like about 8 orders of magnitude speed-up), but it doesn't appear to give a general result for the time complexity of the algorithm, so we don't know if the same speed-up will hold for 2048-bit or 4096-bit numbers, which are the current bit lengths normally used for RSA.

 

[fresh_42]

I'm not sure there is necessarily a flaw in the actual math, just in the claim that this result "destroys the RSA cryptosystem".

This doesn't rule out the other possibility. However, I have to admit that I'm biased, which is why I said personal opinion.

 

[PeterDonis]

An interesting post about how the claimed capabilities of the algorithm described in the paper could be tested:

 

[fresh_42]

The linked abstract alone is "Date: received 1 Mar 2021, last revised 3 Mar 2021"
The PDF linked paper with the different abstract is "work in progress 31.10.2019"

An interesting post about how the claimed capabilities of the algorithm described in the paper could be tested:

I think we will have to take his age into account. This could explain the differences on the time table as well as the missing capability to test the algorithm. Of course this is speculative, and I'm not saying we have a similar case as Atiyah and RH here. But the parallels come to mind.

 

[PeterDonis]

the missing capability to test the algorithm

If the article I linked to is correct that the testing can be done on commodity hardware, I don't think it will be long before somebody tries it, even if Schnorr himself doesn't.

 

[mfb]

How can you declare "destroys RSA" without a practical demonstration?
If you make a revolutionary claim that would be easy to demonstrate - and then you don't... it's pretty clear the claim is wrong.

 

[Keith_McClary]

Asked on crypto.stackexchange.com :
Does Schnorr's 2021 factoring method show that the RSA cryptosystem is not secure?

 

[fresh_42]

There is another strange fact: Schnorr and Shamir know each other personally, so I would have expected something more than "This destroys the RSA cryptosystem." in the abstract of an unpublished paper.

 

[Vanadium 50]

I like "Show me the factors" from the Medium article title. And we already know Shor's Algorithm destroys RSA. Why not Schnorr's?

But anyway, there are plenty of RSA challenges out there. I'd find it more convincing if we had a demonstration.

 

[aheight]

Here's the Cryptography Stack Exchange link about testing the method in "Sage":

Does Schnorr's factoring method work:

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 (in Sage). The preliminary experimental evaluations seem to indicate that the method cannot outperform the state of the art (quoted from Sage code to test algorithm):

However, further:

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

Would anyone be interested in downloading the Sage code and running it for say $N=7919*7727$ and reporting the results here or just explaining what the output below means? I would do so myself if I knew how to interpret the results.

Results of running the Sage code:

Running b=10, n=47, t=1000, we obtained 353 Factoring Relation found out of 1000 trials.
Running b=20, n=47, t=1000, we obtained 65 Factoring Relation found out of 1000 trials.
Running b=40, n=47, t=1000, we obtained 0 Factoring Relation found out of 1000 trials.

 

[Stephen Tashi]

Would a practical fast factoring algorithm have implications for cryptocurrencies?

 

[Office_Shredder]

From my understanding this would not affect bitcoin, but there might be some crypto currency relying on hard factoring in some way.