Introduction
Hello Reader!!
Cryptographic identification schemes are widely used in various applications, including access control, secure communication, and online transactions. They play a critical role in ensuring the security and privacy of these systems and services.
Today, we will learn about one such identification scheme called the Schnorr Identification Scheme.
So, let’s get started!
The Schnorr Identification Scheme
The Schnorr identification scheme is a method for proving the ownership of a secret value (called a "private key") without revealing the value itself. It was proposed by Claus Schnorr in 1991 as a variant of the Fiat-Shamir identification scheme, and it is widely used in various cryptographic protocols, including the Bitcoin protocol.
What is the Schnorr Identification Scheme?
In this scheme, a user (called the "prover") wants to prove to a verifier (called the "verifier") that they know the value of a private key without revealing the key itself. To do this, the prover and the verifier agree on a public key derived from the private key using a mathematical function. The prover then generates a random number (called the "challenge") and sends it to the verifier, along with a proof (called the "response") that is derived from the private key and the challenge.
The verifier can check the validity of the proof by using the public key, the challenge, and the response to perform a computation. If the computation is correct, the verifier can be confident that the prover knows the value of the private key without the prover actually revealing the key itself.
Uses
The Schnorr identification scheme is used in various applications, including password-authenticated key exchange protocols and digital signature schemes. It is considered a secure and efficient method for proving knowledge of a secret value.
It is known for its simplicity, efficiency, and security, and it has become a popular choice for use in various cryptographic protocols, including the Bitcoin protocol.
Working
The Schnorr identification scheme is a protocol that allows one party (the prover) to prove to another party (the verifier) that they know the value of some secret information without actually revealing the secret information itself. It is a zero-knowledge proof, meaning that the verifier does not learn any additional information about the prover's secret beyond the fact that the prover knows it.
Here is an outline of how the Schnorr identification scheme works:
- The prover and verifier agree on a prime number p and two integers g and h, such that h = gx (mod p) for some secret integer x that only the prover knows.
- Prover generates a random number r and calculates gr (mod p). They then send this value to the verifier, along with a value s such that s = xr + e (mod p-1), where e is a random number.
- The verifier checks that gs = g(xr) * ge = h * gr (mod p). If this is true, the verifier accepts the proof and concludes that the prover knows the value of x.
The critical property of the Schnorr identification scheme is that it is zero-knowledge, meaning that the verifier does not learn any additional information about the prover's secret beyond the fact that the prover knows it. This is achieved through the use of the random numbers r and e, which make it difficult for the verifier to determine the value of x based on the information provided by the prover.
Algorithm
Discrete logarithm
Logarithms described in terms of multiplicative cyclic groups are called discrete logarithms. We know from the definition of cyclic groups that any element h in G may be expressed as gx for some x if G is a multiplicative cyclic group and g is a generator of G. The discrete logarithm of h in the group G, to the base g, is defined as x.
Choosing parameters
- All signature scheme users agree on a group G, of prime order p, with a generator g, where the discrete log problem is supposed to be hard. A Schnorr group is commonly used.
- The cryptographic hash function H: {0,1}*→Zq is accepted by all users.
Key generation
- Select a private signing key, x, from the available set.
- Then, y=gx is the public verification key.
Signing
To sign a message m:
- Select a random value, k, from the available set.
- Consider, r = gk
- Consider, e= H(r||m), where || represents concatenation.
- Consider s= k-xe
Then, the signature will be the pair (s,e).
Verifying
- Consider rv = gsye
- Then, ev = H( rv || m)
If ev = e, then the signature is said to be verified.