DEF CON 27 - Andreas Baumhof - Are Quantum Computers Really A Threat To Cryptography

Shor's Algorithm for factoring integer numbers is the big threat to cryptography (RSA/ECC) as it reduces the complexity from exponential to polynomial, which means a Quantum Computer can reduce the time to crack RSA-2048 to a mere 10 seconds. However current noisy NISQ type quantum computers are very limited to something like 16 bit RSA keys. And the quality of the current qubits is so bad that error-correction comes at a massive cost of at least 100 times the amount of qubits.

While the world is pre-occupied whether we have universal quantum computers big enough for Shor's algorithm, Quantum Annealing is stealing the show with having factored a 20-bit number just in January this year using 97 qubits. And these qubits are actually good enough to factor bigger numbers. If we assume a linear scalability, we'd "only" need around 10,000 qubits to factor a 2048bit RSA key. D-Wave announced a quantum computer with 5,640 qubits, so that puts it within reach soon.

So, could Quantum Annealing be more of a threat to cryptography than Shor's algorithm on universal quantum computers? How do these algorithms work? How do they achieve a polynomial complexity to what traditional computers need exponential time? What impact will this have on the competition from NIST for the design of post-quantum-cryptography algorithms? ... https://www.youtube.com/watch?v=J0ameQl0jWM