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

Ben Laurie ben at links.org
Wed Feb 1 22:40:31 EST 2012

On Wed, Feb 1, 2012 at 1:01 PM, Francois Grieu <fgrieu at gmail.com> wrote:
> On 01/02/2012 21:09, Jon Callas wrote:
>> As I remember Hal's protocol, it requires about eight megabytes of data to
>> be transferred back and forth to prove that you know the SHA1 hash. It's not
>> so much to be obviously absurd, but not efficient enough to be something
>> you'd want to do often.
> Close. If I get it correctly, it is a zero-knowledge proof, with one pass
> (leaving I guess <=50% odds of forgery)

Presumably a _lot_ less. Whilst you might be able to flip bits in the
computation and get away with it if you flip the right other bits, my
intuition suggests the combinations that don't work will vastly
outnumber those that do.

More information about the cryptography mailing list