25
$\begingroup$

We consider a public hash function $H$, assumed collision-resistant and preimage-resistant (for both first and second preimage), similar in construction to SHA-1 or SHA-256.

Alice discloses a value $h$, claiming that she (or/and parties she can communicate with or/and devices they have access to) knows a message $m$ such that $H(m)=h$. Can some protocol convince Bob of this claim without help of a third party/device that Bob trusts, nor allowing Bob to find $m$?

At Crypto 98 rump session, Hal Finney made a 7-minutes presentation A zero-knowledge proof of possession of a pre-image of a SHA-1 hash which seems to be intended for that. This remarkable result is occasionally stated as fact, including recently here and next door. But I do not get how it is supposed to work.

Update: This talk mentions using the protocol in the Crypto'98 paper of Ronald Cramer and Ivan B. Damgård: Zero-Knowledge Proofs for Finite Field Arithmetic or: Can Zero-Knowledge be for Free? (this version is very similar, or there is this earlier, longer version).

Improve this question
$\endgroup$
7
  • $\begingroup$ I could not find any article that supported his talk in the rump session. Do you have an access to any such article. I would be very much interested in that because it sounds like a challenging problem especially when one sees hash function in the random oracle model. Maybe, then I could be of some help. $\endgroup$
    – Jalaj
    Jan 28, 2012 at 17:58
  • 1
    $\begingroup$ I went beyond what was in the talk. I think that considering a RO-model and solving this problem will be a theoretically great result. $\endgroup$
    – Jalaj
    Jan 29, 2012 at 2:51
  • $\begingroup$ My current intuition is that no practical protocol can rightly convince Bob of Alice's claim, for that very protocol would be able to distinguish $H$ from a random oracle, something that was never done for SHA-1 (restricted to messages of constant length). I reason that in the random oracle model, the only way for Bob to be convinced that the oracle outputs $h$ for message $m$ is to submit it himself, which implies knowledge of $m$. $\endgroup$
    – fgrieu ♦
    Jan 29, 2012 at 9:38
  • 1
    $\begingroup$ The protocol can allow Bob to distinguish $H$ from a random oracle, but it requires Alice's input. I don't think that contradicts indistinguishability. For example, Elgamal is IND-CPA-secure but also admits proofs of plaintext knowledge. Alice could allow Bob to distinguish ciphertexts he couldn't on his own. In any case, no implemented hash function can act as a random oracle in the real world. $\endgroup$
    – PulpSpy
    Jan 30, 2012 at 2:02
  • 3
    $\begingroup$ The hash design needs to be known so both parties can follow the progress through the circuit. I don't think we can always have something real-world practical (it isn't claimed in the talk that we can; only that we can for SHA-1). It depends on how well the function lends itself to certain tricks for speeding up the proof. What he did was as much art as science in converting SHA-1 into a blend of boolean/arithmetic circuitry. $\endgroup$
    – PulpSpy
    Jan 30, 2012 at 15:12

3 Answers 3

Reset to default
12
$\begingroup$

Yes, there are general zero-knowledge proofs for all statements in NP.

This result dates back to a paper by Oded Goldreich, Silvio Micali and Avi Wigderson from 1986. The basic idea is to give a zero-knowledge proof for graph 3-coloring, which is NP-complete, i.e., every other statement in NP can be encoded in it.

And the statement $\exists m. H(m) = h$ is clearly a NP statement: If you have $m$, you can check the statement in polynomial time (by computing the hash function).

We need to be careful a little though. What you ask for is not just a zero-knowledge proof but a "zero-knowledge proof of knowledge" because the prover wants to prove not only that such a $m$ exists but also that it "knows" one. But this problem can be addressed as well (see Section 7 in the third tutorial below).

If you're interested in understanding zero-knowledge proofs, I recommend these three tutorials, which explicitly consider of general proofs for NP statements (in increasing order of technicality):

As far as I understand, the motivation of Hal Finney's talk was to demonstrate how (im)practical general zero-knowledge proof system were back then. But this is 20 years ago, and things have improved tremendously. We're certainly getting close to practicality, even when the proof should be non-interactive, i.e., the prover just sends a single message.

If you're looking for practical protocols today, the most efficient candidates are STARKs, Bulletproofs, Ligero, BCCGP16, WTSTW17, and ZKBoo. For example, ZKBoo is pretty fast (in the order of a few milliseconds for proving and verifying), and Bulletproofs are much slower but are interesting proof size is very crucial. WTSTW17 contains a nice performance comparison. (This discussion ignores proof systems, which require a trusted setup. With trusted setup, the proofs can be made even more efficient, see libsnark for a nice overview.) A good resource for keeping track of recent developments is https://zkp.science/.

Improve this answer
$\endgroup$
2
  • $\begingroup$ Neither of those are the most efficient techniques time wise. MPC in your head (e.g. Zkboo github.com/Sobuno/ZKBoo) or zkSNARKs are both faster to prove, much faster to verify, and in the case of SNARKs, much smaller. $\endgroup$
    – imichaelmiers
    Apr 8, 2018 at 3:11
  • $\begingroup$ edited, feel free to add more $\endgroup$
    – real-or-random
    Apr 8, 2018 at 9:48
10
$\begingroup$

I'm not sure what I can add that wasn't covered in the talk. The approach is that Alice commits to the preimage and sends the commitment to Bob. The commitment has homomorphic properties, meaning it is possible to do computation on the value.

For example, if Alice commits to $x$ and $y$, Bob may be able to compute a commitment to $z$ where $z=f(x,y)$ for some function $f$. For example, if the commitments are additively homomorphic, Bob can add two commitments or multiply by a constant for free.

Alternatively, $f$ may not be directly computable. In this case, Alice who knows the actual values computes $z$, sends a commitment to $z$ to Bob asserting that it is correct. Bob holds commitments to $x$, $y$, and $z$; as well as knowing $f$. Alice can then interactively prove that for $f$, the commitment containing $z$ does contain the correct output for the inputs contained in the commitments to $x$ and $y$.

The Cramer-Damgaard paper shows how to do these proofs for a simple Turning-complete set of both boolean and arithmetic gates (for example, NAND and modular addition/multiplication).

The size of the circuit implementing SHA-1, expressed with only NAND gates for example, will be very large and infeasible. The art to doing the proof in practice is breaking it into subprotocols that are best represented by either boolean or arithmetic circuits and switching between the proof systems as appropriate. For certain SHA operations, he works at the bit level with boolean operations and for other operations, he works with integers in a finite field.

Improve this answer
$\endgroup$
5
  • 1
    $\begingroup$ Do you feel confident that the answer to the question is a clear "yes, using the techniques in the Cramer-Damgård paper"? Or something weaker? I get that there is no evidence of impossibility. $\endgroup$
    – fgrieu ♦
    Jan 30, 2012 at 12:54
  • 2
    $\begingroup$ An unbounded Alice can always prove. A bounded Alice can only prove when the circuit complexity of the hash has the same bound. A real-life Alice can only prove if she can generate a relatively simple description of the circuit with operations that have efficient zero-knowledge proofs. The latter is the case with SHA-1, but necessarily other hash functions. $\endgroup$
    – PulpSpy
    Jan 30, 2012 at 15:08
  • $\begingroup$ I guess the above is intended to read "but not necessarily other hash functions", and otherwise is supportive that a practical protocol can be devised in the case of SHA-1 as claimed in the talk. I'm still a tad skeptical, on these (admittedly weak) arguments: 1) such a protocol is something we can't devise in general for a perfect hash, yet we are computationally unable to distinguish SHA-1 (with fixed message size) from a perfect hash, other than by the fact that it is SHA-1; 2) details on the talk's method are scarce; 3) this remarkable result does not appear to have been reproduced. $\endgroup$
    – fgrieu ♦
    Jan 30, 2012 at 20:10
  • $\begingroup$ @fgrieu: 3) Do you have use cases where this construction would be useful (and more desirable than a ZKPoK of a plaintext)? $\endgroup$
    – bob
    Oct 13, 2012 at 19:49
  • $\begingroup$ @bob: to be honest, no I do not have a use case. My interest at that point is purely theoretical. $\endgroup$
    – fgrieu ♦
    Oct 15, 2012 at 11:14
4
$\begingroup$

I wanted to comment on PulpSpy's answer, but my comment turned out to be too large!

I have an intuitive understand why they does not stick to the idea of using Boolean circuits alone for all the proofs which I am writing it down here. I might be wrong and I would like to be cross examined on this.

There will be an issue with the boolean and arithmetic circuits. I view this from a linear algebra point of view. We can write the boolean circuit in form of a corresponding matrix that performs the transformation. Since every matrix will be linear transformation, there are known lower bounds which are of form $\Omega(n^2/r^c)$, where $n$ is the input size, $c$ is an arbitrary constant, and $r$ is the size of the biggest sub-matrix that is linear dependent. Since SHA-1 does mixing very well, I am sure we won't be able to reject even a constant fraction of input for any small (in matrix form, a submatrix of large size, comparable to $n$). This further implies that computing the circuit will require a lot of computation one that we are not willing to take.

I feel this argument works well for most of the candidate hash functions that uses linear arithmetic circuit to do the mixing.

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.