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?

$\endgroup$
2
  • $\begingroup$ So your goal is taking a $\Sigma$-protocol that is only known to be HVZK and making it ZK? $\endgroup$
    – lamontap
    Commented May 1, 2023 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
    Commented May 3, 2023 at 7:16

1 Answer 1

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.

$\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
    Commented May 4, 2023 at 21:11
  • 1
    $\begingroup$ At first glance, providing additional inputs to $H$ seems to prevent the problems I've outlined. $\endgroup$
    – lamontap
    Commented May 8, 2023 at 20:48

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.