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.

Advertisements

2 Responses to “Solving the symmetric key distribution problem for digital signatures using the BitCoin peer-to-peer infrastructure”

  1. » First robotic underwater vehicle to be powered entirely by natural, renewable, ocean thermal energy Says:

    […] Archimedes Submerged jQuery.ajax({type:"GET",async:false,url:"http://www.InnovationToronto.com/wp-content/plugins/post-views/post-views.php&quot;,data:"cache_post_id=5045&cache_view_type=normal&cache_output_type=content",cache:false}); […]

  2. salinasmullen40682 Says:

    They just play prank in phone call that we charge 350rs, it just to pull customer in shop then they give false hope to customer and take huge money. like 12000, 8000 etc etc Come on http://tropaadet.dk/salinasmullen40682081845

Leave a Reply

Please log in using one of these methods to post your comment:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s


%d bloggers like this: