Defining Digital Signatures

Digital signature overview 🔗

When Bob sends Alice a message, Alice needs to verify that it came from Bob

\rightarrow

use a

digital signature

No one can generate Bob's signature without his private key.

This authenticates the source, Bob, and the integrity of the message data.

A digital signature scheme consists of three polynomial-time algorithms.

KeyGen
( $\lambda$ $λ$ ) $\rightarrow$ $\to$ (pk, sk): Key generation.
- Takes a security parameter $\lambda$ and generates a public key (pk) and private key (sk).
Sign
(sk, m) $\rightarrow$ $\to$ $\sigma$ $σ$ : Signing.
- Takes a private key (sk) and message (m) and produces a digital signature ( $\sigma$ ).
Verify
(pk, m, $\sigma$ $σ$ ) $\rightarrow$ $\to$ {0, 1}: Verification.
- Takes a public key (pk), message (m), and digital signature ( $\sigma$ ) and checks whether the signature is valid.
- Returns 1 if valid, and 0 otherwise.

Correctness

: The verification algorithm must satisfy the following.

Consider a game between a challenger

C

and attacker

A

Setup: $C$ runs KeyGen( $\lambda$ ) to generate $(pk, sk)$ , then gives the public key $pk$ to $A$ .
Signing queries: $A$ $A$ requests signatures for messages $M_i$ $M_{i}$ a polynomial number of times.
- For each $M_i$ , $C$ executes $\text{Sign}(sk, M_i) → \sigma_i$ to generate a signature $\sigma_i$ and returns it to $A$ .
Output: $A$ $A$ returns $(M, \sigma)$ $(M, σ)$ .
- $M$ is a message that $C$ has not signed and differs from the messages for which $A$ requested signatures.
- If $A$ produces a valid signature for $M$ , namely $\sigma$ , then $A$ succeeds.

The success probability of

A

is defined as follows.

The signature scheme is strongly unforgeable under an adaptive chosen-message attack.

If the probability that a polynomial-time attacker

A

succeeds in this game is negligible, the scheme is strongly

unforgeable