Schnorr Identification Protocol

What it is

The Schnorr Identification Protocol allows a party A to prove to another party B that they know a secret $x$ without revealing such secret to party B.

This protocol is an interactive version of a Zero-Knowledge Proof and serves as a foundation for a digital signature scheme called Schnorr Signature.

How it works

In our example we have two parties, Alice and Bob. Alice wants to prove to Bob that she knows a secret value $x$ without revealing it to Bob. In the Zero-Knowledge literature Alice would be called the “prover” whereas Bob is the “verifier”.

Our core assumption is that we’re working with an Elliptic Curve $E$ of order $q$. The curve’s generator we’re using will be called $G$. All calculations are done $\bmod\ q$ if not stated otherwise.

The first step is for Alice to decide on the secret $x$ she wants to prove knowledge of. Once done, Alice multiplies the secret $x$ with the generator $G$ to get $X = xG$. The value $X$ is then shared with Bob.

As a next step, Alice generates a random value $r$ she keeps secret. This value is multiplied by $G$ which results in $R = rG$. $R$ will be shared with Bob as well. Note that this step is identical to the first step, the only difference being that $r$ has to be random and should never be used more than once. The value $r$ is often called “nonce” (number used once) in the literature.

Now that Bob has $X$ and $R$ he generates a random value $c$ that shouldn’t be guessable by Alice. This value is called “challenge” and will be sent to Alice.

Upon receiving $c$, Alice computes $e = r + cx$ and sends $e$ to Bob.

Given $e$, Bob multiplies $e$ with $G$ to check whether $eG \overset{?}{=} R + cX$ (remember that Bob knows $R$, $c$, $X$ and $e$).

Why it works

Given that Bob doesn’t know the nonce $r$, Alice can hide $x$ multiplied by Bob’s challenge $c$ which results in $e$ being indistinguishable from randomness.

Bob can’t unmask $x$ with probability higher than a random guess.

Why $c$ needs to be random

Let’s assume that Alice can predict the value of Bob’s challenge $c$. With this knowledge Alice can forge a proof that she knows the value of $x$ without her actually knowing it.

This works, because Bob does the following calculation to validate Alice’s proof: $eG \overset{?}{=} R + cX$

Taking a random value for $e$ and the known challenge $c$, Alice can compute the following:

\begin{aligned} eG &= R + cX && \mid - cX \\ R &= eG - cX \end{aligned}

This way Alice can generate a valid $R$ without her knowing $r$ and $x$.

A note on nonce reuse

It’s of utmost importance to not reuse the nonce $r$ but rather treat it as an ephemeral, random value that’s disposed once used (and never reused again).

To see why, let’s consider a case where the nonce is reused in two subsequent protocol rounds.

Following the regular protocol we’ll eventually reach the point where we $e$ is calculated:

1st Round:

$e = r + cx \longrightarrow eG = R + cX$

2nd Round:

$e' = r + c'x \longrightarrow e'G = R + c'X$

Recording both values we can calculate the following:

\begin{aligned} eG &= R + cX \\ -e'G &= R + c'X \\ \hline eG - e'G &= (R + cX) - (R + c'X) \\ eG - e'G &= \cancel{R} + cX - \cancel{R} - c'X \\ (e - e')G &= (c - c')X \\ (e - e')G &= (c - c')X && \mid \div (c - c') \\ \frac{(e - e')}{(c - c')}G &= X \\ \frac{(e - e')}{(c - c')}G &= xG && \mid \div G \\ \frac{(e - e')}{(c - c')} &= x \end{aligned}

Which means that given two protocol runs where the same random value $r$ is used, we can recover the secret $x$.

Schnorr Identification Protocol vs. Schnorr Signature

The Schnorr Identification Protocol is the interactive version of the Schnorr Signature.

In the Schnorr Identification Protocol the verifier generates the random challenge $c$ whereas in Schnorr Signatures the random challenge $c$ can be computed by the prover using a hash function which produces a random output deterministically.

The technique which allows for this transformation from interactiveness- to non-interactiveness is called Fiat-Shamir heuristic.

References

The following resources have been invaluable for me to learn the concepts discussed in this article.

You should definitely give them a read if you want to dive deeper into the topic.