Asymmetric Cryptography

2Signatures and Security Notions

Marc FISCHLIN

Technische Universität Darmstadt, Germany

We introduce the notion of digital signature schemes and discuss some example schemes used in practice. We then discuss basic security properties of signature schemes, especially unforgeability and strong unforgeability under chosen-message attacks.

2.1. Signature schemes

In this section, we describe the interfaces of a digital signature scheme, and the minimal functional requirement that genuine signatures generated by the signer can be verified as correct. We then discuss two classical examples of such signature schemes.

2.1.1. Definition

As with handwritten signatures, we expect a digital signature σ to tie the content of a message m from some space of admissible messages to the signer. The signer is identified by a public key pk, which may be certified and thus attached to an identity. Since we expect only the signer to be able to create such signatures, the signer holds a matching secret key sk, generated together with pk via some KGen algorithm. Signing with the secret key sk is carried out by the Sig algorithm of the scheme, and verification under the public key pk is done via the Vf algorithm.

With the above interfaces, the three algorithms, KGen, Sig, and Vf, are not “connected” yet. This is done via the correctness property, mentioning that signatures generated by algorithm