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

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."*

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.

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.)

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.

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.

- 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

- 5.1 The Main Ideas 48
- 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

- 6.1 Properties 125
- 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

- 7.1 Definition 149
- 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

- 8.1 Some Group and Number Theory 213
- 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

Birgit Pfitzmann, pfitzmann@cs.uni-sb.de