IBM will soon launch a 53-qubit quantum computer

Re:IBM will soon launch a 53-qubit quantum computer by steelframe on Thursday September 19, 2019 @11:16AM (#21016989)

> 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

[ Parent | on HN ]

Re:IBM will soon launch a 53-qubit quantum computer by ChrisLomont on Thursday September 19, 2019 @10:39PM (#21022839)

See 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.

[ Parent | on HN ]