3 ms·
I wrote my thesis on post-quantum public key cryptosystems, though I'm not currently a practitioner and haven't been academically active since ~2017 or so. With
by fractionalhare 6y ago
I wrote my thesis on post-quantum public key cryptosystems, though I'm not currently a practitioner and haven't been academically active since ~2017 or so. With those provisos in mind, I'll try to give the summary as I see it. As a basic tl;dr I'm skeptical of the paper. Crypto-twitter is lit up about this right now and as far as I can tell, harbors the same skepticism.
- For context and background: yes, there are well-established links between factoring problems and lattice problems. These links have been known from at least the early 90s. There are many complexity theoretic reductions between specific factoring problems and specific lattice problems, and the approximate variants of the latter. There hasn't been an arbitrary reduction yet, it's mostly on a problem by problem basis.
- That first bullet point means that this research is at least structurally built on, and engages with, prior work in the academic community. Schnorr in particular has been pursuing this since the 90s. Schnorr is an accomplished and established cryptographer.
- I consider the context of that second bullet point unfortunate, because it means the research gets outsized attention even though it is otherwise, as of now, unsubstantiated. It gives the paper a lot more charity than it would ordinarily receive.
- Critically: Schnorr has not empirically demonstrated a break in RSA. He has demonstrated - in theory - faster factoring methods using SVP and CVP solving techniques which rely on a reduction of the factoring problem.
- The paper may not be worthless even if it doesn't break RSA. If he has indeed found a polynomial time way to solve a subset of lattice (and factoring) problems, that will be impressive. I'll have to read the paper a few more times to come to a belief on this point though.
Many comparisons are being drawn online between Schnorr and Atiyah, because the latter kept insisting he found a proof of the Riemann Hypothesis towards the end of his life. It would be sad if this is the case for Schnorr, but it's personally what I believe at this time pending an empirical demonstration of his work and/or critical substantiation from the rest of the academic community. I'm skeptical of this result the same way I'm skeptical when highly established mathematicians publish purported proofs of long standing open problems.
- cleansingfire 6y agoAssuming it works, I'm interested in its limitations. At various complexity levels, there are subsets of problems that yield easily, like unsafe primes in RSA, or trivially, how I can instantly get one factor of an even composite. Schnorr's main novel claim here seems to be a speedup in finding the SVP and CVP in some cases (he explicitly acknowledges limitations.) A Proof Of Concept seems like it would be great to test for edge cases, and that's where I think the interesting bits are likely to be. Disclaimer: Not a mathematician or complexity theorist. Just here to learn, and glad to be corrected any time.