[Cryptography] quantum computers & crypto

Adam P. Goucher apgoucher at gmx.com
Fri Oct 29 22:12:46 EDT 2021


> And how long do you think it would take to implement and deploy PQC
> if the industry was not already prepared for it?  How long do you
> think it would take to roll back the millions upon millions of
> fraudulent transactions that likely would have been executed before
> someone pulled the breaker?  Remember, the scenario we are talking
> about here is a potential global compromise of all banking credentials.

Note that bigger quantum computers with more qubits and gates are harder
to build than smaller quantum computers with fewer qubits and gates.

So, if you're a Bond villain and you're building a quantum computer with
the intention to break industrial cryptography in order to steal money,
you'd start with the easiest target, which is 256-bit elliptic curve
cryptography.

(Since RSA is weaker against classical attacks than ECC for the same
keysize, everyone compensates by using much larger key sizes -- e.g.
2048-bit RSA. That makes them many times stronger against Shor's
algorithm than 256-bit ECC.)

Also, it's going to be expensive to run your quantum computer, so
you'd want to maximise 'bang for your buck' -- i.e. extort the most
money from solving that 256-bit ECDLP problem.

So, what fun things could you do with the ability to solve a single
ECDLP problem?

It looks like "creating malicious updates to Intel's microcode" is
not one of those, because they apparently use 3072-bit RSA for their
digital signatures. Maybe you could issue malicious software updates
to operating systems instead? Or take over a certificate authority
and start creating fake HTTPS certificates?

But no, there's a much more guaranteeably profitable thing that you
can do if you had a genie that gives you the solution to one ECDLP
problem: determine the private keys to the following Bitcoin address:

https://www.blockchain.com/btc/address/1P5ZEDWTKTFGxQjZphgWPQUpe554WKDfHQ

and walk away with 6 billion dollars of unspent transaction outputs.

In effect, that address is a canary in a coal mine: it being drained is
likely to be the first indicator of someone breaking 256-bit ECDLP
(either with a quantum computer or some clever unpublished mathematics).
And if/when that happens, you should really expedite a move to
post-quantum cryptography -- probably using the 'hybrid approach' where
you sign with the concatenation of an Ed448 elliptic curve signature
and a post-quantum Dilithium signature, just in case there's a
vulnerability in Dilithium.


Best wishes,


Adam P. Goucher


More information about the cryptography mailing list