Digital signature

A digital signature (DS) scheme allows a signer holding a secret signing key to produce an unforgeable signature on a message, which anyone can verify using the corresponding public verification key. Digital signatures are the public-key analogue of MACs.

Syntax

A Digital Signature scheme is a tuple of efficient algorithms $\mathsf{DS}=(\mathsf{KeyGen},\mathsf{Sign},\mathsf{Vrfy})$ with respect to signing keyspace ${\mathcal{K}}_{\mathrm{sk}}$, verification (or public) keyspace ${\mathcal{K}}_{\mathrm{pk}}$, message space $\mathcal{M}$, and signature space $\mathcal{S}$:

• $\mathsf{KeyGen}(1^{\lambda })\to (\mathsf{sk},\mathsf{vk}),$ is a randomized algorithm which samples a signing key $\mathsf{sk}\in {\mathcal{K}}_{\mathrm{sk}}$ and verification (or public) key $\mathsf{vk}\in {\mathcal{K}}_{\mathrm{pk}}$,
• $\mathsf{Sign}(\mathsf{sk},m)\to \sigma ,$ is a (possibly) randomized algorithm which takes a signing key $\mathsf{sk}\in {\mathcal{K}}_{\mathrm{sk}}$ and message $m\in \mathcal{M}$, outputting signature $\sigma \in \mathcal{S}$,
• $\mathsf{Vrfy}(\mathsf{vk},m,\sigma )\to b,$ is a deterministic algorithm which takes a verification key $\mathsf{vk}\in {\mathcal{K}}_{\mathrm{pk}},$ a message $m\in \mathcal{M},$ and a signature $\sigma \in \mathcal{S}$, outputting a bit $b\in \{0,1\}$ indicating whether the signature is valid or not.

Properties

Correctness

A Digital Signature scheme $\mathsf{DS}=(\mathsf{KeyGen},\mathsf{Sign},\mathsf{Vrfy})$ is $(1-\epsilon )$-correct if for all $m\in \mathcal{M}$,

$$\mathrm{Pr}\left[\mathsf{Vrfy}(\mathsf{vk},m,\mathsf{Sign}(\mathsf{sk},m))=1\right]\ge 1-\epsilon ,$$

over the randomness of $(\mathsf{sk},\mathsf{vk})\leftarrow \mathsf{KeyGen}(1^{\lambda })$ and possibly $\mathsf{Sign}.$

Existential Unforgeability

The following is the existential unforgeability under chosen message attacks (EUF-CMA) game. This security notion requires that an adversary cannot produce a valid message-signature pair $(\hat{m},\hat{\sigma })$ for a message $\hat{m}$ it has not submitted to the signing oracle, even given signatures on adversarially chosen messages.

\begin{algorithm}
\algname{Game}
\caption{$\Game^{\eufcma}_{\DS,\calA}(\secpar)$}
\begin{algorithmic}
\State $(\sk, \vk) \gets \KeyGen(1^\secpar)$
\State $\calQ \gets \{\}$
\State $(\hat{m},\hat{\sigma}) \gets \calA^{\calO}(1^\secpar, \vk)$
\If{$\hat{m}\in \calQ$}
\Comment{$\hat{m}$ cannot repeat}
\Return $0$
\EndIf
\Return $[\Vrfy(\vk,\hat{m},\hat{\sigma})]$
\end{algorithmic}
\end{algorithm}

\begin{algorithm}
\algname{Oracle}
\caption{$\calO(m)$}
\begin{algorithmic}
\State $\sigma \gets \Sign(\sk,m)$
\State $\calQ \gets \calQ \cup \{m\}$
\Return $\sigma$
\end{algorithmic}
\end{algorithm}

A DS scheme $\mathsf{DS}$ is EUF-CMA unforgeable if for all efficient $\mathcal{A}$,

$${\mathbf{Adv}}_{\mathsf{DS},\mathcal{A}}^{\mathrm{euf}\text{-}\mathrm{cma}}(\lambda ):=\mathrm{Pr}\left[{\mathbf{G}}_{\mathsf{DS},\mathcal{A}}^{\mathrm{euf}\text{-}\mathrm{cma}}(\lambda )=1\right]$$

is negligible.

Strong Unforgeability

The following is the strong unforgeability under chosen message attacks (SUF-CMA) game. This security notion strengthens the above EUF-CMA notion and requires $\mathsf{DS}$ to prevent an adversary from “mauling” the signature to produce a new signature for the same message. For example, by rerandomizing the signature into another valid signature.

\begin{algorithm}
\algname{Game}
\caption{$\Game^{\sufcma}_{\DS,\calA}(\secpar)$}
\begin{algorithmic}
\State $(\sk, \vk) \gets \KeyGen(1^\secpar)$
\State $\calQ \gets \{\}$
\State $(\hat{m},\hat{\sigma}) \gets \calA^{\calO}(1^\secpar, \vk)$
\If{$(\hat{m},\hat{\sigma})\in \calQ$}
\Comment{$(\hat{m},\hat{\sigma})$ cannot repeat}
\Return $0$
\EndIf
\Return $[\Vrfy(\vk,\hat{m},\hat{\sigma})]$
\end{algorithmic}
\end{algorithm}

\begin{algorithm}
\algname{Oracle}
\caption{$\calO(m)$}
\begin{algorithmic}
\State $\sigma \gets \Sign(\sk,m)$
\State $\calQ \gets \calQ \cup \{(m, \sigma)\}$
\Return $\sigma$
\end{algorithmic}
\end{algorithm}

A DS scheme $\mathsf{DS}$ is SUF-CMA unforgeable if for all efficient $\mathcal{A}$,

$${\mathbf{Adv}}_{\mathsf{DS},\mathcal{A}}^{\mathrm{suf}\text{-}\mathrm{cma}}(\lambda ):=\mathrm{Pr}\left[{\mathbf{G}}_{\mathsf{DS},\mathcal{A}}^{\mathrm{suf}\text{-}\mathrm{cma}}(\lambda )=1\right]$$

is negligible.

Variations

Schnorr signatures

Schnorr signatures are built from the Schnorr identification protocol — a three-message sigma protocol for proving knowledge of a discrete logarithm — compiled to a signature via the Fiat-Shamir transform. For a generator $g$ of a group of prime order $p$, to sign $m$ with secret key $x$ (where $\mathsf{pk}=g^x$): sample $r\stackrel{\$}{\leftarrow }{\mathbb{Z}}_p$, compute $R=g^r$, $c=H(R\Vert m)$, $s=r+cx\mathrm{mod}p$; the signature is $(R,s)$. Verification checks $g^s=R\cdot {\mathsf{pk}}^c$.

Schnorr signatures (Sch91, via FS86) are EUF-CMA secure under the discrete logarithm assumption in the random oracle model — PS96, PS00. They support efficient multi-signatures whose signatures verify as Schnorr signatures, with the key included in the hash, under an aggregate public key (MuSig, MuSig2) — MPSW19, NRS21, and threshold signatures. Blinding the signer’s commitment and the challenge gives blind Schnorr signatures, analysed by Sch01 and FPS20.

For groups with compact encodings, such as elliptic-curve groups, two properties of the hash function, random-prefix preimage resistance and random-prefix second-preimage resistance, are necessary for the security of Schnorr signatures and, in the generic group model, sufficient; collision resistance is not among them — NSW09. The sufficiency theorem needs a further condition on how group elements are encoded as bit strings: a defective encoding of curve points meets its hypotheses while making Schnorr signatures insecure — Bro15.

EdDSA

EdDSA works in the subgroup of prime order $L$ generated by a base point $B$ of a twisted Edwards curve, written additively, with a hash function $H$ (SHA-512 for Ed25519). The secret key is a seed $k$ with $H(k)=(h,prefix)$, from which a clamped scalar $a$ is read off $h$; the public key is $A=aB$. To sign $m$, set $r=H(prefix\Vert m)\mathrm{mod}L$, $R=rB$ and $S=r+H(R\Vert A\Vert m)a\mathrm{mod}L$, and output $(R,S)$. Verification checks $SB=R+H(R\Vert A\Vert m)A$, or the same equation multiplied by the curve’s cofactor — BDLSY11. EdDSA is the Schnorr scheme with the public key included in the hash and nonces derived deterministically from the secret key and the message — standard.

BLS signatures

BLS signatures (Boneh-Lynn-Shacham) BLS01 use a bilinear pairing $e:{\mathbb{G}}_1\times {\mathbb{G}}_2\to {\mathbb{G}}_T$ to achieve unique, deterministic, and aggregatable signatures. To sign $m$: output $\sigma =H(m{)}^{\mathsf{sk}}\in {\mathbb{G}}_1$ (where $H:\{0,1{\}}^{\ast }\to {\mathbb{G}}_1$ is a hash-to-curve function). Verification checks $e(\sigma ,g_2)=e(H(m),\mathsf{pk})$.

Key properties:

• Deterministic: no per-signature randomness needed
• Short: one group element ($\approx 48$ bytes on BLS12-381)
• Aggregatable: $n$ signatures on distinct messages can be aggregated into one signature verifiable with $n+1$ pairings, checking $e(\sigma ,g_2)={\prod }_{i=1}^{n}e(H(m_i),{\mathsf{pk}}_i)$ — BGLS03
• co-CDH ⇒ BLS signatures

BLS signatures are used in Ethereum 2.0 for validator attestations and threshold BLS is widely used in threshold signature protocols.

Aggregate signatures

An aggregate signature scheme is a DS scheme $(\mathsf{KeyGen},\mathsf{Sign},\mathsf{Vrfy})$ with two further algorithms. $\mathsf{Agg}(({\mathsf{pk}}_1,m_1,{\sigma }_1),\dots ,({\mathsf{pk}}_n,m_n,{\sigma }_n))\to \sigma$ combines $n$ signatures, by possibly different signers on possibly different messages, into one, and $\mathsf{AggVrfy}(({\mathsf{pk}}_1,m_1),\dots ,({\mathsf{pk}}_n,m_n),\sigma )\to b$ checks an aggregate. Restrictions such as pairwise-distinct messages belong to a scheme’s $\mathsf{AggVrfy}$, not to the game. In the aggregate chosen-key model the adversary gets one honest key ${\mathsf{pk}}^{\ast }$ and a signing oracle for it, chooses every other key itself with no registration, and wins with an aggregate that verifies on a list whose first entry is $({\mathsf{pk}}^{\ast },m_1)$ for a message $m_1$ it never queried — BGLS03.

\begin{algorithm}
\algname{Game}
\caption{$\Game^{\mathrm{agg}}_{\Pi,\calA}(\secpar)$}
\begin{algorithmic}
\State $(\sk^*, \pk^*) \gets \KeyGen(1^\secpar)$; $\calQ \gets \{\}$
\State $((\pk_i, m_i)_{i \le n}, \sigma) \gets \calA^{\calO}(1^\secpar, \pk^*)$
\Comment{$\pk_2, \ldots, \pk_n$ are arbitrary}
\If{$\pk_1 \ne \pk^*$ or $m_1 \in \calQ$}
\Return $0$
\EndIf
\Return $[\AggVrfy((\pk_i, m_i)_{i \le n}, \sigma)]$
\end{algorithmic}
\end{algorithm}

\begin{algorithm}
\algname{Oracle}
\caption{$\calO(m)$}
\begin{algorithmic}
\State $\sigma \gets \Sign(\sk^*, m)$
\State $\calQ \gets \calQ \cup \{m\}$
\Return $\sigma$
\end{algorithmic}
\end{algorithm}

An aggregate signature scheme $\Pi$ is unforgeable in the aggregate chosen-key model if for all efficient $\mathcal{A}$,

$${\mathbf{Adv}}_{\Pi ,\mathcal{A}}^{\mathrm{agg}}(\lambda ):=\mathrm{Pr}\left[{\mathbf{G}}_{\Pi ,\mathcal{A}}^{\mathrm{agg}}(\lambda )=1\right]$$

is negligible.

Waters signatures

In a symmetric bilinear group $(\mathbb{G},{\mathbb{G}}_T,p,g,e)$, the Waters scheme for $n$-bit messages has $\mathsf{vk}=(g,g_1=g^{\alpha },g_2,u^{\prime },u_1,\dots ,u_n)$ with $\alpha \stackrel{\$}{\leftarrow }{\mathbb{Z}}_p$ and $g_2,u^{\prime },u_i\stackrel{\$}{\leftarrow }\mathbb{G}$, and $\mathsf{sk}=g_2^{\alpha }$. With $U(m)=u^{\prime }{\prod }_{i:m_i=1}{u}_i$, $\mathsf{Sign}(\mathsf{sk},m)$ samples $r\stackrel{\$}{\leftarrow }{\mathbb{Z}}_p$ and outputs $({\sigma }_1,{\sigma }_2)=(g_2^{\alpha }U(m{)}^r,g^r)$, and $\mathsf{Vrfy}(\mathsf{vk},m,\sigma )$ accepts iff $e({\sigma }_1,g)=e(g_1,g_2)\cdot e(U(m),{\sigma }_2)$ — Wat05. Signatures re-randomize publicly: for $t\stackrel{\$}{\leftarrow }{\mathbb{Z}}_p$, $({\sigma }_{1}U(m{)}^t,{\sigma }_2{g}^t)$ is a uniformly random valid signature on $m$ — standard.

Tight Diffie-Hellman signatures

Signatures whose security reduces tightly, without forking, to a Diffie–Hellman problem in a group of prime order $p$, with a hash modeled as a random oracle.

EDL signatures

The public key is $y=g^x$. To sign $m$, pick a random salt $r$, set $h=H(m,r)\in \mathbb{G}$ and $z=h^x$, and output $(z,r,\pi )$, where $\pi$ is a Fiat–Shamir Chaum–Pedersen proof that ${\log }_{g}y={\log }_{h}z$ — GJ03.

Katz-Wang signatures

The public key is $\mathsf{pk}=(g,h,y_1,y_2)$ with $y_1=g^x$ and $y_2=h^x$. To sign $m$, sample $r\stackrel{\$}{\leftarrow }{\mathbb{Z}}_p$ and output $(c,s)$ with $c=H(\mathsf{pk},g^r,h^r,m)$ and $s=r+cx\mathrm{mod}p$. Verification checks $c=H(\mathsf{pk},g^s{y}_1^{-c},h^s{y}_2^{-c},m)$. A signature is a Fiat–Shamir proof that $(g,h,y_1,y_2)$ is a Diffie–Hellman tuple — KW03, GJKW07.

Structure-preserving signatures

A DS scheme over a bilinear group $({\mathbb{G}}_1,{\mathbb{G}}_2,{\mathbb{G}}_T,p,e)$ is structure-preserving if its verification keys, messages and signatures are vectors of elements of ${\mathbb{G}}_1$ and ${\mathbb{G}}_2$, and $\mathsf{Vrfy}$ only checks group membership and a conjunction of pairing-product equations ${\prod }_{i,j}e(A_i,B_j{)}^{{\gamma }_{ij}}=1$, where the $A_i\in {\mathbb{G}}_1$ and $B_j\in {\mathbb{G}}_2$ are key, message and signature elements and public constants, and the ${\gamma }_{ij}\in {\mathbb{Z}}_p$ are public — AFG+10. Security is EUF-CMA. In a Type 3 bilinear group, every structure-preserving signature scheme whose signer uses only generic group operations has signatures of at least three group elements — AGHO11.

Optimally short structure-preserving signatures

Structure-preserving signature schemes in a Type 3 bilinear group whose signatures consist of three group elements, the minimum for a signer that uses only generic group operations — AGHO11.

ECDSA

ECDSA works in a subgroup of prime order $q$ generated by a point $G$ of an elliptic curve, with secret key $x\in {\mathbb{Z}}_q$ and public key $X=xG$. To sign $m$, sample $k\stackrel{\$}{\leftarrow }{\mathbb{Z}}_q^{\ast }$, set $r=f(kG)$, where the conversion function $f$ reduces the $x$-coordinate of a point modulo $q$, and $s=k^{-1}(H(m)+rx)\mathrm{mod}q$, and output $(r,s)$, resampling if $r=0$ or $s=0$. Verification checks $r=f(s^{-1}H(m)G+s^{-1}rX)$. DSA is the same scheme in a subgroup of prime order $q$ of ${\mathbb{Z}}_P^{\ast }$, with $f$ reducing the group element modulo $q$ — standard. Since $kG$ and $-kG$ have the same $x$-coordinate, $(r,-s\mathrm{mod}q)$ is again a valid ECDSA signature on $m$, so ECDSA is not strongly unforgeable — standard.

• ECDSA is EUF-CMA secure if the hash function is collision-resistant and has a uniformity property, the ephemeral-key generator is pseudorandom, the group is treated generically, and a further condition holds on the map from ephemeral public keys to scalars. That condition seems to fail for DSA — Bro05.
• Prior generic-group analyses of ECDSA in fact establish strong unforgeability, which ECDSA does not have, so their abstraction of the conversion function does not describe ECDSA faithfully — FKP16.
• With the conversion function modeled as two algebraic outer maps around an inner bijective random oracle, unmodified DSA and ECDSA are as hard to forge as DLOG, without assuming generic group behavior — FKP16.
• An algebraic security reduction for ECDSA can exist only if it programs the conversion function — HK23.
• If OMDL is hard, no algebraic reduction from DLOG proves DSA or ECDSA secure in the standard model (the barrier for Schnorr signatures) — PV05.

Hash-based signatures

Hash-based signatures need no number-theoretic or lattice assumption: one-time signatures follow from OWF — Lam79 — and many-time signatures from OWF — Rom90.

• CRHF + One-time signature ⇒ DS
• Hash function + PRF ⇒ DS (XMSS)
• SPHINCS+ is stateless: a hypertree of XMSS-style Merkle trees authenticates the keys of the few-time signature FORS at its leaves — BHK+19

One-time signatures

A one-time signature scheme is EUF-CMA secure against adversaries that make at most one signing query.

• OWF ⇒ One-time signatures (Lamport)

Lattice-based signatures

Lattice-based signatures achieve post-quantum security under LWE/SIS assumptions.

• Module LWE + Module-SIS ⇒ DS
• NTRU + NTRU-SIS ⇒ DS
• SIS ⇒ DS

Other results

• OWF ⇒ One-time signatures (Lamport)
• CRHF + One-time signature ⇒ DS
• FAC ⇒ DS
• DS ⇒ OWF
• For Waters signatures, whose signatures re-randomize publicly, every simple reduction of EUF-CMA security to a non-interactive hardness assumption, one that runs the forger only as straight-line instances one after another — MP18 — loses a factor $\Omega (q_S)$ for $q_S$ signing queries, unless the assumption is false (the barrier for Waters signatures) — HJK12. Coron’s earlier meta-reduction, stated for schemes with unique signatures, gives the corresponding bound for BLS signatures in the random-oracle model (the barrier for BLS signatures) — Cor02.
• For signature schemes whose relation between verification and signing keys is unique or re-randomizable, the security loss of passing from single-user EUF-CMA to multi-user EUF-CMA with adaptive corruptions cannot be avoided by reductions from a very general class of non-interactive assumptions — BJLS16. Their meta-reduction refines the one of Cor02.

Participates in

Builds on Digital signature

• BLS signatures ⇒ DS (via BLS signatures)
• Digital signatures ⇒ Byzantine broadcast (Dolev–Strong)
• DS ⇒ OWF
• EdDSA ⇒ DS (via EdDSA)
• EDL signatures ⇒ DS (via EDL signatures)
• CRHF + One-time signature ⇒ DS (via One-time signatures)
• Katz–Wang signatures ⇒ DS (via Katz-Wang signatures)
• Schnorr signatures ⇒ DS (via Schnorr signatures)
• Optimally short structure-preserving signatures ⇒ Structure-preserving signatures (via Optimally short structure-preserving signatures)
• Structure-preserving signatures ⇒ DS (via Structure-preserving signatures)
• UOWHF + One-time signature ⇒ DS (Naor–Yung) (via One-time signatures)
• Waters signatures ⇒ DS (via Waters signatures)

Produces Digital signature

• Bilinear pairing + q-SDH ⇒ DS (Boneh–Boyen)
• BLS signatures ⇒ DS
• co-CDH ⇒ Aggregate signatures (BGLS) (via Aggregate signatures)
• co-CDH ⇒ BLS signatures (via BLS signatures)
• DLOG ⇒ Schnorr signatures (via Schnorr signatures)
• DLOG ⇒ BLS signatures (via BLS signatures)
• EdDSA ⇒ DS
• EDL signatures ⇒ DS
• FAC ⇒ DS
• CRHF + One-time signature ⇒ DS
• OWF + iO ⇒ DS
• OWF ⇒ DS
• Hash function + PRF ⇒ DS (XMSS)
• OWF ⇒ One-time signatures (Lamport) (via One-time signatures)
• ID ⇒ DS
• Katz–Wang signatures ⇒ DS
• Module LWE + Module-SIS ⇒ DS
• NTRU + NTRU-SIS ⇒ DS
• Φ-Hiding ⇒ DS (RSA full-domain hash, tight)
• Prime-order CDH ⇒ EDL signatures (via EDL signatures)
• Prime-order DDH ⇒ Katz–Wang signatures (via Katz-Wang signatures)
• DLOG ⇒ EdDSA (via EdDSA)
• DLOG ⇒ Schnorr signatures (tight, AGM) (via Schnorr signatures)
• RSA ⇒ DS (Hohenberger–Waters, short and stateless)
• Schnorr identification ⇒ Schnorr signatures (Fiat–Shamir) (via Schnorr signatures)
• Schnorr signatures ⇒ DS
• Optimally short structure-preserving signatures ⇒ Structure-preserving signatures (via Structure-preserving signatures)
• SIS ⇒ DS
• Strong RSA + CRHF ⇒ DS
• Structure-preserving signatures ⇒ DS
• SXDH ⇒ Structure-preserving signatures (Kiltz–Pan–Wee) (via Structure-preserving signatures)
• TDP ⇒ DS (full-domain hash, random oracle model)
• Type 1 pairing + CDH ⇒ Waters signatures (via Waters signatures)
• Type 1 pairing + DLIN ⇒ Structure-preserving signatures, tightly (Hofheinz–Jager) (via Structure-preserving signatures)
• Type 1 pairing + LRSW ⇒ DS (Camenisch–Lysyanskaya)
• Type 3 pairing ⇒ DS (Pointcheval–Sanders)
• Type 3 pairing ⇒ Optimally short structure-preserving signatures (AGHO) (via Optimally short structure-preserving signatures)
• UOWHF + One-time signature ⇒ DS (Naor–Yung)
• Waters signatures ⇒ DS

Barriers

• No fixed-construction reduction from Fiat-Shamir + Hash function to DS
• No tight simple reduction from non-interactive assumptions to BLS signatures (via BLS signatures) — circumvented by co-CDH ⇒ BLS signatures, DLOG ⇒ BLS signatures
• No algebraic reduction from non-interactive assumptions to optimally short structure-preserving signatures (via Optimally short structure-preserving signatures)
• No tight simple reduction from non-interactive assumptions to Waters signatures (via Waters signatures) — circumvented by Type 1 pairing + CDH ⇒ Waters signatures
• No single-instance reduction from DLOG to Schnorr signatures in the non-programmable ROM (via Schnorr signatures) — circumvented by DLOG ⇒ Schnorr signatures, DLOG ⇒ Schnorr signatures (tight, AGM)
• No tight generic reduction from DLOG to Schnorr signatures (via Schnorr signatures) — circumvented by DLOG ⇒ Schnorr signatures, DLOG ⇒ Schnorr signatures (tight, AGM)
• No algebraic reduction from DLOG to Schnorr signatures in the standard model (via Schnorr signatures) — circumvented by DLOG ⇒ Schnorr signatures, DLOG ⇒ Schnorr signatures (tight, AGM)
• No tight algebraic reduction from DLOG to Schnorr signatures in the ROM (via Schnorr signatures) — circumvented by DLOG ⇒ Schnorr signatures, DLOG ⇒ Schnorr signatures (tight, AGM)