Asymmetric Signature Scheme

cryptography

Definition

Asymmetric Signature Scheme

An asymmetric signature scheme with a public key space $\mathcal{P}\mathcal{K}$, a private key space $\mathcal{S}\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 pair $(pk,sk)\in \mathcal{P}\mathcal{K}\times \mathcal{S}\mathcal{K}$.
• The signing algorithm $\mathsf{Sign}$ takes a private key $sk\in \mathcal{S}\mathcal{K}$ and a message $m\in \mathcal{M}$, and produces a signature $\sigma \in \mathcal{S}$:

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

• The verification algorithm $\mathsf{Verify}$ takes a public key $pk\in \mathcal{P}\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{P}\mathcal{K}\times \mathcal{M}\times \mathcal{S}\to \{0,1\}$$

Visualisation