Signature Scheme

cryptography

Definition

Signature Scheme

A signature scheme with a key space $\mathcal{K}$, a message space $\mathcal{M}$, and a signature space $\mathcal{S}$ is a triple of algorithms:

$$⟨\mathsf{Gen},\mathsf{Sign},\mathsf{Verify}⟩$$

where:

• The key generation algorithm $\mathsf{Gen}$ takes no input and returns a randomly selected key $k\in \mathcal{K}$.
• The signing algorithm $\mathsf{Sign}$ takes a key $k\in \mathcal{K}$ and a message $m\in \mathcal{M}$, and produces a signature $\sigma \in \mathcal{S}$:

$$\mathsf{Sign}:\mathcal{K}\times \mathcal{M}\to \mathcal{S}$$

• The verification algorithm $\mathsf{Verify}$ takes a key $k\in \mathcal{K}$, a message $m\in \mathcal{M}$, and a signature $\sigma \in \mathcal{S}$, and outputs a bit $b\in \{0,1\}$:

$$\mathsf{Verify}:\mathcal{K}\times \mathcal{M}\times \mathcal{S}\to \{0,1\}$$