Digital signatures based on discrete logarithms
Steven D. Galbraith⋆ · Cambridge University Press eBooks · 2012
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 = g a 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 s 0 , then the Verifier sends a challenge s 1 and finally the Prover sends a response s 2 . The Verifier either accepts or rejects the proof.