Schnorr Protocol
The Schnorr Protocol is a cryptographic protocol used for secure communication and digital signatures. It was originally proposed by Claus-Peter Schnorr in 1989 and has gained attention for its simplicity and efficiency. There are both interactive and non-interactive versions of the Schnorr Protocol.
Interactive Schnorr Protocol
a. Key Generation:
The prover generates a public-private key pair.
$$sk = a; pk = a \cdot G$$
b. Commitment:
The prover chooses a random number $r$ and commits to the value $R$.
$$R = r \cdot G$$
c. Challenge:
The verifier sends a random challenge $c$ to the prover.
d. Response:
The prover responds to the challenge with information derived from the secret key. The prover sends $z$ to the verifier.
$$z = r + c \cdot sk$$
e. Verification:
The verifier checks the validity of the response and decides whether to accept or reject.
$$z \cdot G \overset{\text{?}}{=} R + c \cdot pk$$
Non-Interactive Schnorr Protocol
The non-interactive version is designed to be more efficient and is often used in scenarios where a single round of communication is preferred.
This is achieved by using a technique called a Fiat-Shamir transform, which converts an interactive protocol into a non-interactive one by replacing the challenge from the verifier with a hash function.
The steps involved in the non-interactive Schnorr Protocol are as follows:
a. Key Generation:
The prover generates a public-private key pair.
$$sk = a; pk = a \cdot G$$
b. Commitment:
The prover chooses a random number $r$ and commits to the value $R$, similar to the interactive version.
$$R = r \cdot G$$
c. Hashing:
The prover hashes the commitment and other relevant information to generate a challenge.
$$c = \text{Hash}(pk,R)$$
d. Response:
The prover responds to the challenge with information derived from the secret key. The prover sends $z$ and $R$ to the verifier.
$$z = r + c \cdot sk$$
e. Verification:
The verifier checks the validity of the response using the hash function and decides whether to accept or reject.
$$c^{‘} = \text{Hash}(pk,R)$$
$$z \cdot G \overset{\text{?}}{=} R + c^{‘} \cdot pk$$