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 are the basis for EdDSA (e.g. Ed25519) — BDLSY11. They support efficient multi-signatures and threshold signatures.

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 ⇒ 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 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

Participates in

Builds on Digital signature

• DS ⇒ OWF
• CRHF + One-time signature ⇒ DS (via One-time signatures)

Produces Digital signature

• co-CDH ⇒ DS
• DLOG ⇒ Schnorr signatures (via Schnorr signatures)
• DLOG ⇒ BLS signatures (via BLS signatures)
• FAC ⇒ DS
• Schnorr identification ⇒ Schnorr signatures (Fiat–Shamir) (via Schnorr signatures)
• 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
• Module LWE + Module-SIS ⇒ DS
• NTRU + NTRU-SIS ⇒ DS
• SIS ⇒ DS
• Strong RSA + CRHF ⇒ DS

Barriers

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