Table of contents
Open Table of contents
What it is
The Schnorr Identification Protocol allows a party A to prove to another party B that they know a secret without revealing such secret to party B.
This protocol is an interactive version of a Zero-Knowledge Proof and serves as a foundation for a digital signature scheme called Schnorr Signature.
How it works
In our example we have two parties, Alice and Bob. Alice wants to prove to Bob that she knows a secret value without revealing it to Bob. In the Zero-Knowledge literature Alice would be called the “prover” whereas Bob is the “verifier”.
Our core assumption is that we’re working with an Elliptic Curve of order . The generator we’re using for this curve will be called .
The first step is for Alice to decide on the secret she wants to prove knowledge of. Once done, Alice multiplies the secret with the generator to get . The value is then shared with Bob.
As a next step, Alice generates a random value she keeps secret. This value is multiplied by which results in . will be shared with Bob as well. Note that this step is identical to the first step, the only difference being that has to be random and should never be used more than once. The value is often called “nonce” (number used once) in the literature.
Now that Bob has and he generates a random value that shouldn’t be guessable by Alice. This value is called “challenge” and will be sent to Alice.
Upon receiving , Alice computes and sends to Bob.
Given , Bob multiplies with to check whether (remember that Bob knows , , and ).
Why it works
Given that Bob doesn’t know the nonce , Alice can hide multiplied by Bob’s challenge which results in being indistinguishable from randomness.
Bob can’t unmask with probability higher than a random guess.
Why needs to be random
Let’s assume that Alice can predict the value of Bob’s challenge . With this knowledge Alice can forge a proof that she knows the value of without her actually knowing it.
This works, because Bob does the following calculation to validate Alice’s proof:
Taking a random value for and the known challenge , Alice can compute the following:
This way Alice can generate a valid without her knowing and .
A note on nonce reuse
It’s of utmost importance to not reuse the nonce but rather treat it as an ephemeral, random value that’s disposed once used (and never reused again).
To see why, let’s consider a case where the nonce is reused in two subsequent protocol rounds.
Following the regular protocol we’ll eventually reach the point where we is calculated:
Recording both values we can calculate the following:
Which means that given two protocol runs where the same random value is used, we can recover the secret .
Schnorr Identification Protocol vs. Schnorr Signature
The Schnorr Identification Protocol is the interactive version of the Schnorr Signature.
In the Schnorr Identification Protocol the verifier generates the random challenge whereas in Schnorr Signatures the random challenge can be computed by the prover using a hash function which produces a random output deterministically.
The technique which allows for this transformation from interactiveness- to non-interactiveness is called Fiat-Shamir heuristic.