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 _______________________________________________ cryptography mailing list [email protected] http://lists.randombit.net/mailman/listinfo/cryptography
