# Schnorr Signature

## 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}

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.