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 at 0:43
  • 1
    $\begingroup$ You can ask to merge your accounts. $\endgroup$ – kelalaka Jan 9 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 at 20:27
1
$\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 only need interaction from the verifier in order to get that random challenge $e$, so what you want to do is to simply find a way to get rid of that challenge so that you'll 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)$.

Now, you can still verify that it works just like the interactive case, excepted we didn't need to ask Victor the verifier to provide us with a random challenge.

$\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.