Schnorr Signature

Open Table of contents

What it is
How it works
Why it works
Schnorr Signature vs. Schnorr Identification Protocol
References

What it is

A Schnorr Signature is a way to prove that one knows a secret $x$ without revealing what the secret $x$ 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 $x$ . Therefore Alice is the prover whereas Bob takes the role of the verifier. Furthermore we’ll work with the Elliptic Curve $E$ that is of order $q$ and has a generator $G$ . All calculations are done $\bmod\ q$ if not stated otherwise.

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

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

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

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

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

She then calculates $R = rG$ which is similar to the calculation she did to get $X$ .

As a next step, Alice needs to derive a random value $c$ which is called “challenge” in the literature. This value has to depend on $X$ and $R$ 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 $H$ to derive the challenge $c$ by hashing the concatenation of $X$ and $R$ :

c = H(X \mathbin\Vert R)

As a last step, Alice computes $e$ as $e = r + cx$ and sends $X$ , $R$ and $e$ to Bob.

Given that Bob has now access to $X$ and $R$ , he can derive the same value for the challenge $c$ by hashing the concatenation of $X$ and $R$ :

c = H(X \mathbin\Vert R)

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

\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 $x$ without disclosing it to Bob.

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

If Alice wants to sign a message $m$ , she needs to concatenate it with the $X$ and $R$ values that are passed into the Hash Function $H$ to produce the challenge $c$ :

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

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

Why it works

Because the nonce $r$ is randomly sampled and never reused it’ll mask the value $x$ so that $e$ 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 $c$ that Alice computes herself to commit to $X$ and $R$ .

Furthermore this random output isn’t predictable and solely depends on the input values. Because $r$ is chosen randomly and a hash function’s output is random as well, the value $c$ 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 $c$ 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 $c$ .

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.