Digital signatures are the cryptographic equivalent of legally binding handwritten signatures, augmented by mathematical non-repudiation and unforgeability under chosen-message attacks (EUF-CMA). However, standard single-key signatures introduce single points of failure: if the private key is lost or compromised, total catastrophe ensues. In this part, we examine the mechanics of Schnorr signatures, the fragile perils of ECDSA, and how Shamir Secret Sharing and threshold multi-party signatures eliminate centralized custody.
1. The Schnorr Signature Protocol & Linearity
Patented by Claus Schnorr in 1989 (delaying its open adoption for 20 years), the Schnorr Signature is universally acknowledged as the cleanest, most algebraically elegant signature scheme. Let (G) be a cyclic group of prime order (q) with generator (g), and let (x in mathbb{Z}_q) be the private key with public key (X = g^x):
- Commitment: Signer samples ephemeral nonce (r leftarrow mathbb{Z}_q) and computes commitment (R = g^r).
- Challenge: Via the Fiat-Shamir transformation, compute challenge scalar (e = H(R parallel X parallel m) in mathbb{Z}_q).
- Response: Compute response scalar:
[
s = r + e cdot x pmod q
]
The signature is the pair ((R, s)). The verifier checks whether:
[
g^s stackrel{?}{=} R cdot X^e
]
Correctness follows immediately: (g^s = g^{r + ex} = g^r cdot (g^x)^e = R cdot X^e). Unlike ECDSA, Schnorr is linear in the secret key: ((s_1 + s_2) = (r_1 + r_2) + e(x_1 + x_2)). This linearity permits native multi-signatures (like MuSig2 in Bitcoin Taproot), where (n) parties construct a joint public key and sign cooperatively to produce a single standard signature indistinguishable from a single-signer transaction.
2. ECDSA: Mechanics and The Nonce-Leak Catastrophe
Because Schnorr was constrained by patents in the 1990s, standards committees designed the Elliptic Curve Digital Signature Algorithm (ECDSA). While widely deployed, ECDSA is notoriously brittle against subtle implementation flaws.
To sign message (m) with private key (d_A):
- Sample random secret nonce (k leftarrow mathbb{Z}_n^*).
- Compute curve point ((x_1, y_1) = [k]G), and set (r = x_1 bmod n).
- Compute (s = k^{-1} (z + r d_A) bmod n), where (z) is the message hash.
The catastrophic vulnerability of ECDSA is that the nonce (k) must be uniformly random, secret, and never repeated. If an adversary observes two signatures ((r, s_1)) and ((r, s_2)) sharing the same nonce (k) on messages (z_1, z_2):
[
s_1 – s_2 = k^{-1}(z_1 – z_2) implies k = rac{z_1 – z_2}{s_1 – s_2} pmod n
]
Once (k) is computed, the private key is instantly recovered: (d_A = (s_1 k – z_1) r^{-1} bmod n). This vulnerability caused the famous PlayStation 3 security failure (2010). Modern implementations prevent this by using RFC 6979 deterministic nonce generation: (k = ext{HMAC}(d_A, z)).
3. Shamir’s (k, n) Threshold Secret Sharing
In 1979, Adi Shamir solved the key custody problem via Secret Sharing: dividing a master secret (S) among (n) trustees such that any (k) shares can reconstruct (S), while any (k – 1) shares reveal strictly zero information.
The scheme relies on Lagrange Polynomial Interpolation over a prime field (mathbb{F}_p) (where (p > n) and (p > S)):
- The dealer sets the secret as the constant term (a_0 = S), and samples (k – 1) random coefficients (a_1, dots, a_{k-1} leftarrow mathbb{F}_p), forming a degree-((k-1)) polynomial:
[
f(x) = S + sum_{j=1}^{k-1} a_j x^j pmod p
] - Participant (i) receives the point share ((x_i, y_i) = (i, f(i))) for (i in {1, dots, n}).
Given any subset of (k) shares ({(x_i, y_i)}_{i=1}^k), the polynomial is reconstructed via Lagrange basis polynomials (ll_i(x)):
[
f(x) = sum_{i=1}^k y_i ll_i(x), quad ext{where } ll_i(x) = prod_{j
eq i} rac{x – x_j}{x_i – x_j} pmod p
]
Evaluating at (x = 0) recovers the secret: (S = f(0) = sum_{i=1}^k y_i ll_i(0)). Information-theoretic security is absolute: for any (k – 1) points, every possible secret (S’ in mathbb{F}_p) is mapped to by exactly one valid polynomial passing through those points, meaning (Pr[S = s mid k-1 ext{ shares}] = 1/p).
