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.
a. Key Generation:
The prover generates a public-private key pair.
s k = a ; p k = a ? G sk = a; pk = a \cdot G sk=a;pk=a?G
b. Commitment:
The prover chooses a random number r r r and commits to the value R R R.
R = r ? G R = r \cdot G R=r?G
c. Challenge:
The verifier sends a random challenge c c c to the prover.
d. Response:
The prover responds to the challenge with information derived from the secret key. The prover sends z z z to the verifier.
z = r + c ? s k z = r + c \cdot sk z=r+c?sk
e. Verification:
The verifier checks the validity of the response and decides whether to accept or reject.
z ? G = ? R + c ? p k z \cdot G \overset{\text{?}}{=} R + c \cdot pk z?G=?R+c?pk
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.
s
k
=
a
;
p
k
=
a
?
G
sk = a; pk = a \cdot G
sk=a;pk=a?G
b. Commitment:
The prover chooses a random number r r r and commits to the value R R R, similar to the interactive version.
R = r ? G R = r \cdot G R=r?G
c. Hashing:
The prover hashes the commitment and other relevant information to generate a challenge.
c = Hash ( p k , R ) c = \text{Hash}(pk,R) c=Hash(pk,R)
d. Response:
The prover responds to the challenge with information derived from the secret key. The prover sends z z z and R R R to the verifier.
z = r + c ? s k z = r + c \cdot sk z=r+c?sk
e. Verification:
The verifier checks the validity of the response using the hash function and decides whether to accept or reject.
c
′
=
Hash
(
p
k
,
R
)
c^{'} = \text{Hash}(pk,R)
c′=Hash(pk,R)
z
?
G
=
?
R
+
c
′
?
p
k
z \cdot G \overset{\text{?}}{=} R + c^{'} \cdot pk
z?G=?R+c′?pk