This book offers a mathematical foundation for modern cryptography. It is primarily intended as an introduction for graduate students. Readers should have basic knowledge of probability theory, but familiarity with computational complexity is not required. Starting from Shannon's classic result on secret key cryptography, fundamental topics of cryptography, such as secret key agreement, authentication, secret sharing, and secure computation, are covered. Particular attention is drawn to how correlated randomness can be used to construct cryptographic primitives. To evaluate the efficiency of such constructions, information-theoretic tools, such as smooth min/max entropies and information spectrum, are developed. The broad coverage means the book will also be useful to experts as well as students in cryptography as a reference for information-theoretic concepts and tools.
Cryptography is the science underlying all online payment systems and more recent blockchain and crypto engineering waves. Despite its popularity and its importance, it is quite difficult for most people outside the theoretical cryptography community to verify the security of basic cryptographic primitives. The reason for this is that cryptography has evolved rather rapidly and using a language which is not easily accessible by outsiders. Even for people working in related theoretical areas such as information theory or quantum physics, it is not easy to follow the ideas and details.
Admittedly, most exciting developments in practical cryptography have relied on computationally secure primitives, which can only be treated formally using these abstractions. Nonetheless, one would expect that information-theoretically secure cryptography could be understood without overly subscribing to these abstractions. Unfortunately, these details are scattered across technical papers and online lecture notes. This book is an attempt to collate this information in one place, in a form that is accessible to anyone with basic knowledge of probability.
Specifically, computational cryptography assumes the availability of certain computational primitives such as one-way functions which are easy to compute but computationally hard to invert. Using such primitives, we design cryptographic protocols that remain secure as long as the adversary is computationally restricted to using polynomial-time algorithms. On the other hand, information-theoretic cryptography seeks to establish cryptographic protocols that are information-theoretically secure. Often this requires additional resources; for instance, encryption is possible only when the parties share secret keys and two-party secure computation requires the availability of nontrivial correlated observations (such as oblivious transfer).
This book is a comprehensive presentation of information-theoretically secure cryptographic primitives, with emphasis on formal security analysis.
Author(s): Himanshu Tyagi, Shun Watanabe
Publisher: Cambridge University Press
Year: 2023
Language: English
Pages: 519
Contents
Preface page xiii
1 Introduction 1
1.1 Information Theory and Cryptography 1
1.2 Overview of Covered Topics 2
1.3 Overview of the Technical Framework 6
1.4 Possible Course Plans 9
1.5 References and Additional Reading 11
Part I External Adversary: Encryption, Authentication, Secret Key 13
2 Basic Information Theory 15
2.1 Very Basic Probability 16
2.2 The Law of Large Numbers 19
2.3 Convex and Concave Functions 20
2.4 Total Variation Distance 22
2.5 Kullback–Leibler Divergence 27
2.6 Shannon Entropy 29
2.7 Mutual Information 32
2.8 Fano’s Inequality 34
2.9 Maximal Coupling Lemma 35
2.10 A Variational Formula for KL Divergence 38
2.11 Continuity of Entropy 38
2.12 Hoeffding’s Inequality 39
2.13 Pinsker’s Inequality 42
2.14 R ́enyi Entropy 43
2.15 References and Additional Reading 44
3 Secret Keys and Encryption 47
3.1 Secure Communication 47
3.2 Approximate Security 50
3.3 Approximately Secure Keys 57
3.4 Security and Reliability 60
3.5 References and Additional Reading 63
viii Contents
4 Universal Hash Families 66
4.1 A Short Primer on Finite Fields 66
4.2 Universal Hash Family: Basic Definition 69
4.3 Strong Universal Hash Families 72
4.4 Example Applications 74
4.5 Almost Universal Hash Families 76
4.6 Practical Constructions 80
4.7 References and Additional Reading 85
5 Hypothesis Testing 87
5.1 Binary Hypothesis Testing: The Neyman–Pearson Formulation 87
5.2 The Neyman–Pearson Lemma 89
5.3 Divergence and Hypothesis Testing 91
5.4 Stein’s Lemma 93
5.5 A Primer on Method of Types 95
5.6 Composite Hypothesis Testing 100
5.7 References and Additional Reading 101
6 Information Reconciliation 104
6.1 Source Coding and Smooth Max-entropy 104
6.2 Source Coding with Side-information and Conditional Smooth
Max-entropy 106
6.3 Evaluation of Smooth Max-entropies 109
6.4 References and Additional Reading 115
7 Random Number Generation 118
7.1 Random Number Generation 118
7.2 Leftover Hashing 122
7.3 Leftover Hashing with Side-information 124
7.4 Smoothing 128
7.5 A General Leftover Hash Lemma 131
7.6 Evaluation of Smooth Min-entropies 133
7.7 References and Additional Reading 135
8 Authentication 139
8.1 Message Authentication Using Secret Keys 139
8.2 MAC with Optimal Attack Detection Probabilities 142
8.3 MAC with Optimal Length Secret Keys 146
8.4 Authentication of Multiple Messages 148
8.5 Nonmalleability 153
8.6 References and Additional Reading 155
9 Computationally Secure Encryption and Authentication 158
9.1 One-time Encryption Revisited 159
Contents ix
9.2 Pseudorandom Generators and Computational Security 161
9.3 CPA Secure Encryption and Pseudorandom Functions 164
9.4 CCA Secure Encryption and Authentication 170
9.5 References and Additional Reading 175
10 Secret Key Agreement 177
10.1 Information-theoretic Secret Key Agreement 177
10.2 Information Reconciliation and Privacy Amplification 180
10.3 Impossibility Bounds 182
10.4 Secret Key Capacity 189
10.5 Protocols with Interactive Communication 197
10.6 References and Additional Reading 203
Part II Internal Adversary: Secure Computation 207
11 Secret Sharing 209
11.1 Threshold Schemes 209
11.2 Ramp Schemes 213
11.3 Secret Sharing Schemes with a General Access Structure 216
11.4 Dishonest Share Holders 219
11.5 Error Correction and Secret Sharing 222
11.6 References and Additional Reading 224
12 Two-party Secure Computation for a Passive Adversary 227
12.1 Secure Computation with Interactive Communication 227
12.2 Secure Computation of Asymmetric Functions and Randomized
Functions 232
12.3 Perfect Secure Computation from Scratch 235
12.4 Oblivious Transfer 247
12.5 Oracle Access and Memoryless Channels 249
12.6 Completeness of Oblivious Transfer 250
12.7 Classification of Deterministic Symmetric Functions 256
12.8 References and Additional Reading 259
13 Oblivious Transfer from Correlated Randomness 262
13.1 Information-theoretic Construction of Oblivious Transfer 262
13.2 String Oblivious Transfer from Correlation 264
13.3 Construction of Oblivious Transfer from Correlation 265
13.4 Impossibility Results 274
13.5 Oblivious Transfer Capacity 278
13.6 Proof of Characterization of Complete Functions 280
13.7 References and Additional Reading 284
x Contents
14 Bit Commitment from Correlated Randomness 290
14.1 Bit Commitment 290
14.2 Example Applications 291
14.3 Standalone Security of Implemented Bit Commitment 293
14.4 Schemes for Implementing Bit Commitment Protocols 296
14.5 Impossibility Result 305
14.6 Bit Commitment Capacity 307
14.7 References and Additional Reading 308
15 Active Adversary and Composable Security 312
15.1 Functions and Protocols 312
15.2 Admissible and Nonadmissible Attacks 316
15.3 Perfect Standalone Security 318
15.4 Approximate Standalone Security and Protocols with Abort 329
15.5 Composable Security and the Sequential Composition Theorem 336
15.6 Security for Multiphase Functions 341
15.7 Complete Fairness and Relaxation 350
15.8 Concurrent Composition 351
15.9 Oblivious Transfer from Correlated Randomness: Active Adversary 354
15.10 References and Additional Reading 358
16 Zero-knowledge Proof 362
16.1 Interactive Proofs and Zero-knowledge Proofs 362
16.2 Zero-knowledge Proof for an NP Language 366
16.3 Multi-prover Interactive Proofs 367
16.4 Parallel Repetition 368
16.5 References and Additional Reading 371
17 Two-party Secure Computation for an Active Adversary 374
17.1 The AND Function 375
17.2 The Committed Copy Function 378
17.3 Proving Linear Relations 383
17.4 The Committed Oblivious Transfer Function 386
17.5 Security Analysis of the Protocol for AND 393
17.6 References and Additional Reading 397
18 Broadcast, Byzantine Agreement, and Digital Signature 399
18.1 Multiparty Communication Model 399
18.2 Broadcast and Byzantine Agreement 402
18.3 Broadcast from Scratch 407
18.4 Impossibility of Broadcast from Scratch without a Supermajority 411
18.5 Broadcast without a Supermajority 415
18.6 Computationally Secure Digital Signature 423
18.7 References and Additional Reading 424
Contents xi
19 Multiparty Secure Computation 432
19.1 Multiparty Computation Formulation 432
19.2 Secure Computation from Scratch for a Passive Adversary 434
19.3 Verifiable Secret Sharing 439
19.4 Secure Computation for an Active Adversary 447
19.5 Beyond an Honest Majority 453
19.6 References and Additional Reading 459
Appendix Solutions to Selected Problems 462
References 473
Symbol Index 495
Index
