Digital Signature Systems - Contemporary Cryptography - page 369

Chapter 15

Digital Signature Systems

In this chapter, we elaborate on digital signatures and DSSs. More specifically, we
introduce the topic in Section 15.1, elaborate on basic and secure systems in Sections
15.2 and 15.3, overview and discuss one-time signature systems, digital signatures
for streams, and variations of “normal” DSSs in Sections 15.4-15.6, and conclude
with some final remarks in Section 15.7. Note that all topics on cryptography
(including the ones itemized in the Preface) address digital signatures and DSSs
and that there are even a few topics that focus entirely on this topic (e.g., [1, 2]).

15.1 INTRODUCTION

In Section 2.3.2, we introduced, briefly discussed, and put into perspective digital
signatures and corresponding DSSs with appendix or message recovery. According
to Definitions 2.11 and 2.12, a DSS consists of three efficiently computable algo-
rithms (i.e., Generate , Sign ,and Verify or Recover ). In short, the Generate algorithm
is used to generate public key pairs (that consist of a signing key and a corresponding
verification key), the Sign algorithm is used to generate digital signatures, and the
Verify or Recover algorithm is used to verify the digital signatures in one way or
another. In either case, a DSS must be correct and secure to be useful in practice.

• Correctness means that valid signatures must be accepted. For DSSs with

appendix, this means that Verify ( k, m, Sign ( k − 1 ,m )) must return valid for
all public key pairs ( k, k − 1 ) and all messages m . Similarly, for DSSs with
message recovery, this means that Recover ( k, Sign ( k − 1 ,m )) must return m
for all public key pairs ( k, k − 1 ) and all messages m .

• Security means that it must be impossible or computationally infeasible (for

an adversary) to forge a signature (i.e., to compute, without knowledge of the