crypto-snippets/schnorr
Schnorr Signature
#instantiation
#signatures
$\gdef\system{\mathsf{Sig}}$ $\gdef\systemprefix{}$ $\gdef\keygen{\mathsf{\systemprefix{}KGen}}$ $\gdef\sign{\mathsf{\systemprefix{}Sign}}$ $\gdef\verify{\mathsf{\systemprefix{}Verify}}$ $\gdef\msgspace{\mathcal{M}}$ $\gdef\group{\mathbb{G}}$ $\gdef\gen{g}$
$\gdef\order{q}$ $\gdef\hash{\mathsf{H}}$
Given a cyclic group $\group$ of prime order $\order$, generator $\gen \in \group$, and a hash function $H$, the schnorr signature algorithm instantiates a digital signature scheme as follows:
$\keygen(1^n) \to (pk, sk)$
- Sample random \(x \stackrel{\$}{\gets} \mathbb{Z}_\order\)
- $X := \gen^x$
- Output $(pk := X, sk := x)$
$\sign(sk, m) \to \sigma$
- Sample random \(r \stackrel{\$}{\gets} \mathbb{Z}_\order\)
- $R := \gen^r$
- $c \gets \hash(X \| R \| m)$
- $s := r + cx$
- Output $\sigma := (R, s)$
$\verify(pk, m, \sigma) \to \{0,1\}$
- Parse $(R, s) := \sigma$
- Output $g^s \stackrel{?}{=} RX^c$
Correctness
This works because:
- $g^s \stackrel{?}{=} RX^c$
- $g^{r + cx} \stackrel{?}{=} g^r (g^x) ^c$
- $g^{r + cx} \stackrel{?}{=} g^r g^{xc}$
- $g^{r + cx} = g^{r + xc}$
Last modified June 16, 2025, 3:16 p.m.