[cryptography] Proving knowledge of a message with a given

Francois Grieu fgrieu at gmail.com
Wed Feb 1 13:20:17 EST 2012


Natanael wrote:

 > We do have zero-knowledge proofs, but AFAIK they do not use SHA1.

I'm not after a proof that "uses" SHA-1; I'm after a proof of a
message with given SHA-1 result, which is something very different.

 > http://en.wikipedia.org/wiki/Zero-knowledge_password_proof
 > http://en.wikipedia.org/wiki/Zero-knowledge_proof
 > http://en.wikipedia.org/wiki/Non-interactive_zero-knowledge_proof <--
 > Most likely what you want

Some of the techniques discussed here are close.
In particular, some zero-knowledge proof of the solution of a SAT
problem may fit the task, as it is easy to rewrite the problem
h=SHA-1(m) for known h and unknown m as a SAT problem with
some thousands clauses.

However I'm afraid that the proof size (or the amount of work/data
involved in the protocol) could grow beyond practicality. The talk
does hint that it was necessary to use optimizations, but I could
not extract enough information to understand which.

   Francois Grieu



More information about the cryptography mailing list