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 c,$ 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}[\mathsf{Vrfy}(\mathsf{vk},m,\mathsf{Sign}(\mathsf{sk},m))=1]\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 many samples

\begin{algorithm}
\algname{Game}
\caption{$\Game^{\eufcma}_{\DS,\calA}(\secpar)$}
\begin{algorithmic}
\State $(\sk, \vk) \gets \KeyGen(1^\secpar)$; $b \getsr \bits$
\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}[{\mathbf{G}}_{\mathsf{DS},\mathcal{A}}^{\mathrm{euf}\text{-}\mathrm{cma}}(\lambda )=1]$$

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)$; $b \getsr \bits$
\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 SU-CMA unforgeable if for all efficient $\mathcal{A}$,

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

is negligible.

Variations

Other results

• OWFs imply one-time digital signatures via Lamport’s scheme — Lam79
  • Lamport signatures are single-use; a single key pair signs at most one message securely
• Many-time signatures from OWFs are obtained by authenticating a collection of one-time verification keys using a Merkle hash tree, giving $O(\lambda )$-size signatures with a $\mathrm{poly}(\lambda )$-size public key — Mer89
• The foundational EUF-CMA security definition was introduced alongside the first construction of a many-time signature scheme secure under adaptive chosen-message attacks, based on factoring — GMR88
• Digital signatures imply OWFs: if signing is hard to forge, the signing algorithm is a one-way function (knowing the message and signature reveals nothing useful about the key)