Proving knowledge of a preimage of a hash without disclosing it?

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 freely downloadable version is very similar, or there is this earlier, longer version).

-
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. –  Jalaj Jan 28 '12 at 17:58
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. –  Jalaj Jan 29 '12 at 2:51
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$. –  fgrieu Jan 29 '12 at 9:38
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. –  PulpSpy Jan 30 '12 at 2:02
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. –  PulpSpy Jan 30 '12 at 15:12

2 Answers

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.

-
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. –  fgrieu Jan 30 '12 at 12:54
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. –  PulpSpy Jan 30 '12 at 15:08
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. –  fgrieu Jan 30 '12 at 20:10
@fgrieu: 3) Do you have use cases where this construction would be useful (and more desirable than a ZKPoK of a plaintext)? –  bob Oct 13 '12 at 19:49
@bob: to be honest, no I do not have a use case. My interest at that point is purely theoretical. –  fgrieu Oct 15 '12 at 11:14

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.

-