[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.
http://video.google.com/videoplay?docid=-5745972992365920864

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?"
http://www.springerlink.com/content/0l4734h77615u161/
ftp://ftp.inf.ethz.ch/pub/crypto/publications/CraDam98.pdf
http://www.brics.dk/RS/97/27/BRICS-RS-97-27.pdf

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?

TIA,
  Francois Grieu



More information about the cryptography mailing list