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."
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.
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.)
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.
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.
- 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,
pfitzmann@cs.uni-sb.de
Date of last real modification: Oct. 17, 1996