Skip to content

Schnorr Identification Protocol

Table of contents

Open Table of contents

What it is

The Schnorr Identification Protocol allows a party A to prove to another party B that they know a secret xx 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 xx 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 EE of order qq. The generator we’re using for this curve will be called GG.

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

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

Now that Bob has XX and RR he generates a random value cc that shouldn’t be guessable by Alice. This value is called “challenge” and will be sent to Alice.

Upon receiving cc, Alice computes e=r+cxmodqe = r + cx \mod q and sends ee to Bob.

Given ee, Bob multiplies ee with GG to check whether eG=?R+cXeG \overset{?}{=} R + cX (remember that Bob knows RR, cc, XX and ee).

Schnorr Identification Protocol

Why it works

Given that Bob doesn’t know the nonce rr, Alice can hide xx multiplied by Bob’s challenge cc which results in ee being indistinguishable from randomness.

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

Why cc needs to be random

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

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

Taking a random value for ee and the known challenge cc, Alice can compute the following:

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

This way Alice can generate a valid RR without her knowing rr and xx.

A note on nonce reuse

It’s of utmost importance to not reuse the nonce rr 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 ee is calculated:

1st Round:

e=r+cxmodqeG=R+cXe = r + cx \mod q \longrightarrow eG = R + cX

2nd Round:

e=r+cxmodqeG=R+cXe' = r + c'x \mod q \longrightarrow e'G = R + c'X

Recording both values we can calculate the following:

eG=R+cXeG=R+cXeGeG=(R+cX)(R+cX)eGeG=R+cXRcX(ee)G=(cc)X(ee)G=(cc)X÷(cc)(ee)(cc)G=X(ee)(cc)G=xG÷G(ee)(cc)=x\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 rr is used, we can recover the secret xx.

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 cc whereas in Schnorr Signatures the random challenge cc 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.

Additional Resources