Birgit Pfitzmann:

Digital Signature Schemes

General Framework and Fail-Stop Signatures

LNCS 1100, Springer-Verlag, Heidelberg, August 1996

Pages: xvi + 396 pp. Price: DM 78,-; £ 36,50; FF 294,-; Lit. 86.140; öS 569,40; sFr 69,- (1 DM approx. 0.66$); ISBN 3-540-61517-2

Computer Science, Cryptology, Digital Communication. For researchers and professionals.

Book category: Monograph

Who should read it?

I tried to write the book in a way that the first half of it (Chapters 1-6) can be easily read by everybody interested in digital signatures. The second half is clearly intended for cryptographers and theoretical computer scientists, in particular those interested in fail-stop signatures.

At the end of this page you can find the table of contents.

But let me start my personal direct-marketing campaign by showing you what Springer-Verlag says about it:

"This book, based on the author's Ph.D. thesis, was selected during the 1995 GI (German Society for Informatics) Doctoral Dissertation Competition as the winning thesis in the foundations-of-informatics track. Securing integrity for digital communications in the age of global electronic information exchange and electronic commerce is vital to democratic societies and a central technical challenge for cryptologists. As core contribution to advancing the state of the art, the author develops the new class of digital fail-stop signatures. This monograph is self-contained regarding the historical background and cryptographic primitives used. For the first time, a general and sophisticated framework is introduced in which innovative fail-stop signatures are systematically presented and evaluated, from theoretical foundations to engineering aspects."

1. Why is it Interesting for Everybody?

Chapters 1-6 are of interest to anybody interested in the applications of digital signatures, including the 'ordinary user.'

Signature schemes are a central application of cryptology, arguably even more important than encryption schemes, i.e., schemes for keeping message contents secret. The first part of this book is the first text giving a complete overview of signature schemes, starting from the legal requirements. In particular, new schemes with special properties like "fail-stop" are treated, but they are not given much emphasis in the first part.

In particular, all other books I am aware of still introduce signatures as a variant of encryption. This view does not fit well with most systems, except for RSA. Moreover it often leads to signatures, symmetric authentication, and encryption being mixed up in practice. A view that starts from requirements on signatures has the additional advantage of allowing an integrated treatment of aspects that are often somewhat neglected as protocols "around" cryptographic primitives.

2. Why is it Interesting For Cryptographers?

This book, in particular Chapter 5, contains the first combination of cryptologic security definitions with high-level specifications. Usually, there is large gap between an entirely informal goal and an intricate complexity-theoretic definition, and many such definitions turned out to be unsatisfactory.

Such a combination makes the modeling process of cryptology transparent -- i.e., how do you write a security definition and assure yourself that it says what you meant. In other words, one could say that for the first time, an entire design process for a cryptologic system class is shown, from a high-level description over concrete definitions and constructions to lower bounds showing how near to the optimum the existing constructions are, with fail-stop signatures as an example.

Personally, I consider this part (with sketches of how to model other system classes in the same way) the most promising one for future work, in particular for larger cryptologic protocols such as payment systems, which currently have very unsatisfactory definitions, both for applications and for evaluating the security of concrete proposals. (Not to raise too high hopes, however: It should be easy to apply this approach to other integrity requirements, but privacy requirements are a lot more difficult.)

3. Why is it Interesting for Theoretical Computer Scientists and Mathematicians?

The text contains mathematically rigorous security definitions and proofs (in particular, from Chapter 7 onwards), which is rare among cryptology books. In particular, no book so far gave any formal definition of signatures. At most, formal definitions of primitives like one-way functions and zero-knowledge proofs were presented. Signature schemes etc. were treated as "protocols" that have no definition, but need careful heuristic engineering (even though there is a formal definition of "ordinary" signature schemes in an article by Goldwasser, Micali, and Rivest 1988).

This led several theoretical computer scientists I know to regarding such cryptographic protocols as not really serious. Furthermore, they were not really sure which of the statements "with negligible probability" in original papers to believe (in contrast to regarding them as just another heuristic), as the probability spaces are often only sketched. Thus I have been more careful with probability spaces than even most articles are; and indeed I got a few unexpected problems.

4. Fail-Stop Signatures

Fail-stop signatures were the original topic of this text, and have properties that make them interesting enough to be considered separately in texts on the legal relevance of signatures, at least in Germany. Their main advantage over ordinary digital signatures is: As long as the underlying cryptographic assumption is not broken (all practical signature schemes rely on such an assumption), one can be absolutely sure about this fact in legal disputes. This frees courts from a decision that they would otherwise have to make "blindly".

The more technical view of this property is that fail-stop signatures enable the supposed signer to actually prove forging in the case of a successful attack: If the signer is confronted with a forged signature, she can produce data called "proof of forgery" that will convince any other party that the underlying assumption was broken.

Table of Contents

1 Requirements on Digital Signature Schemes 1
1.1 Brief Survey of Applications 1
1.2 Legal Significance of Signatures 2
1.3 Consequences of the Legal Significance 4
1.4 Secure Hardware Support 6
1.5 Relation to Other Types of Schemes 8
1.6 A Variant: Invisible Signatures 10
2 History of Digital Signature Schemes 11
2.1 Classical Cryptography 11
2.2 Information-Theoretically Secure Symmetric Schemes 12
2.3 Invention of Digital Signature Schemes 13
2.4 Intuitively Constructed Digital Signature Schemes 18
2.5 Problems, Countermeasures, and Emerging Security Notions 22
2.6 "Provably Secure" Digital Signature Schemes 25
2.7 Special Variants 28
2.7.1 Special Signature Schemes 28
2.7.2 Signature-Related Schemes 29
3 Information-Theoretic Security for Signers: Introduction 33
3.1 Problems with Ordinary Digital Signature Schemes 33
3.2 One New Type: Fail-Stop Signature Schemes 35
4 Terminology 37
4.1 General Notation 37
4.2 Probabilities and Probabilistic Functions 37
4.3 Complexity 38
4.4 Interaction 40
4.4.1 Overview and Meta-Terminology 40
4.4.2 Some Terminology about Specifications 41
4.4.3 Interactive Functions and Algorithms 42
4.4.4 System Structure 44
4.4.5 Attackers 45
4.4.6 System Behaviour 45
4.4.7 Degrees of Fulfilling 46
5 Properties of Digital Signature Schemes 47
5.1 The Main Ideas 48
5.1.1 The Ideas and their Background 48
5.1.2 Problems, Alternatives, and Simplification 51
5.2 Service 55
5.2.1 What Kind of Specification? 56
5.2.2 Overview of the Services of Signature Schemes 58
5.2.3 Remarks on the Generality of the Definition 62
5.2.4 Interface Events in Detail 64
5.2.5 Specification and System Parameters 72
5.2.6 Towards Formalizations of Requirements 75
5.2.7 Minimal Requirements 81
5.2.8 Stronger Requirements 88
5.2.9 Multiple Specifications for Different Degrees of Security 91
5.2.10 Special Specification Parameters 96
5.2.11 Additional Transactions 97
5.2.12 Privacy Requirements 102
5.3 Structure 103
5.3.1 Minimal Structural Requirements 104
5.3.2 Additional Structural Properties 105
5.4 Security 109
5.4.1 Access of Attackers to System Parts 110
5.4.2 Influence of Attackers on Honest Users 112
5.4.3 Computational Assumptions and Notions of Fulfilling 116
5.4.4 Sketches of Expected Theorems and Proofs 121
6 Overview of Existing Schemes with Other than Ordinary Security 125
6.1 Properties 125
6.1.1 Top-Level Classification 125
6.1.2 Fail-Stop Signature Schemes 126
6.1.3 Invisible Signature Schemes with Dual Security 131
6.1.4 "Normal" Signature Schemes with Dual Security 132
6.1.5 Schemes with Information-Theoretic Security 133
6.2 Possible Applications and Legal Significance 134
6.2.1 Possible Benefits of Dual Security 135
6.2.2 Possible Benefits of Fail-Stop Security 138
6.3 Important Construction Ideas 139
6.3.1 Construction of Fail-Stop Signature Schemes 140
6.3.2 Construction of Invisible Signature Schemes with Dual Security 145
6.3.3 Construction of "Normal" Signature Schemes with Dual Security 146
6.3.4 Construction of Schemes with Information-Theoretic Security 147
7 Conventional Definitions of Fail-Stop Signature Schemes and General Reductions 149
7.1 Definition 149
7.1.1 Concentrating on Schemes with Special Risk Bearers 150
7.1.2 Top-Down Derivation of the Components 150
7.1.3 Breaking Down the Minimal Requirements 161
7.1.4 Breaking Down Additional Service Properties 166
7.1.5 Formal Security Definitions 168
7.2 Relations Between Security Properties 175
7.2.1 Security for the Signer "Backwards" 175
7.2.2 Unforgeability 180
7.3 Fail-Stop Signature Schemes with Prekey 184
7.3.1 Appropriate Zero-Knowledge Proof Schemes 185
7.3.2 Definition of Schemes with Prekey 192
7.3.3 Security of Schemes with Prekey 196
7.4 Relation to Ordinary Digital Signature Schemes 201
7.5 Constructions with Many Risk Bearers 203
7.5.1 Replication of Initialization 203
7.5.2 Multi-Party Function Evaluation in Initialization 207
8 Building Blocks 213
8.1 Some Group and Number Theory 213
8.1.1 Basic Facts from Group Theory 213
8.1.2 Basic Facts about Rings of Integers Modulo n 214
8.1.3 Generalized Blum Integers 216
8.1.4 Williams Integers 217
8.1.5 The Density of Primes 217
8.2 Functions with Large Preimage Sets 218
8.2.1 Discrete-Logarithm Case: Tuple Exponentiation 219
8.2.2 A Construction from Pairs of Permutations 221
8.2.3 Factoring Case: Iterated Squaring and Doubling (Or: A Useful Homomorphism on an Ugly Group) 223
8.3 Some Efficient Algorithms 228
8.4 Concrete Cryptologic Assumptions 230
8.4.1 Integer Factoring 230
8.4.2 Discrete Logarithm 233
8.5 Collision-Intractable Function Families 240
8.5.1 Overview 240
8.5.2 Definitions 244
8.5.3 Constructions in the Discrete-Logarithm Case 253
8.5.4 Constructions from Claw-Intractable Pairs of Permutations 273
8.5.5 Constructions in the Factoring Case 282
9 Constructions for One Message Block 289
9.1 Definition of Schemes for Signing Message Blocks 289
9.2 General Construction Framework 290
9.3 Implementation Based on the Discrete-Logarithm Assumption 299
9.4 Implementations Based on the Factoring Assumption 304
9.5 Complexity Overview 311
10 Signing Many Long Messages 313
10.1 Message Hashing 313
10.2 Bottom-up Tree Authentication 322
10.3 Top-Down Tree Authentication 325
10.4 Top-Down Tree Authentication with Small Amount of Private Storage 332
10.5 Discrete-Logarithm Scheme with Shorter Secret Key 339
10.6 The Case of a Fixed Recipient 343
11 Lower Bounds 345
11.1 Information-Theoretic Background 346
11.2 Random Variables in Fail-Stop Signature Schemes 348
11.3 Lower Bound on the Secret Random Bits Needed 349
11.4 Length of Signatures and Public Keys 356
11.5 Lower Bounds on Information-Theoretically Secure Signature Schemes 360
11.6 Comparison 366
References 371
Symbols 387
Index 391

Back to the SIRENE literature list or Birgit Pfitzmann's home page.
Birgit Pfitzmann,
Date of last real modification: Oct. 17, 1996