Skip to content

Schnorr Signature

Table of contents

Open Table of contents

What it is

A Schnorr Signature is a way to prove that one knows a secret xx without revealing what the secret xx is. In the literate such a proof is often called a Zero-Knowledge Proof.

A speciality of the Schnorr Signature protocol is that it’s non-interactive which means that the proof computation and verification can be carried out asynchronously without the prover and verifier being online at the same time.

A closely related protocol that serves as the foundation for the Schnorr Signature protocol is the Schnorr Identification Protocol.

How it works

In our example we assume that Alice wants to convince Bob that she knows a secret value xx. Therefore Alice is the prover whereas Bob takes the role of the verifier. Furthermore we’ll work with the Elliptic Curve EE that is of order qq and has a generator GG.

The first thing Alice does is to decide on the value xx she wants to prover possession of. She e.g. does this by sampling this value randomly:

x$Zqx \overset{{\scriptscriptstyle\$}}{\leftarrow} \mathbb{Z}_q

Next up she computes X=xGX = xG which is the value she can publicly share.

Alice now needs to sample a random value rr called the “nonce” (number used once). It’s important that this value is truly random and never reused:

r$Zqr \overset{{\scriptscriptstyle\$}}{\leftarrow} \mathbb{Z}_q

She then calculates R=rGR = rG which is similar to the calculation she did before to get XX.

As a next step, Alice needs to derive a random value cc which is called “challenge” in the literature. This value has to depend on XX and RR as Alice should be forced to commit to those values.

Given that the output of a Hash Function is unpredictable and random, Alice can use such a function HH to derive the challenge cc by hashing the concatenation of GG, XX and RR:

c=H(GXR)c = H(G \mathbin\Vert X \mathbin\Vert R)

As a last step, Alice computes ee as e=r+cxmodqe = r + cx \mod q and sends XX, RR and ee to Bob.

Given that GG is a publicly known value and Bob has access to XX and RR, he can derive the same value for the challenge cc by hashing the concatenation of GG, XX and RR:

c=H(GXR)c = H(G \mathbin\Vert X \mathbin\Vert R)

As a last step, Bob checks if eG=?R+cXeG \overset{?}{=} R + cX to verify that Alice in fact knows the secret value xx. This check works because:

eG=R+cX(r+cx)G=rG+cxG(r+cx)G=(r+cx)G\begin{aligned} eG &= R + cX \\ (r + cx)G &= rG + cxG \\ (r + cx)G &= (r + cx)G \end{aligned}

Schnorr Signature

Why it works

Because the nonce rr is randomly sampled and never reused it’ll mask the value xx so that ee is indistinguishable from randomness for Bob.

The properties of a cryptographically secure hash function ensure that it’s output follows a random distribution which is necessary for the challenge cc that Alice computes herself to commit to XX and RR.

Furthermore this random output isn’t predictable and solely depends on the input values. Because rr is chosen randomly and a hash function’s output is random as well, the value cc will be random and therefore not guessable in advance.

The deterministic nature of a hash function allows Alice and Bob to derive the same value for cc independently.

Schnorr Signature vs. Schnorr Identification Protocol

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

The non-interactivity is possible thanks to the Fiat-Shamir heuristic that’s implemented by utilizing a hash function to allow the prover to asynchronously and deterministically derive the random value cc.

Additional Resources