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

Samuel Neves sneves at dei.uc.pt
Thu Feb 23 03:17:00 EST 2012

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 <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.

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.

More information about the cryptography mailing list