Paper 2015/482

Time-release Protocol from Bitcoin and Witness Encryption for SAT

Jia Liu and Flavio Garcia and Mark Ryan

Abstract

We propose a new time-release protocol based on the bitcoin protocol and witness encryption. We derive a ``public key'' from the bitcoin block chain for encryption. The decryption key are the unpredictable information in the future blocks (e.g., transactions, nonces) that will be computed by the bitcoin network. We build this protocol by witness encryption and encrypt with the bitcoin proof-of-work constraints. The novelty of our protocol is that the decryption key will be automatically and publicly available in the bitcoin block chain when the time is due. Witness encryption was originally proposed by Garg, Gentry, Sahai and Waters. It provides a means to encrypt to an instance, $x$, of an NP language and to decrypt by a witness $w$ that $x$ is in the language. Encoding CNF-SAT in the existing witness encryption schemes generate poly(n*k) group elements in the ciphertext where n is the number of variables and k is the number of clauses of the CNF formula. We design a new witness encryption for CNF-SAT which achieves ciphertext size of 2n+2k group elements. Our witness encryption is based on an intuitive reduction from SAT to Subset-Sum problem. Our scheme uses the framework of multilinear maps, but it is independent of the implementation details of multilinear maps.