# 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$.

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

$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 before 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 $G$, $X$ and $R$:

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

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

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

$c = H(G \mathbin\Vert 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}

## 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 it’s 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$.