Boneh–Lynn–Shacham Digital Signature Algorithm

crypto-snippets/bls

Boneh–Lynn–Shacham Digital Signature Algorithm

$\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')$

References

Dan Boneh, Ben Lynn, Hovav Shacham. Short Signatures from the Weil Pairing. ASIACRYPT 2001. pages 514-532. See also J. Cryptology 17(4): 297-319 (2004).

Last modified June 1, 2025, 5:02 p.m.