crypto-snippets/bls
Boneh–Lynn–Shacham Digital Signature Algorithm
#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\gone{\mathbb{G}_1}$ $\gdef\genone{g_1}$ $\gdef\gentwo{g_2}$ $\gdef\gtwo{\mathbb{G}_2}$ $\gdef\gthree{\mathbb{G}_T}$ $\gdef\order{q}$ $\gdef\hash{\mathsf{H}}$
Given:
- Three cyclic group $\gone,\gtwo,\gthree$ with bilinear pairing $e: \gone \times \gtwo \to \gthree$, all of prime order $\order$
- Generators $\genone \in \gone, \gentwo \in \gtwo$
- A function $\hash: \msgspace \to \gone$ for mapping elements of the message space $\msgspace$ to elements in $\gone$.
BLS instantiates a signature scheme as follows:
$\keygen(1^n) \to (pk, sk)$
- Random \(\alpha \stackrel{\$}{\gets} \mathbb{Z_q}\)
- $h := \genone^\alpha$
- Output $(pk := h, sk := \alpha)$
$\sign(sk, m) \to \sigma$
- $m' \gets \hash(m)$
- $\sigma \gets m'^\alpha$
- Output $\sigma$
$\verify(pk, m, \sigma) \to \{0,1\}$
- $m' \gets \hash(m)$
- Output $e(\genone, \sigma) \stackrel{?}{=} e(pk, m')$
Last modified June 1, 2025, 5:02 p.m.