Archive for July, 2011

Solving the symmetric key distribution problem for digital signatures using the BitCoin peer-to-peer infrastructure


It appears that the lead time to quantum computers is decreasing while the lead time for eliminating our amazingly widespread dependence on public key cryptosystems is increasing. So we should develop alternatives and quit creating new dependences. Here I discuss a small part of the problem, the digital signature protocol. The BitCoin peer-to-peer currency network happens to use an elliptic curve public key system to sign payment authorizations. Wikipedia says that this cryptosystem, although better than the system based on factoring large integers, is still vulnerable to quantum computer attack. But the BitCoin infrastructure (comprising among other things millions of dollars of privately owned and operated GPU’s distributed across the globe) also provides a way out of the problem, via its hashchain, a sort of distributed timestamp protocol.

Nothing here is particularly new, but as far as I know, the combination has not been proposed (or patented, I hope).

Instead of using public and private keys, we use public and private GUID’s together with a secure iterated hash function, hash(N, message) with 0 < hash() < H, and a secure symmetric key function crypt(message,key) with 0 < key < H.  The private GUID is pvt = hash(1, H * random()), and the public GUID is pub = hash(N, pvt) .

Suppose Alice wants to sign messages. She chooses a random private GUID pvt, stores it safely, and computes her public GUID  pub = hash(N, pvt), where N limits the number of signatures Alice can make using this GUID.

To sign her K-th message, Alice computes msghash = hash(1, message), sigkey = hash(NK, pvt), and sig = crypt(msghash, sigkey), and submits {pubK, sig} to the network together with a transaction fee in bitcoins. If the fee is large enough, and if the block chain does not already contain a signature with public GUID pub and a larger serial number K, the transaction will soon be included in a block.  After the transaction is verified, Alice discloses sigkey.  Anyone can compute msghash = crypt(sig, sigkey), verify that hash(K, sigkey) == pub, that crypt(msghash, sigkey) == sig, and given message, that hash(1, message) == msghash, but noone can use the newly disclosed sigkey to sign a different message unless they can succeed in subverting the blockchain.  Unlike a public key signature, this signature requires reference to the blockchain for verification, but when quantum computers arrive, the public key free lunch is over.

It should be possible to use this approach to enhance the digital signature used in the bitcoin protocol without increasing the verification latency time by including {pubK, sig} in the bitcoin transaction as well as the public key signature, and requiring publication of sigkey (but not necessarily inclusion of sigkey in the block chain) before the bitcoin transaction is accepted as verified.