On 02/01/2012 10:32 PM, Jonathan Katz wrote: > On Wed, 1 Feb 2012, Nico Williams wrote: > >> On Wed, Feb 1, 2012 at 3:49 AM, Francois Grieu <[email protected]> wrote: >>> The talk does not give much details, and I failed to locate any article >>> with a similar claim. >>> I would find that result truly remarkable, and it is against my >>> intuition. >> >> The video you posted does help me with the intuition problem. The >> idea seems to be to replace the normal arithmetic in SHA-1 with >> operations from a zero-knowledge scheme such that in the end you get a >> zero-knowledge proof of the operations that were applied to the input. >> That makes complete sense to me, even without seeing the details. >> But maybe I'm just gullible :^) >> >> Nico > > In some sense this is all not very surprising. The Cramer-Damgard > paper he cites in his talk describes a zero-knowledge proof for the > NP-complete problem of boolean circuit satisfiability. So the only > question is to express SHA-1 (plus a check for string equality) as a > boolean circuit and then apply their technique. And implement it, of > course. =) > > (Anyone have an estimate as to how many gates such a circuit would > have, assuming you are evaluating SHA-1 on a two-block input?) > > As he says in his talk, the point of the exercise is not to claim any > novelty for the resulting protocol, but to explore how efficient these > generic techniques can be when applied to circuits of practical > interest. Since he appears not to have written up the work, it is > unclear what additional optimizations could have been made. >
There have been recent developments in this area. The work in [1] shows ZK proofs for integer comparison and AES circuits. It is not fast. SHA-1 is (most likely) not going to be faster. [1] Essam Ghadafi, Nigel P. Smart and Bogdan Warinschi. "Practical Zero-Knowledge Proofs for Circuit Evaluation." 2009. http://www.springerlink.com/content/c432727520u07573/ _______________________________________________ cryptography mailing list [email protected] http://lists.randombit.net/mailman/listinfo/cryptography
