You can obviously prove it in the case where Alice claims she knows SHA-1(SHA-1(m)), which seems to be the same claim.
William > -----Original Message----- > From: cryptography-boun...@randombit.net [mailto:cryptography- > boun...@randombit.net] On Behalf Of Francois Grieu > Sent: Wednesday, February 01, 2012 4:49 AM > To: cryptography@randombit.net > Subject: [cryptography] Proving knowledge of a message with a given SHA-1 > without disclosing it? > > 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 > cryptography@randombit.net > http://lists.randombit.net/mailman/listinfo/cryptography _______________________________________________ cryptography mailing list cryptography@randombit.net http://lists.randombit.net/mailman/listinfo/cryptography
