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

Francois Grieu fgrieu at gmail.com
Wed Feb 1 04:49:22 EST 2012

Alice discloses a 160-bit value h and claims that she (or
parties/devices she has access to) knows a message m with h=SHA-1(m).

Can she convince Bob of her claim using some protocol, without letting
Bob find m, and without a third party or device that Bob trusts?

At a Crypto'98 rump session, Hal Finney made a 7-minutes presentation "A
zero-knowledge proof of possession of a pre-image of a SHA-1 hash"
claiming a feasible protocol for this.

This talk mentions using the protocol in the Crypto'98 paper of Ronald
Cramer and Ivan B. Damgård: "Zero-Knowledge Proofs for Finite Field
Arithmetic or: Can Zero-Knowledge be for Free?"

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.

Any info on the Hal Finney protocol, or a protocol giving a similar
result, or the (in)feasibility of such a protocol?

  Francois Grieu

More information about the cryptography mailing list