Table of contents
Open Table of contents
What it is
A Schnorr Signature is a way to prove that one knows a secret without revealing what the secret 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 . Therefore Alice is the prover whereas Bob takes the role of the verifier. Furthermore we’ll work with the Elliptic Curve that is of order and has a generator .
The first thing Alice does is to decide on the value she wants to prover possession of. She e.g. does this by sampling this value randomly:
Next up she computes which is the value she can publicly share.
Alice now needs to sample a random value called the “nonce” (number used once). It’s important that this value is truly random and never reused:
She then calculates which is similar to the calculation she did before to get .
As a next step, Alice needs to derive a random value which is called “challenge” in the literature. This value has to depend on and 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 to derive the challenge by hashing the concatenation of , and :
As a last step, Alice computes as and sends , and to Bob.
Given that is a publicly known value and Bob has access to and , he can derive the same value for the challenge by hashing the concatenation of , and :
As a last step, Bob checks if to verify that Alice in fact knows the secret value . This check works because:
Why it works
Because the nonce is randomly sampled and never reused it’ll mask the value so that 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 that Alice computes herself to commit to and .
Furthermore this random output isn’t predictable and solely depends on the input values. Because is chosen randomly and a hash function’s output is random as well, the value 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 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 .