3 ms·
Schnorr 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 v
by pbsd 6y ago
Schnorr 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...