How to make the interactive Schnorr identification protocol become non-interactive

Question

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”

Answer 1

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.