2
$\begingroup$

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.

Improve this question
$\endgroup$
1
  • $\begingroup$ intuitively I would assume this can't be done for a black box hash function without looking at it's internals, but obviously can be done for any efficently computeable hash function. $\endgroup$
    – Meir Maor
    Jul 28, 2018 at 10:20

1 Answer 1

Reset to default
3
$\begingroup$

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.

Improve this answer
$\endgroup$
2
  • $\begingroup$ Thanks. I understand that since the statement is is NP, there will exist a zk proof for this statement. Additionally, can you also let me know how well this specific problem is studied and is there any standard approach just like Graph-isomorphism(GI) or GNI? $\endgroup$
    – sourav
    Jul 28, 2018 at 16:33
  • $\begingroup$ If by "this specific problem" you mean "a hash of a signature concatenated with a public value", I don't think it has been specifically considered - but well, there is no point in considering separately different instances of a problem. All the approaches I mentioned are "standard" for solving this class of problem, and all apply well to your specific problem. You only need to write down a boolean circuit for computing the function you are interested in (hash of signature), and then pick the solution that works best for this circuit size. $\endgroup$
    – Geoffroy Couteau
    Jul 30, 2018 at 17:26

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.