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