3 ms·
If my understanding is correct, Schnorr converts the integer factorization problem to lattice problems: SVP and CVP. Then he claims he had an efficient algorith
by bcaa7f3a8bbc 6y ago
If my understanding is correct, Schnorr converts the integer factorization problem to lattice problems: SVP and CVP. Then he claims he had an efficient algorithm to solve this particular instance of SVP and CVP, thus RSA is destroyed. But, the hardness assumption of SVP and CVP in general is the very foundation that another branch of public-key cryptosystems - lattice-based cryptography - is built upon. So, if Schnorr's claims are true (uncertain and still to be determined), I can't stop to think about its impact on lattice cryptosystems: Can we use the same technique to attack them? I think it's a more important question than RSA [0] - lattice cryptosystems are the candidate for Post-Quantum Cryptography, meant to replace all of the existing public-key cryptosystems of today (e.g. RSA and ECC). Even if the attack is purely theoretical, if it can solve other instances of SVP and CVP, it'll certainly affect the security assessment of lattice-based PQC (e.g. NTRU, also LWE).
Of course, I don't know what I'm talking about.
[0] Factorization had a history of speedups, both theoretical and practical. It doesn't really affect the practical security but always comes at a cost of either decreasing confidence or constantly increasing the keysize, so I won't be too surprised if Schnorr really has new insights to speed it up further. In fact, "We need something with a better security record than RSA" was one of the main arguments for transitioning to ECC - which has already completed at large on today's Internet, RSA is only used for digital signature, almost all key exchanges are ECC now. You can't decrypt post-2016 web traffic by breaking RSA.
- pbsd 6y agoSchnorr got close to making such a claim in a previous version of the paper [1, Section 6]. Namely, that NTRU is close to being broken if a sufficiently short vector (it is not specified how short) is found. The main claim of Schnorr's, as far as I can gather, is that for lattices where the shortest vector(s) are much shorter than the maximum shortest vector(s) for the same dimension, i.e., low-density lattices, those vectors can be found in heuristic polynomial time with his enumeration approach. Now, low-density lattices are fairly common in cryptographic settings, where the solution, discoverable by finding shortest vectors, is unusually short/close relatively to what one would expect in a random lattice. As such, if true, I would expect Schnorr's idea to lead to more breaks than just RSA. But I don't personally think it's true. At the same time, I'm not a lattice expert, so make of that what you will. [1] https://www.math.uni-frankfurt.de/~dmst/research/papers/SVP2+1.pdf https://www.math.uni-frankfurt.de/~dmst/research/papers/SVP2...
- JoblessWonder 6y ago> Of course, I don't know what I'm talking about. I would honestly have no way of knowing either way. It is always fun to get a peek into people working out ideas in fields I have no experience in.
- k3liutZu 6y ago> It is always fun to get a peek into people working out ideas in fields I have no experience in. Phew. I'm not alone. I understood _some_ of the words used in the HN comments in this thread.
- bcaa7f3a8bbc 6y agoI noticed HN user fractionalhare has made a comprehensive reply to my questions, but it wasn't posted as a reply to me, so now it has fallen to the bottom of the page. You can see it here: https://news.ycombinator.com/item?id=26331747 https://news.ycombinator.com/item?id=26331747