Skip to content

Instantly share code, notes, and snippets.

@harding
Created July 23, 2018 11:44
Show Gist options
  • Save harding/bfd094ab488fd3932df59452e5ec753f to your computer and use it in GitHub Desktop.
Save harding/bfd094ab488fd3932df59452e5ec753f to your computer and use it in GitHub Desktop.
Description of Tim Ruffing's upgrade path to post-quantum in presence of QC attackers

Background: future fast Quantum Computers (QCs) are hypothesized to be much faster at solving various forms of the Discrete Log Problem (DLP) than classical computers (e.g. what we use now). Bitcoin uses the DLP in what's called a trapdoor function: a function that's easy to compute one way (a private key generating a public key) but hard to compute the other way (using a public key to recover the original private key). Fast QCs break that trapdoor, hypothetically allowing the operator of the QC to steal the bitcoins from anyone whose public key is publicly known.

However, although must bitcoins are ultimately controlled by public keys, in many cases those public keys aren't publicly known until someone broadcasts an unconfirmed transacting spening those bitcoins. That's because of an optimization Satoshi Nakamoto implemented in Bitcoin 0.1 to allow Bitcoin addresses to be around 25 bytes long rather than the 70 bytes he knew how to create another way (but which we could do equivilently in 38 bytes today since we know about compressed public keys). Nakamoto's optimization has the side effect of hiding public keys behind a hash until it's time to spend using them. Although QCs are a bit faster at compromising hashes than classical computers, the speed up isn't anywhere near as huge as it is for solving DLPs, so hashes of a certain strength will likely stay secure much further into the future.

We do know about other signature schemes with other trapdoor functions that make it incredibly hard for both classical computers and QCs to recover a private key from a public key, so Bitcoin users can ultimately upgrade to protect themselves against hypothetical future fast QCs. But there's still a problem at the point in time when we start to think that QCs have become fast enough to start recovering private keys: at that point, it's not safe to spend your bitcoins because spending requires you reveal your public key and that can allow the QC operater to double-spend your unconfirmed transaction.

Tim Ruffing's solution[1] allows you to generate a transaction you know you want to send in the future (e.g. moving your funds to a new signature scheme) and then publishing it to the block chain encrypted by your public key (which nobody but you knows at this point). This doesn't actually spend your funds, but it does allow the encrypted form of that transaction (which not even the QC operator can see) to get a bunch of confirmations and become essentially irreversible.

Then you release your public key to the block chain. This allows the QC operator to recover your private key, but it also allows everyone else to look for any previous transactions you encrypted with your public key
and use the earliest of those as the actual spend of your funds rather than anything that came later and which could've been created by the QC operator.

Thus Bitcoin users have an upgrade path even if the case of a sudden discovery that there exist fast QCs. (Note: to gain this protection, you can never reuse an address after you've spent from it. Really, you should try really hard to never use the same address twice anyway for privacy.)

[1] https://lists.linuxfoundation.org/pipermail/bitcoin-dev/2018-February/015758.html

@vinniefalco
Copy link

I love it when you talk dirty

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment