2
$\begingroup$

I am reading about ZKP and I found this interesting question about changing this protocol from interactive Schnorr identification protocol to non-interactive and I need help in solving it :

Peggy (prover) and Victor (verifier) have shared primes p,q such that q|p-1 and a generator $g$ such that $1<g<p$ and $g^q=1 \bmod p.$

Peggy has a private key $s$ and a public key $v=g^s$ ($v$ is known to Victor). Peggy wishes to convince Victor that she knows the secret exponent s without revealing what s is. She performs the following interactive protocol with Victor.

  1. Peggy chooses a random $r$ from $[0,q-1]$, calculates $x =g^r \bmod p$, and sends $x$ to Victor.

  2. Victor chooses a random challenge $e$ from $[1,\ldots,2t-1]$ where $t$ is a security parameter and sends $e$ to Peggy.

  3. Peggy calculates $y = r-se \bmod q$ and sends it to Victor.

  4. Victor checks that $x= g^yv^e \bmod p$. If so, then Victor “accepts”; otherwise, Victor “rejects”
$\endgroup$
  • 2
    $\begingroup$ Please fix the dangling "1" at the end. $\endgroup$ – kodlu Jan 9 '19 at 0:43
  • 1
    $\begingroup$ You can ask to merge your accounts. $\endgroup$ – kelalaka Jan 9 '19 at 16:27
  • 2
    $\begingroup$ What have you tried and where are you stuck? In all likelyhood your reading material has given you hints or info on how to solve this? $\endgroup$ – Maarten Bodewes Jan 9 '19 at 20:27
2
$\begingroup$

The most common way to change an interactive Schnorr protocol into a non-interactive one is to rely on a random oracle. This is the so-called "Fiat-Shamir heuristic".

Notice that a transcript in your case would look like $(r, e, y)$, where $e$ is the challenge the verifier sends to the prover. Now, you want to get rid of any interaction with the verifier to get that random challenge $e$, so what you need to do is to find a way to get rid of that interactive challenge. And there, you could have a random oracle giving you the challenge instead of the verifier.

In practice, this is done using a cryptographic hash function $H$ and so your transcript becomes $(r, H(r), y)$ or, as on Wikipedia: $(r, H(g,y,r), y)$. (It is important to include the public parameters in your Fiat-Shamir, to avoid problems such as weak Fiat-Shamir heuristics.)

Now, you can still verify that it works just like the interactive case, excepted we don't need to ask Victor, the verifier, to provide us with a random challenge anymore, since both the prover and the verifier can compute the challenge out of the rest of the data in a non-interactive way.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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