Schnorr Identification Protocol

Open Table of contents

What it is
How it works
Why it works
Why $c$ needs to be random
A note on nonce reuse
Schnorr Identification Protocol vs. Schnorr Signature
References

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

Schnorr Identification Protocol

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