Schnorr Signature

crypto-snippets/schnorr

Schnorr Signature

$\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}$

References

Schnorr, C. P. (1991). Efficient signature generation by smart cards. Journal of cryptology

Last modified June 16, 2025, 3:16 p.m.