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 _______________________________________________ cryptography mailing list [email protected] http://lists.randombit.net/mailman/listinfo/cryptography
