Information-theoretic Cryptography

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. 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 This introductory graduate coursebook offers a mathematical foundation for modern cryptography. Coverage includes secret key agreement, authentication, secret sharing, and secure computation. The book will also serve experts in the field as a reference for information-theoretic tools such as smooth min/max entropies and information spectrum.