Digital signature scheme

From CRYPTUTOR

A digital signature scheme provides a way for a party to unforgeably "sign" a message, and for anyone to verify that the signature was generated by the signer. It is a public-key analog of a MAC, but also provides non-repudiation.

Contents 1 Definition 2 Non-repudiation 3 One-time digital signature scheme 4 See also

Definition

A digital signature scheme scheme consists of the following 3 algorithms:

• Key generation (KeyGen): a probabilistic algorithm that takes the implicit security parameter of the scheme as input, and outputs a signing/verification key pair (SK,VK).
• Signing (Sign): an algorithm that takes a signing key and a message as input, and outputs a signature. We generally write as .
• Verification (Ver): An algorithm that takes a verification key, a message, and a signature as input, and outputs a bit. As above, we generally write as .

These algorithms must satisfy the following properties:

• Efficiency: All three algorithms run in polynomial time in the security parameter.
• Correctness: For all , and all messages m,
• Unforgeability: For all non-uniform PPT (polynomial in the security parameter) adversaries A, the probability that A succeeds in the following experiment is negligible (in the security parameter):

Digital Signature Unforgeability Experiment:

1. We choose a key pair and give VK to A.
2. A is allowed to query an oracle that computes .
3. A outputs a message/signature pair (m,σ), with the restriction that the oracle was never queried on input m.

We say that A succeeds if .

Non-repudiation

Unlike in a MAC, if we are shown a message and signature that verifies, we can be convinced that the holder of the signing key must have produced that signature.

One-time digital signature scheme

A weak variant of a digital signature scheme is that of a one-time digital signature scheme. In this variant, we modify the unforgeability experiment so that the adversary can only get one signature from the Sign oracle:

One-Time Digital Signature Unforgeability Experiment:

1. We choose a key pair and give VK to A.
2. A outputs a single message m.
3. We give to A.
4. A outputs a message/signature pair (m',σ), with the restriction that .

We say that A succeeds if .

See also

• Lamport's one-time signature scheme