Re: Proving knowledge of a message with a given SHA-1 without disclosing it?

On 01/02/2012 22:40, Paul Rubin wrote:

Francois Grieu<fgrieu@xxxxxxxxx> writes:
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?

I don't know about zero-knowledge, but I'd expect from the PCP theorem
that there is a protocol that might leak some info about m. The amount
of leak would be bounded by k bits where Bob is supposed to be convinced
with confidence 1-2**O(k) that Alice has a preimage. Maybe the format
of m can be designed so that this bounded amount of leakage doesn't matter.

Or maybe a leak is not exploitable by Bob, because he is computationally
For example, if Alice discloses SHA-1(~m), she discloses 160 bits
about m, mostly additional to SHA-1(m). Yet it does not help a computationally
bounded Bob, to the best of the known techniques.

Francois Grieu