5 ms·
Can someone please correct me? We don't know polynomial CVP/SVP algorithms correct? In fact, isn't SVP an NP-Hard problem? Why would this "destroy" RSA?
by gnulinux 6y ago
Can someone please correct me? We don't know polynomial CVP/SVP algorithms correct? In fact, isn't SVP an NP-Hard problem? Why would this "destroy" RSA?
- dleslie 6y agoI'm not sure if this is the claim in the paper; but I'll try to explain in plain terms. Let's say you have an algorithm that can solve NP-hard problems in polynomial time with an N% success rate. What value of N makes the algorithm useful in practice depends on the practicality of its use as an attack against the NP-hard problem; there is an inflection point whereat the speed of the attack outstrips the speed at which the cypher can change secrets.
- gnulinux 6y agoI see, makes sense, thanks.