2
$\begingroup$

Suppose we have a standard $\Sigma$-protocol for proving the knowledge of a witness $x$ for the statement $y$. It has an honest-verifier ZK and special soundness. Now we do an unusual modification to get an interactive $\Sigma'$-protocol in ROM:

  1. The prover $\mathcal{P}$ compute $a$ exactly like in $\Sigma$-protocol and sends it to the verifier $\mathcal{V}$.
  2. The verifier $\mathcal{V}$ replies with a challenge $e$. So far, everything is like in $\Sigma$-protocol.
  3. Modification: The prover $\mathcal{P}$ computes $e' = \textsf{Hash}(e)$ and uses $e'$ as the challenge to compute the answer $z$.

Has anyone seen this construction mentioned anywhere? I think it should have full ZK in ROM, but I never saw anything similar. Is it because $\Sigma'$ is folklore/not very useful, or am I wrong about the full ZK?

Improve this question
$\endgroup$
2
  • $\begingroup$ So your goal is taking a $\Sigma$-protocol that is only known to be HVZK and making it ZK? $\endgroup$
    – lamontap
    May 1 at 20:59
  • $\begingroup$ Yes, interactive protocol with ZK in ROM by just hashing the challenge before applying it. I just wonder if anyone was looking into something similar $\endgroup$
    – pintor
    May 3 at 7:16

1 Answer 1

Reset to default
1
$\begingroup$

For the Fiat-Shamir transform, HVZK becomes ZK because the verifier sends nothing to the prover. The ZK simulator generates $(a,e,z)$ from the HVZK simulator and reprograms the oracle so that $H(a)=e$. This works because $c$ is uniformly random and the verifier cannot have known the value of $H(a)$ before the reprogramming (except with negligible probability).

A similar trick doesn't work with the scheme you propose since the verifier can query $H(e)$ before step 2, making reprogramming harder. The verifier can also influence the distribution of $e'$, for example by querying the oracle on many points and rejection sampling. If the simulator could somehow guess the challenge $e$, it could generate a transcript for a uniformly random challenge $e'$ and reprogram the oracle as $H(e)=e'$. But the probability of making the right guess is exponential in the size of $e$ and even if we were to make this size logarithmic and use rewinding, we run into issues. The verifier could compute the full table for $H(e')$ since there are only polynomially many possible values, making reprogramming impossible.

But as you hinted in your question, this scheme does not seem all that useful, especially in a model (the ROM) where you can make the whole thing non-interactive.

Improve this answer
$\endgroup$
2
  • 1
    $\begingroup$ Thanks a lot! Quick question, if the whole issue is that the verifier can query Hash(e) multiple times and affect the distribution, does it mean that setting $e'= Hash(e, a, y)$ would fix it? $\endgroup$
    – pintor
    May 4 at 21:11
  • 1
    $\begingroup$ At first glance, providing additional inputs to $H$ seems to prevent the problems I've outlined. $\endgroup$
    – lamontap
    May 8 at 20:48

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.