20210303, 06:44  #1 
May 2003
Warsaw
3·5 Posts 
RSA cracked by SVP algorithms? (claim is disputed)
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 
20210303, 15:00  #2 
Apr 2010
151 Posts 
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.

20210303, 15:21  #3 
"Robert Gerbicz"
Oct 2005
Hungary
2×3^{2}×83 Posts 
An early slide from him: https://eurocrypt2009rump.cr.yp.to/e...a7ba36cf73.pdf
Forums about these claims: https://crypto.stackexchange.com/que...misnotsecur https://www.reddit.com/r/math/commen...ithms/gphobll/ 
20210303, 17:25  #4 
Bamboozled!
"πΊππ·π·π"
May 2003
Down not across
2^{2}×3×11×83 Posts 
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? 
20210303, 17:29  #5 
Apr 2010
151 Posts 
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 closeenoughlatticevector problem that helps generate smooth integers \(u\) and \(v\) such that \(u/v\) is close to the tobefactored integer \(N\). Then \(uvN\) 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 closeenough 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 closevectors 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 400bit and 800bit 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 machineword 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 polynomialcomplexity claim, but that seems to refer to the part that finds closeenough 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 morethanpolynomial slowdown (which I consider likely as Dickman's rho function will have a say there). 
20210303, 19:08  #6  
Aug 2006
3×1,993 Posts 
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:
Quote:
Last fiddled with by CRGreathouse on 20210303 at 19:09 

20210303, 21:15  #7 
6809 > 6502
"""""""""""""""""""
Aug 2003
101Γ103 Posts
2·3·1,669 Posts 

20210304, 15:20  #8 
Nov 2005
2×3×17 Posts 

20210305, 00:00  #9  
Apr 2012
Gracie on alert.
2^{4}×5^{2} Posts 
Quote:
Good thread with good links! Last fiddled with by jwaltos on 20210305 at 00:01 

20210305, 07:10  #10 
Apr 2012
Gracie on alert.
2^{4}·5^{2} Posts 
https://www.math.unifrankfurt.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. Last fiddled with by jwaltos on 20210305 at 07:22 
20210305, 09:46  #11 
Nov 2005
2·3·17 Posts 

Thread Tools  
Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
AMD hardware level debugger cracked  dans  Hardware  3  20101202 02:23 
EFF claim(s)  bearnol  Miscellaneous Math  58  20100905 17:48 
GIMPS may not claim $100,000  Mindnar  Lounge  28  20080827 16:22 
ECDLP cracked mathematically acc. Bearnol  bearnol  Miscellaneous Math  2  20060812 09:17 
Ramanujan math puzzle cracked at last  Jeff Gilchrist  Math  1  20050324 02:31 