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. All calculations are done mod q\bmod\ q if not stated otherwise.

The first thing Alice does is to decide on the value xx she wants to prove possession of. She e.g. does this by sampling this value randomly from Zq\mathbb{Z}_q:

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 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 XX and RR:

c=H(XR)c = H(X \mathbin\Vert R)

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

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

c=H(XR)c = H(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

In the example above, Alice only proved that she knows the secret value xx without disclosing it to Bob.

The protocol can be slightly modified to allow for the creation of a digital signature over an arbitrary message mm.

If Alice wants to sign a message mm, she needs to concatenate it with the XX and RR values that are passed into the Hash Function HH to produce the challenge cc:

c=H(XRm)c = H(X \mathbin\Vert R \mathbin\Vert m)

To verify if the signature over the message mm is valid, Bob needs to recompute c=H(XRm)c = H(X \mathbin\Vert R \mathbin\Vert m) and check if eG=?R+cXeG \overset{?}{=} R + cX as he did before.

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


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.