Schnorr signature

For a user with secret key \(x\) and public key \(Y = g^x\).

• Sign \((M, x, g, Y)\) - Choose \(t \in_R \mathbb{Z}_p\) and compute \(T \leftarrow g^t\). Then compute the challenge \(c \leftarrow H(T, M)\) and \(s \leftarrow t + c \cdot x\). Output the signature \(\sigma = (c, s)\).
• Verify \((M, \sigma, Y, g)\) - Restore the t-value \(T' \leftarrow g^{s}Y^{-c}\) and check whether the equation \(H(T', M) \stackrel{?}{=} c\) holds.

\(\Sigma\)-protocols

Basically, we may turn any \(\Sigma\)- protocol into a signature scheme. To do that we hash the ,,\(t\)-values'' with a message and use this value as challenge.

Simplified notation - example

\[\sigma = SPoK\{(\alpha, \beta): g^{\alpha} = y \land \hat{g}^{\alpha}g^{\beta} = z\}(M) \] This denotes a signature of knowledge \(\sigma\) under message \(M\), of knowledge of \(\alpha\) and \(\beta\) s.t. the relations \(g^{\alpha} = y\) and \(\hat{g}^{\alpha}g^{\beta} = z\) hold.

Intro

• Signature scheme proposed and standardized by NIST
• Combination of two schemes: Schnorr signature and ElGamal signature

The scheme

• Private key \(0 < x < q\) and public key \(Y \leftarrow g^x \mod p\), where \(p\) is prime, \(g\) is the group generator of \(\mathbb{Z}_p^*\) of order \(q\).
• Sign\((x, Y, M)\) - choose \(0 < k < q\), compute \(r \leftarrow (g^k \mod p ) \mod q\) and \(s = k^{-1} \cdot (H(m) + x \cdot r) \mod q\). Return the signature \(\sigma = (r, s)\)
• Verify \((Y, \sigma, M)\) - compute \(w \leftarrow s^{-1} \mod q\), \(u_1 \leftarrow H(M) \cdot w \mod q\) and \(u_2 \leftarrow r \cdot w \mod q\). Verify whether \(r \stackrel{?}{=} (g^{u_1}\cdot Y^{u_2} \mod p) \mod q\).

• Security arguments as in schnorr signature do not apply here. No extractor, cannot be simulated.
• The problem is due the way the ,,challenge'' hash is computed.
• DSA was mostly criticised by RSA lobbyist. Surprisingly, the fact that it had no security reduction have been omitted.

• Choose two prime numbers \(p\) i \(q\).
• Compute \(n = p \cdot q\) and \(\phi(n) = (p - 1)(q - 1)\)
• choose a random number \(1 < e < \phi(n)\) co-prime with \(\phi(n)\), i.e. \(gcd(e, \phi(n)) = 1\)
• Compute \(d = e^{-1} \mod \phi(n)$, ($1 < d < \phi(n)\))
  
  
• Sign\((M, d)\) - compute and return \(\sigma \leftarrow H(M)^d \mod n\).
• Verify\((M, \sigma, e)\) - Check whether \(H(M) = \sigma^e \mod n\)

By far we discussed:

• Fundamentals on Interactive and Non-Interactive proof systems.
• Relationship of non-interactive proof systems to signature schemes.
• Schnorr identification scheme (or proof of knowledge of discrete logarithm), compositions of schnorr scheme
• Fiat-Shamir heuristic and DSA signature scheme
• RSA signature scheme

Privacy?

By far for each identification/signature scheme the verifier knew the identity of the user i.e. a constant and unique, for each user, public key.