<p>In the rump session of Crypto 98, <a href="http://finney.org/~hal/" rel="nofollow">Hal Finney</a> 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.<s>, but the video is available on both <a href="http://www.youtube.com/watch?v=2jQsSIdGTwo" rel="nofollow">YouTube</a> and <a href="http://video.google.com/videoplay?docid=-5745972992365920864" rel="nofollow">Google Videos</a>. (the videos are no longer available; see the comments below.)</s> The video is now available from my <a href="https://drive.google.com/file/d/0BxSJdYnjz8zdVG9qR0xiX191V28/view?usp=sharing" rel="nofollow">Google Drive</a>.</p>

CC BY-SA 3.0
2014-01-06T11:30:23.053Z
the links no longer work. any chance you could summarize?
mulllhausen
CC BY-SA 3.0
2014-01-08T23:44:01.860Z
@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...
Sadeq Dousti
CC BY-SA 3.0
2014-01-08T23:45:52.743Z
@mulllhausen: I uploaded the video [here](http://www.fileconvoy.com/dfl.php?id=gedec10fb4a58cced9994404442c2b677ac88b8b92), so that you can watch it for yourself. Please note that this is a temporary file hosting, and will be deleted after 14 days.
Sadeq Dousti
CC BY-SA 3.0
2011-09-30T14:34:46.410Z
2014-12-05T10:55:13.700Z
2014-12-05T10:55:13.700Z
Sadeq Dousti
<p>There is an elegant and rather efficient zero-knowledge protocol for these kinds of NP statements given in this paper:</p>

<ul>
<li>Marek Jawurek, Florian Kerschbaum, Claudio Orlandi: <a href="http://eprint.iacr.org/2013/073" rel="nofollow">Zero-Knowledge Using Garbled Circuits: How To Prove Non-Algebraic Statements Efficiently</a> (CCS 2013)</li>
</ul>

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

<p>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:</p>

<ul>
<li><p>Tore Kasper Frederiksen, Jesper Buus Nielsen, Claudio Orlandi: <a href="http://eprint.iacr.org/2014/598" rel="nofollow">Privacy-Free Garbled Circuits with Applications To Efficient Zero-Knowledge</a> (manuscript)</p></li>
<li><p>Samee Zahur, Mike Rosulek, David Evans: <a href="http://eprint.iacr.org/2014/756" rel="nofollow">Two Halves Make a Whole: Reducing Data Transfer in Garbled Circuits using Half Gates</a> (manuscript). Disclaimer: self promotion alert!</p></li>
</ul>

<p>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.</p>

CC BY-SA 3.0
2014-12-07T07:30:17.260Z
2014-12-07T07:43:26.593Z
2014-12-07T07:43:26.593Z
mikero
<p>Is there a zero knowledge proof which demonstrates that Peggy knows a value v whose hash-function is w?</p>

<p>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.</p>

<cr.crypto-security><hash-function><zero-knowledge>
Zero knowledge proof for value of a hash function
Clion
# Zero knowledge proof for value of a hash function

(Asked by: username_0 on 2011-09-27)

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.

**Tags:** cr.crypto-security, hash-function, zero-knowledge


---

## 2 answers

### Answer by username_1 on 2011-09-30. Score: 7

In the rump session of Crypto 98, [Hal Finney](http://finney.org/~hal/) 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](http://www.youtube.com/watch?v=2jQsSIdGTwo) and [Google Videos](http://video.google.com/videoplay?docid=-5745972992365920864). (the videos are no longer available; see the comments below.)~~ The video is now available from my [Google Drive](https://drive.google.com/file/d/0BxSJdYnjz8zdVG9qR0xiX191V28/view?usp=sharing).

> **Comments:**
> **username_2**: the links no longer work. any chance you could summarize?  
> **username_1**: @username_2: 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...  
> **username_1**: @username_2: I uploaded the video [here](http://www.fileconvoy.com/dfl.php?id=gedec10fb4a58cced9994404442c2b677ac88b8b92), so that you can watch it for yourself. Please note that this is a temporary file hosting, and will be deleted after 14 days.  

---

### Answer by username_3 on 2014-12-07. Score: 2

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

* Marek Jawurek, Florian Kerschbaum, Claudio Orlandi: [Zero-Knowledge Using Garbled Circuits: How To Prove Non-Algebraic Statements Efficiently](http://eprint.iacr.org/2013/073) (CCS 2013)

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:

* Tore Kasper Frederiksen, Jesper Buus Nielsen, Claudio Orlandi: [Privacy-Free Garbled Circuits with Applications To Efficient Zero-Knowledge](http://eprint.iacr.org/2014/598) (manuscript)
* Samee Zahur, Mike Rosulek, David Evans: [Two Halves Make a Whole: Reducing Data Transfer in Garbled Circuits using Half Gates](http://eprint.iacr.org/2014/756) (manuscript). Disclaimer: self promotion alert!

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.


---

