Zero-knowledge-proofs on committed value

Question

Assume user $A$ with corresponding public-private keys $(pk,sk)$ and a public information $r_1$ and $r_2$.

Let $r_{1s} = Sign(sk, r_1)$ be the signature on $r_1$ generated using $sk$ and $c = Hash(r_2 || r_{1s})$.

Now given $r_1, r_2$ and $c$ are publicly available can user $A$ produce a zero-knowledge proof that $c$ is generated correctly without revealing $r_{1s}$ and $sk$ ? If so how?

Thanks in advance.

Answer 1

Yes, user $A$ can produce such a proof - indeed, any statement in NP (i.e., for which it is possible to verify that a given solution is valid, which is obviously the case here) can be proven in zero-knowledge.

In general though, proving non-algebraic statements of this kind (involving evaluations of hash functions, rather than algebraic manipulations such as exponentiation) is more costly and less easy than proving algebraic statements. Yet, this kind of questions have been considered at length. There are currently three main approaches:

• Using garbled-circuit-based techniques, see e.g. this paper and some follow-ups
• Using MPC-in-the-head techniques, introduced in this seminal paper and subsequently improved in Zkboo, ZKB++, and this recent paper.
• A slightly different approach was taken in Ligero, using error-correcting codes, achieving a cost that scales only with the square root of the size of the circuit representing the statement (all previous solutions are linear).

Other techniques can also apply here, depending on your other constraints: should the prover be efficient? The verifier? Do you need the proof to be non-interactive? As short as possible? For each case, different solutions exist and provide various tradeoffs.