7
$\begingroup$

Is there a zero knowledge proof which demonstrates that Peggy knows a value v whose hash-function is w?

In my understanding of the general theorems on zero-k there EXISTS such a function if the has-function has polynomial time complexity. However, I would like to know how such the protocol would look like for the case of SHA-256. My problem is, that the usual proof requires me to reduce the fact of having a certain SHA-256 to Graph 3 Coloring, for example, and I do not see how this could be done practically.

Improve this question
$\endgroup$

2 Answers 2

Reset to default
7
$\begingroup$

In the rump session of Crypto 98, Hal Finney provided a talk which might be of your interest. The title is "A zero-knowledge proof of possession of a pre-image of a SHA-1 hash." I have not found any transcripts., but the video is available on both YouTube and Google Videos. (the videos are no longer available; see the comments below.) The video is now available from my Google Drive.

Improve this answer
$\endgroup$
3
  • $\begingroup$ the links no longer work. any chance you could summarize? $\endgroup$
    – mulllhausen
    Jan 6, 2014 at 11:30
  • $\begingroup$ @mulllhausen: As far as I understood, the idea is to use a special (malleable) commitment to the preimage, give the commitment to the verifier, and then replace the internal SHA-1 operations with special operations acting on the commitments. Finally, the verifier gives back the result to the prover, who decommits it, and shows it to equal to the SHA-1 image. Hal Finney does not give much detail into what the commitment and the special operation are, but concludes that the implementation took a few hours to execute. I'll upload the video on some temporary file hosting, and post the link next... $\endgroup$
    – Sadeq Dousti
    Jan 8, 2014 at 23:44
  • 1
    $\begingroup$ @mulllhausen: I uploaded the video here, so that you can watch it for yourself. Please note that this is a temporary file hosting, and will be deleted after 14 days. $\endgroup$
    – Sadeq Dousti
    Jan 8, 2014 at 23:45
2
$\begingroup$

There is an elegant and rather efficient zero-knowledge protocol for these kinds of NP statements given in this paper:

In fact, SHA-256 preimage is the example they list in the abstract. Maybe this old question inspired their paper? ;)

The protocol is based on garbled circuits. There is also some more recent relevant followup work optimizing the garbled circuit constructions that can be used in this protocol:

Using the privacy-free garbling scheme in our latest paper, a zero-knowledge proof for one round of SHA-256 involves sending 1.5MB of garbled circuit data (with 128-bit secure garbling) plus a small number of oblivious transfers. I don't think the numbers I have for SHA-256 reflect a circuit that has been optimized for garbling, though.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.