IACR News item: 21 May 2015
Jia Liu, Flavio Garcia, Mark Ryan
ePrint Reportthat 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.
Additional news items may be found on the IACR news page.