[cryptography] Proving knowledge of a message with a given SHA-1 without disclosing it?

Jonathan Katz jkatz at cs.umd.edu
Wed Feb 1 17:32:29 EST 2012

On Wed, 1 Feb 2012, Nico Williams wrote:

> On Wed, Feb 1, 2012 at 3:49 AM, Francois Grieu <fgrieu at gmail.com> 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.

More information about the cryptography mailing list