Fiat-Shamir Identification Protocol

There are three principals Prover Peggy, Verifier Victor, and Trusted Third Party Trent. We setup as follows:

• Trent chooses two large prime numbers $p$ and $q$ to calculate $n=p\times q$.
• $n$ is announced to the public, whereas $p$ and $q$ are kept secret.
• Peggy chooses a secret number $s$ between $1$ and $n-1$, and calculates $v=s^2\text{ mod }n$. She keeps $s$ as her private key and registers $v$ as her public key with the third party.

Victor knows $v=s^2\text{ mod }n$ but does not know $s$. Peggy wants to convince Victor that she knows the secret $s$ but Victor should not learn $s$.

We believe that square root modulo $n$ is not easy to compute.

Verification of Peggy by Victor proceeds in 4 steps (this is a round):

1. Peggy chooses a random number $r$ between $1$ and $n-1$. $r$ is called the commitment Peggy calculates the witness $x=r^2\text{ mod }n$ and sends it to Victor.
2. Victor sends the challenge $c$ to Peggy, which is either $0$ or $1$.
3. Peggy calculates the response $y=(r\times s^c)\text{ mod }n$ and sends it to Victor to show that she knows her private key $s$ modulo $n$. She claims to be Peggy.
4. Victor calculates $y^2\text{ mod }n$ and $(x\times v^c)\text{ mod }n$. If these values are congruent, then Peggy either knows the value of $s$ (honest) or she has calculated the value of $y$ is some either ways (dishonest) because in module $n$ arithmetic we have that: $y^2{=}_n(r\times s^c{)}^2{=}_n{r}^2\times s^{2c}{=}_n{r}^2\times (s^2{)}^c{=}_{n}x\times v^c$ The verification is repeated several times with the value of $c$ equal to $0$ or $1$ at random. Peggy must pass the test in each round to be verified: if she fails one single round => we abort the process entirely.