[cryptography] Proving knowledge of a message with a given
fgrieu at gmail.com
Wed Feb 1 13:20:17 EST 2012
> 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/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.
More information about the cryptography