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

Francois Grieu fgrieu at gmail.com
Wed Feb 1 16:01:03 EST 2012


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) requiring 100 seconds and
22 kbytes of data (exchanged?), after some initial pre-computation
requiring 40 minutes and 6MBytes of data (storage?), on a PC as
it was circa 14 years ago.

That, and more, is at 6'52" in the talk at
http://video.google.com/videoplay?docid=-5745972992365920864

Hal Finney explains he got his result after careful optimizations,
rewriting some SHA-1 internal operations as arithmetic operations
in some appropriate field, rather than as boolean operations.
Everything he says is convincing, but in 7 minutes there is not much
detail, and so far I could not locate any later work (by him or others)
claiming a comparable result. So it is hard to rule out that some error
crept in his work.

   Francois Grieu



More information about the cryptography mailing list