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{vk}},$ 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 find a message-signature pair $(\hat{m},\hat{\sigma })$ even given oracle access to 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 strongly unforgeability under chosen message attacks (SUF-CMA) game. This security notion strenghtens the above EUF-CMA notation 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. 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 are EUF-CMA secure under the discrete logarithm assumption in the random oracle model — Sch91, FS86. They are the basis for EdDSA (Ed25519, the standard in TLS, SSH, and Signal) and support efficient multi-signatures and threshold signatures.

BLS signatures

BLS signatures (Boneh-Lynn-Shacham) 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 different messages can be aggregated into one signature verifiable with $n$ pairings
• co-CDH ⇒ DS

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

Hash-based signatures

Hash-based signatures achieve post-quantum security from collision-resistant hash functions alone — no number-theoretic assumptions.

• Hash function ⇒ Hash-based signatures
• Hash function ⇒ Hash-based signatures
• Hash function + Hash-based signatures ⇒ DS
• Hash function ⇒ Hash-based signatures
• Hash-based signatures + Hash-based signatures ⇒ DS

Security reduces to second-preimage resistance and pseudorandomness of the underlying hash function — no lattice or number-theoretic assumptions.

Lattice-based signatures

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

• LWE + SIS ⇒ DS
• NTRU ⇒ DS
• SIS ⇒ DS

Other results

• Hash function ⇒ Hash-based signatures
• Hash function ⇒ Hash-based signatures
• Hash function + Hash-based signatures ⇒ DS
• FAC ⇒ DS
• DS ⇒ Hash function

Participates in

Builds on Digital signature

• DS ⇒ Hash function

Produces Digital signature

• BDH ⇒ DS
• Bilinear pairing ⇒ DS
• co-CDH ⇒ DS
• DLOG ⇒ DS
• FAC ⇒ DS
• Fiat-Shamir + Schnorr signatures ⇒ DS
• Hash-based signatures + Hash-based signatures ⇒ DS
• Hash-based signatures ⇒ DS
• Hash function + Hash-based signatures ⇒ DS
• Hash function + iO ⇒ DS
• Hash function ⇒ DS
• ID + ROM ⇒ DS
• ISIS (Inhomogeneous SIS) ⇒ DS
• LWE + SIS ⇒ DS
• Module LWE + Module-SIS ⇒ DS
• Module-SIS ⇒ DS
• NTRU ⇒ DS
• ROM + ZKP ⇒ DS
• SIS ⇒ DS
• Strong RSA ⇒ DS

Barriers

• No reduction from Fiat-Shamir + Hash function to DS