Discrete Logarithm Problem (DLP):

• The security of Schnorr signatures relies on the difficulty of solving the discrete logarithm problem in a cyclic group. Given a group G with a generator g, and an element $y = g^x$ for some secret x, it is computationally hard to find x given g and y.

• Cyclic Group:

  • Schnorr signatures operate in a cyclic group G of prime order q with a generator g. The group is typically a subgroup of the multiplicative group of integers modulo a large prime, or it could be an elliptic curve group.

    Components of Schnorr Signatures

    • Private Key (x): A randomly chosen integer from {0,1,…,q−1}.

    • Public Key (y): The public key is $y = g^x$, where g is the generator of the group.

      Message (m): The data that is to be signed.

    • Hash Function (H): A cryptographic hash function, often modeled as a random oracle.

    1. Key Generation:

    • Choose a random private key x∈{0,1,…,q−1}.
    • Compute the public key $y = g^x$, where g is the generator of the group G.
    • The public key y is shared, and the private key x is kept secret.

    2. Signing a Message:

    • Step 1: Commitment
      • The signer picks a random value k∈{0,1,…,q−1}.
      • Compute the commitment $R = g^k$
    • Step 2: Challenge
      • Compute the challenge c=H(R∥m), where ∥ denotes concatenation, and H is the hash function.
    • Step 3: Response
      • Compute the response $s=k+cxmodq.$
    • Signature:
      • The signature on the message m is the pair (R,s).

    3. Verifying a Signature:

    • To verify the signature (R,s) on the message m:
      • Compute the challenge c=H(R∥m).
      • Compute $g^s$ and check if $g^s=R⋅y^c$
      • If the equation holds, the signature is valid; otherwise, it is invalid.

    WHY it works?

    To understand why the verification process in Schnorr signatures works, it helps to break down the steps and consider what each part of the signature and verification process ensures:

    1. Commitment and Response:

       • When the prover generates the signature, they pick a random value k and compute $R=g^k$. This R serves as a kind of "commitment" to the random value k.
       • The challenge c is derived by hashing the commitment R and the message m, ensuring that c is unpredictable and tightly bound to both R and m.
       • The prover then computes s=k+cx, where x is the secret key. This response s encapsulates the randomness k and the secret key contribution cx.

    2. Verification Equation:

       • The verification equation $g^s=R⋅y^c$ essentially checks that the prover knows the correct relationship between the public key $y=g^x$ and the challenge c without revealing the secret key x.

       • To break it down:

         • $g^s=g^{k+cx}=g^k⋅g^{cx}$

         • On the other hand,

           $R \cdot y^c = g^k \cdot (g^x)^c = g^k \cdot g^{cx}$

       • If the prover computed s correctly, then both sides of the verification equation will match, ensuring that s is consistent with the knowledge of the secret key x and the original random value k.

    3. Security through Binding:

       • The challenge c=H(R∥m) binds the commitment R to the message m. This binding ensures that the challenge c is unpredictable until R is determined. This unpredictability makes it infeasible for an attacker to forge a signature without knowing the secret key x.

         c=H(R∥m)

    4. Non-malleability:

       • Because the challenge is generated through a hash function, it's non-malleable—an attacker can't easily modify a valid signature to produce another valid signature for a different message.