4 ms·
> only methods based on Discrete Log are at risk, which includes RSA and ECC RSA's security is based on the presumption that factorization is hard, which is a
by steelframe 7y ago
> only methods based on Discrete Log are at risk, which includes RSA and ECC
RSA's security is based on the presumption that factorization is hard, which is a different problem than finding the discrete log. To attack RSA you would use Shor's algorithm, and to attack ECC you would use Grover's.
See page 2 of this paper:
https://arxiv.org/pdf/1804.00200.pdf https://arxiv.org/pdf/1804.00200.pdf
- ChrisLomont 7y agoSee my answer above. Shoes factoring is efficient because period finding mod N is exactly discrete log. To attack ECC it is directly discrete log, where quantum is exponentially faster than classical. Grover reduces unstructured search from O(N) to O(sort N), only a quadratic speedup, insufficient to weaken crypto more than 1 bit out of a key length, which is too weak to be a threat. Page 2 of your link does not state how QC attacks problems; it dies say ECC is discrete log, though. Both systems break precisely because QC solve DLP in these cases exponentially faster than classical, and this is all that’s needed.