Public key signatures and their security notions were defined in Section 1.3.2. They are arguably the most important topic in public key cryptography (for example, to provide authentication of automatic software updates; see Section 1.1). This chapter gives some digital signature schemes based on the discrete logarithm problem. The literature on this topic is enormous and we only give a very brief summary of the area. RSA signatures are discussed in Section 24.6.

Schnorr signatures

We assume throughout this section that an algebraic group G and an element g ∈ G of prime order r are known to all users. The values (G, g, r) are known as system parameters. Let h = ga be a user's public key. A digital signature, on a message m with respect to a public key h, can be generated by a user who knows the private key a. It should be hard to compute a signature for a given public key without knowing the private key.

To explain the Schnorr signature scheme it is simpler to first discuss an identification scheme.

The Schnorr identification scheme

Informally, a public key identification scheme is a protocol between a Prover and a Verifier, where the Prover has a public key pk and private key sk, and the Verifier has a copy of pk. The protocol has three communication stages: first, the Prover sends a commitment s0, then the Verifier sends a challenge s1 and finally the Prover sends a response s2. The Verifier either accepts or rejects the proof.