9 ms·
Isn't it typical to release the paper first, for peer vetting, ahead of any actual working proof? It seems like the only reason for the "put up or shut up" re
by tyingq 6y ago
Isn't it typical to release the paper first, for peer vetting, ahead of any actual working proof?
It seems like the only reason for the "put up or shut up" reactions is that "destroys RSA" comment in the submitted abstract...which isn't in the actual paper.
- chrisseaton 6y ago> is that "destroys RSA" comment in the submitted abstract...which isn't in the actual paper I think it is - https://eprint.iacr.org/2021/232.pdf https://eprint.iacr.org/2021/232.pdf
- tyingq 6y agoAh, I see. It's been removed in a newer revision of the paper. https://www.math.uni-frankfurt.de/~dmst/teaching/WS2019/SVP9.pdf https://www.math.uni-frankfurt.de/~dmst/teaching/WS2019/SVP9...
- deleted 6y ago[deleted]
- m4lvin 6y agoThat times out for me, I guess www.math.uni-frankfurt.de is now getting more attention than usual ;-) Here is a version in the Google cache, it has an old date on it "work in progress 04.03.2020" and does not contain the "destroys RSA" sentence: https://webcache.googleusercontent.com/search?q=cache:E0L-S3UfRxUJ:https://www.math.uni-frankfurt.de/~dmst/teaching/WS2019/SVP9.pdf https://webcache.googleusercontent.com/search?q=cache:E0L-S3...
- bhaney 6y agoOther way around I think. Your link is an old version of the paper. The one on eprint was just updated today with a version of the paper that adds the "destroys RSA" line and removes the "work in progress" line (put it in the wayback machine to see the version that was there yesterday without the claim of destroying RSA)
- deleted 6y ago[deleted]
- dTP90pN 6y agoThe newer 12-page version on the preprint server has a PDF creation date of 3/3/2021, 11:32:56 AM, created with pdfeTeX-1.30.4. https://eprint.iacr.org/eprint-bin/getfile.pl?entry=2021/232&version=20210303:182120&file=232.pdf https://eprint.iacr.org/eprint-bin/getfile.pl?entry=2021/232... The previous (reportedly wrongly uploaded) version is from 12/5/2019, 9:10:13 AM created with pdfeTeX-1.30.4. https://eprint.iacr.org/eprint-bin/getfile.pl?entry=2021/232&version=20210302:203341&file=232.pdf https://eprint.iacr.org/eprint-bin/getfile.pl?entry=2021/232... The university website version is from 3/5/2020, 12:00:19 PM created with pdfTeX-1.40.15. These dates & times are MM/DD/YYYY & CET. A co-editor of the Cryptology ePrint Archive confirmed the submission on twitter: https://twitter.com/Leptan/status/1367103240228261894 https://twitter.com/Leptan/status/1367103240228261894
- itcrowd 6y agoThe factors could be included in the manuscript as an example..
- dragontamer 6y agoThe sum-of-three cubes announcement was tweeted pretty easily. https://twitter.com/robinhouston/status/1169877007045296128 https://twitter.com/robinhouston/status/1169877007045296128 Its easier to drum up support for your paper when you have a quick way to prove to the community of mathematicians that your results are golden. EDIT: The original webpage: http://math.mit.edu/~drew/sumsofcubes.html http://math.mit.edu/~drew/sumsofcubes.html As you can see, the sum-of-cubes announcements are very terse. Ultimately pointing to the following link: https://share.cocalc.com/share/900eec7e-0710-4e2f-a03a-dba01ca9bd8e/TheUltimateQuestion.ipynb?viewer=share https://share.cocalc.com/share/900eec7e-0710-4e2f-a03a-dba01... That kind of website / tweet is a "drop the mic" moment. It really makes people pay attention.
- coliveira 6y agoThat's not how science works. Yes, if your algorithm is simple enough and you can create an implementation, then it is good that you produce a working version. But it may be more complicated to implement the algorithm than writing a paper. This doesn't mean that the implementation is impossible.
- pdonis 6y ago> That's not how science works. This isn't science, it's math. As the article mentions, there is an 862-bit RSA challenge that hasn't been factored yet. Factoring it should be possible on commodity hardware if the claims in the paper are true. So why not just do it? The test of success is simple: either you win the challenge or you don't.
- winkeltripel 6y agoFor a skilled researcher it may be an order of magnitude easier to write the whitepapar than to code the implementation.
- salawat 6y agoThere are example factorizations around page 11 if I'm reading this correctly. Haven't run them through yet because I'm refreshing my atrophied linear algebra knowledge and walking through some of the source papers, so some work is in there.
- anonisko 6y agoThe whole paper is linked, https://eprint.iacr.org/2021/232.pdf https://eprint.iacr.org/2021/232.pdf
- croddin 6y agoHow broken does this claim RSA is? SHA-1 was known to be broken for a long time before actually pulling off a collision was performed for example.[1] [1]https://en.wikipedia.org/wiki/SHA-1#Attacks https://en.wikipedia.org/wiki/SHA-1#Attacks
- lowercase1 6y agoAn attack is anything that makes it take less than a brute force effort (of 2^80 operations). A 2^63 effort is really expensive in 2007. But by 2015 computation was maybe 2^5 times cheaper and there was a 2^5 cheaper attack. I believe that this breakthrough could be quite a bit bigger because it's changing the costs from exponential to polynomial and so speedup is likely a much bigger change.
- andrewla 6y agoFor something of this magnitude, I think the expected behavior would be to delay the release of the paper until the ecosystem had time to adapt. To prove the paper is valid (and to assert precedence) you would offer to factor several "nothing up my sleeve" numbers -- like sha512("schnorr1") + sha512("schnorr2"). As it is, if the algorithm presented is valid then this potentially compromises currently operating systems.
- dcow 6y agoI do not agree that so-called “responsible disclosure” would or should be the expected behavior. I do understand how someone accustomed to corporate bug bounties and private security mailing lists may think so, though. Full disclosure is a perfectly reasonable strategy especially when we’re operating in the academic realm. Industry always takes years to catch up to academia anyway.
- nine_k 6y agoIf this paper allows to produce a working RSA cracker in a month, much of high-value IT infrastructure is under imminent threat. Yes, you can replace your SSH keys with elliptic ones, and maybe adjust your TLS accepted algorithms. Even this is not always easy or cheap. But other things that may rely on RSA (or triple RSA) may have trouble upgrading fast, and upgrading them at all is going to cost a lot.
- martamorena2843 6y agoYeah, but also the industry knows for DECADES that RSA will likely be broken eventually. Not having reacted yet is not the researcher's fault. We know that Quantum computers can break it too, yet nobody really acts on it with any urgency. If suddenly there is a breakthrough and we can reach this state within a year, then there will be no time to adapt as well. It all boils down to the general corporate attitude of not fixing catastrophic problems without precedence. We see the same with climate change and once it hits hard, it will be too late to adapt.
- Klwohu 6y agoYou probably understand how serious this is, so many people are going to become very emotional as this strikes at the very foundations of the Internet and digital security as we know it. The reactions I've seen so far do seem very emotional and this will only become much, much worse if there's a PoC which is produced.
- not2b 6y agoWhat does emotion have to do with it? For many years, every time someone claims to have broken RSA the response is the same: here is a test case you (the alleged RSA breaker) should be able to crack if your claims are correct. Put up or shut up. That seems like a fair, just-the-facts response.
- ajarmst 6y agoInternet and digital security? This strikes at the very foundations of number theory.
- Jweb_Guru 6y agoEhhhhhhh. I'm not sure I'm aware of anything in number theory that would substantially change if a fast factoring algorithm were discovered, outside of its applications to cryptography. It'd be very likely that a fast factoring algorithm exposed some unusual structure about the natural numbers, I guess?
- ajarmst 6y agoI was exaggerating for effect, but yeah. The existence of a polynomial time prime factoring suggests the existence of a useful predictive pattern in the distribution of primes. That would break the Twin Prime Conjecture and possibly refute Riemann. Undermining those starts tearing the foundations apart. I’m almost certain that won’t have just happened.
- Jweb_Guru 6y agoWe already know there is plenty of structure in the distribution of primes, so I don't see why finding some that can be exploited by a clever algorithm makes that much of a difference to foundational concerns. In fact, I'm pretty sure that even a proof of P=NP, which obviously subsumes fast factoring, wouldn't have any intrinsically interesting non-algorithmic consequences for proofs in number theory that don't directly assume factoring is hard (but this could just be ignorance on my part); all the supposedly absurd consequences people point to like the PH collapsing are more or less restricted to computer science.
- jasonmp85 6y agoThis is math. The working proof _is_ the paper. It just takes a long time to refute if there’s a subtle error. “Putting up” ISN’T proof but it will sure get a lot of important people to drop what they’re doing and check the paper faster.
- roywiggins 6y agoI dunno, isn't a demonstration of a few factors proof that someone somewhere has broken RSA, or has a machine much more powerful than we'd expect to exist? It's not proof that any of the math in the paper is correct, but it doesn't have to be. Even if there's a subtle error in the proof-as-written it doesn't matter if the implementation actually works.
- nl 6y agoAll that is true. But if the author of the paper (or even someone else with a credible reputation) was to public factors and say they used this method then it's useful evidence.
- sellyme 6y ago"Putting up" isn't proof that an RSA decryption algorithm exists, but it is proof that someone has found a way to reverse RSA either way. The latter is much more important.
- KMag 6y agoI haven't looked into the details of the speed improvements... it's often the case that big-O improvements in complex problems come with bigger constant factors. It's entirely reasonable that this new algorithm is slower for factoring 384-bit numbers but faster for 4096-bit numbers. I wouldn't be surprised if a demonstration that pushes the current publicly known record for largest factored RSA modulus costs hundreds of thousands or millions of dollars even with this new algorithm, and the algorithm is also slower than other methods for, say 384-bit RSA. It may be difficult even for Peter Schnorr to get that kind of budget for a demonstration before his paper gets traction.
- ajarmst 6y ago
- dan-robertson 6y agoIf you really think your paper destroys RSA, I think there are ethical questions the authors must decide before publishing it. In particular, I think the right process would be: 1. Give some brief description of the result (eg factoring numbers in O(...)), and some proof (eg a factorisation of the next rsa semiprime, possibly more) that convinces people that your claims are true 2. Wait a while for people to have the chance to not be burned 3. Publish the paper Instead, the authors seem to be going for: 1. Publish the paper with a provocative abstract. 2. Wait to see who implements the algorithm first. It doesn’t seem the best idea to me, but what do I know?
- goalieca 6y agoUnlike a zero day, there still remain a number of important factors (haha) to actually break a large number. But crypto systems are special because they rely on trust. The mere sign of weakness is sufficient to kill that trust. A sufficiently resourced state actor may even be ahead.. we don’t know
- dcow 6y agoThe pursuit of knowledge should not be subject to any annoying effects said knowledge may have on people hedged against such knowledge becoming available. That’s an anti-liberal recipe for a rather dark society. I don't see the point in tone policing people generating knowledge just to remind them that sometimes knowledge is inconvenient.
- jrochkind1 6y ago"tone policing"? What do you think that phrase means? Who was talking about "tone"? Do you believe in "responsible disclosure" [1] of security vulnerabilities? How does your stated philosophy apply or not apply to ethics around disclosure of discovered software security vulnerabilities? Is that different? [1] https://cheatsheetseries.owasp.org/cheatsheets/Vulnerability_Disclosure_Cheat_Sheet.html https://cheatsheetseries.owasp.org/cheatsheets/Vulnerability...
- salawat 6y ago
- DennisP 6y agoAnd the article says it would take around a thousand CPU core years to break 800-bit RSA. Maybe Schnorr needs to publish first to get the budget for that.
- pdonis 6y ago> the article says it would take around a thousand CPU core years to break 800-bit RSA That's for previous algorithms, not the one described in the paper.
- ajarmst 6y agoHe doesn't need to demonstrate it with an 800-bit number. Given the claims made about how much faster this is, the effect should show up even in fairly small numbers.
- martamorena2843 6y agoThat can be solved within hours on a GPU cluster... Looking at a single core is usually not a great idea when you have billions of cores available.
- salawat 6y agoOnly if your algorithm is conducive to parallelism based speedup. Amdahl's law still applies. The paper mentions some gains being possible through parallelism with one of the algorithms their work is based on, but also mentioned most prior art is not effectively parallelizable across discrete machines.
- ajarmst 6y agoYep. A paper has to substantiate any claims made in the abstract, and this failure already undermines my confidence that the result is correct.
- baby 6y agoIt is in the actual paper. Also, without that sentence nobody would be trying to read the paper, so props to Schnorr who understands how to create the buzz :P