The Schnorr Identification Protocol relies upon the security of the Discrete Logarithm Problem. Schnorr's protocol was introduced after, and is comparable to, the identification protocol of Fiat and Shamir and that of Guillou-Quisquater.

The Schnorr Identification Protocol relies upon the security of the Discrete Logarithm Problem. Schnorr's protocol was introduced after, and is comparable to, the identification protocol of Fiat and Shamir and that of Guillou-Quisquater.

Protocol Description

One of the simplest and frequently used proofs of knowledge – the proof of knowledge of a discrete logarithm – is due to Schnorr. The protocol is defined for a cyclic group $G_q$ of order $q$ with generator $g$.

In order to prove knowledge of $x=\log_g y$, the prover interacts with the verifier as follows:

  • In the first round the prover commits herself to randomness $r$; therefore the first message $t=g^r$ is also called commitment.
  • The verifier replies with a challenge $c$ chosen at random.
  • After receiving $c$, the prover sends the third and last message (the response) $s=r+cx$.

The verifier accepts, if $g^s = t y^{c}$.

For details, see the paper: C. P. Schnorr, “Efficient identification and signatures for smart cards”, in G Brassard, ed. Advances in Cryptology – Crypto '89, 239–252, Springer-Verlag, 1990. Lecture Notes in Computer Science, nr 435