The Science Of Quantitative Information Flow

Preface......Page 6
Contents......Page 12
List of definitions, theorems, examples, etc.......Page 19
List of figures......Page 22
List of exercises......Page 23
Part I Motivation......Page 25
Chapter 1 Introduction......Page 26
1.1.2 Bayes vulnerability......Page 28
1.1.3 Deterministic channels......Page 29
1.1.4 Posterior distributions and hyper-distributions......Page 30
1.1.5 Posterior Bayes vulnerability......Page 31
1.1.6 Quantifying leakage......Page 32
1.2 Looking ahead......Page 33
1.3 Exercises......Page 34
1.4 Chapter notes......Page 35
Part II Secrets and How to Measure Them......Page 37
2.1 Secrets and probability distributions......Page 38
2.2 Shannon entropy......Page 39
2.3 Bayes vulnerability......Page 41
2.4 A more general view......Page 42
2.6 Chapter notes......Page 43
3.1 Basic definitions......Page 45
3.1.1 Graphing g-vulnerability......Page 47
3.2.1 The identity gain function......Page 49
3.2.2 Gain functions induced from distance functions......Page 50
3.2.3 Binary gain functions......Page 51
3.2.4 Gain functions for a password database......Page 53
3.2.5 A gain function that penalizes wrong guesses......Page 54
3.2.7 A loss function that gives guessing entropy......Page 55
3.2.8 A loss function that gives Shannon entropy......Page 57
3.3.1 Finite-valued, non-negative vulnerabilities......Page 59
3.3.3 Non-negative gain functions......Page 60
3.4 Mathematical properties......Page 61
3.4.1 Gain function algebra......Page 62
3.5 On ``absolute'' versus ``relative'' security......Page 63
3.7 Chapter notes......Page 64
Part III Channels and Information Leakage......Page 67
4.1 Channel matrices......Page 68
4.2 The effect of a channel on the adversary's knowledge......Page 70
4.3 From joint distributions to hyper-distributions......Page 73
4.4 Abstract channels......Page 76
4.5 More on abstract channels......Page 80
4.6.1 Convex combinations of channels......Page 82
4.6.2 Cascading and the Data-Processing Inequality......Page 83
4.7 Exercises......Page 84
4.8 Chapter notes......Page 85
5.1 Posterior g-vulnerability and its basic properties......Page 90
5.2 Multiplicative and additive g-leakage......Page 99
5.3 A closer look at posterior Bayes vulnerability and Bayes leakage......Page 101
5.4 Measuring leakage with Shannon entropy......Page 103
5.5.1 A matrix-based formulation of posterior g-vulnerability......Page 105
5.5.2 A trace-based formulation of posterior g-vulnerability......Page 106
5.5.3 A linear-programming formulation......Page 109
5.6 Example channels and their leakage......Page 110
5.7 Max-case posterior g-vulnerability......Page 112
5.8 Exercises......Page 113
5.9 Chapter notes......Page 116
6.1 The need for robustness......Page 120
6.4 Chapter notes......Page 122
7.1 Multiplicative Bayes capacity......Page 125
7.2 Additive Bayes capacity......Page 129
7.3 General capacities......Page 134
7.4.1 Fixed g, maximize over......Page 135
7.4.2 Fixed , maximize over g......Page 136
7.5.1 Fixed g, maximize over......Page 137
7.5.2 Fixed , maximize over g......Page 138
7.5.3 Maximize over both g and......Page 141
7.6.2 Improved miracle bounds......Page 142
7.6.3 Examples......Page 143
7.8 Chapter notes......Page 145
8.1 Compositions of (concrete) channel matrices......Page 149
8.1.1 Parallel composition......Page 150
8.1.2 External fixed-probability choice......Page 151
8.1.3 External conditional choice......Page 152
8.1.4 External (general) probabilistic choice......Page 153
8.1.5 Internal fixed-probability choice......Page 154
8.1.8 Cascading......Page 155
8.2.1 The issue of compositionality......Page 156
8.2.3 External fixed-probability choice......Page 157
8.2.6 The internal choices, and cascading......Page 158
8.3 Exercises......Page 160
8.4 Chapter notes......Page 161
9.1 Refinement: for the customer; for the developer......Page 164
9.2.1 Structural refinement for deterministic channels......Page 165
9.2.2 Structural refinement for probabilistic channels......Page 167
9.3 Testing refinement: the customer's point of view......Page 169
9.4 Soundness of structural refinement......Page 170
9.5 Completeness of structural refinement: the Coriaceous theorem......Page 171
9.6 The structure of abstract channels under refinement......Page 174
9.7.1 Compositionality for contexts......Page 176
9.8.1 Who gets to define refinement, anyway?......Page 177
9.8.2 A subjective argument: keeping the customer satisfied......Page 179
9.8.3 An objective argument: compositional closure......Page 181
9.9 Capacity is unsuitable as a criterion for refinement......Page 183
9.11 Chapter notes......Page 184
Chapter 10 The Dalenius perspective......Page 188
10.1 Dalenius scenarios......Page 189
10.2.1 Safety and necessity with respect to Dalenius contexts......Page 192
10.2.2 Justifying refinement: an example......Page 193
10.3 Bounding Dalenius leakage......Page 194
10.4 Chapter notes......Page 196
11.1 An axiomatic view of vulnerability......Page 199
11.2 Axiomatization of prior vulnerabilities......Page 201
11.2.1 Soundness and completeness of Vg with respect to continuous, convex functions......Page 202
11.3 Axiomatization of posterior vulnerabilities......Page 204
11.3.1 Possible definitions of posterior vulnerabilities......Page 205
11.4 Applications of axiomatization to understanding leakage measures......Page 213
11.5 Chapter notes......Page 215
Chapter 12 The geometry of hypers, gains and losses......Page 221
12.1 Barycentric representation of gain/loss functions......Page 224
12.2 Barycentric representation of hypers and their refinement......Page 226
12.3 Primitive hyper-distributions and their refinements......Page 229
12.4 Hyper-distributions are not a lattice under refinement......Page 232
12.5 A geometric proof of antisymmetry of refinement......Page 234
12.7 Chapter notes......Page 236
Part IV Information Leakage in Sequential Programs......Page 238
Chapter 13 Quantitative information flow in sequential computer programs......Page 239
13.1 Markovs don't leak; and channels don't update......Page 240
13.2.1 When is one program better than another, and why?......Page 242
13.2.2 When is one channel better than another, and why?......Page 243
13.3.1 Generalizing Hoare logic for probability......Page 244
13.3.2 Using loss functions......Page 245
13.3.3 Refinement in general......Page 246
13.3.4 Initial-final correlations, and Dalenius......Page 247
13.4.1 Sequential composition......Page 249
13.4.2 On the terms prior, posterior, initial and final......Page 254
13.4.3 Conditionals......Page 255
13.4.4 The power of the adversary: gedanken experiments......Page 256
13.5 Syntax for probabilistic choice......Page 257
13.7 Exercises......Page 260
13.8 Chapter notes......Page 261
14.1 Concrete Hidden Markov Models......Page 268
14.1.1 A priori versus a posteriori reasoning — in more detail......Page 270
14.2.2 Sequential composition of concrete HMM's......Page 271
14.3 Abstract Hidden Markov Models......Page 273
14.3.1 Sequential (Kleisli) composition of abstract HMM's......Page 274
14.4.1 Probabilistic assignment......Page 277
14.4.2 Information flow via channels: leaking with [PRINT]......Page 278
14.4.3 External probabilistic choice......Page 279
14.4.4 (Internal probabilistic choice)......Page 280
14.4.8 Local variables......Page 281
14.5 Leaks caused by conditionals and by external choice......Page 283
14.6.1 First example: Bertrand's Boxes......Page 285
14.6.2 Second example: Goldfish or piraña?......Page 287
14.7 Underlying and unifying structures: a summary......Page 288
14.8 Exercises......Page 291
14.9 Chapter notes......Page 292
15.1 Semantics, logic, and program algebra......Page 296
15.2 Static visibility declarations; multiple variables......Page 297
15.3.1 The Encryption Lemma......Page 299
15.3.3 The One-Time Pad......Page 300
15.4 Algebraic rules for reordering statements......Page 303
15.5 Larger example 1: Oblivious Transfer......Page 304
15.6 Larger example 2: Two-party conjunction, or The Lovers' protocol......Page 309
15.8 Refinement and quantitative analyses......Page 311
15.9 Exercises......Page 314
15.10 Chapter notes......Page 317
16.2 Classical nontermination......Page 319
16.3.1 Nontermination for markovs......Page 320
16.3.3 Applying abstract channels and markovs to sub-hypers......Page 322
16.4 The algebra of nontermination in QIF......Page 323
16.5 A refinement order on sub-hyper-distributions......Page 325
16.6 From nontermination to termination......Page 328
16.7 Example of (certain) termination: how to design a password checker......Page 329
16.8 A taxonomy of refinement orders......Page 331
16.10 Chapter notes......Page 333
17.1.1 Historical introduction, intuition and abstraction......Page 336
17.1.2 Structural definition of refinement for deterministic channels......Page 339
17.1.3 Testing, soundness and completeness: deterministic......Page 340
17.2 Our probabilistic partial order......Page 341
17.3 Basic structure of the demonic lattice......Page 342
17.4 Examples of demonically nondeterministic channels......Page 345
17.5 Testing, soundness and completeness: demonic......Page 347
17.6 A reformulation of demonic testing......Page 348
17.8 Compositional closure......Page 350
17.9 ``Weakest pre-tests'' and source-level reasoning......Page 353
17.10 Exercises......Page 356
17.11 Chapter notes......Page 357
Part V Applications......Page 362
18.1 Introduction to Crowds, and its purpose......Page 363
18.2 Modeling the Crowds protocol......Page 364
18.3 Bayes vulnerability and Bayes leakage......Page 367
18.4.1 Modified Crowds......Page 368
18.4.2 Vulnerability of the original protocol......Page 369
18.5 Why  matters, even for uniform priors......Page 370
18.6 Refinement: increasing  is always safe......Page 371
18.7.1 Paths recreated by the initiator......Page 373
18.7.2 Paths repaired by the last working node......Page 374
18.8 Exercises......Page 375
18.9 Chapter notes......Page 376
19.1 Cryptographic background......Page 378
19.2 A first leakage bound......Page 379
19.3 A better leakage bound......Page 381
19.4 Analytic results about capb(n)......Page 383
19.5 Analytic proofs......Page 387
19.6 Another proof of Theorem 19.5......Page 393
19.7 Chapter notes......Page 394
20.1 Evaluating a defense against side channels......Page 398
20.2 QIF exploration of the fast-exponentiation algorithm......Page 400
20.2.1 Cost/benefit analysis......Page 403
20.3 Chapter notes......Page 404
Chapter 21 Multi-party computation: The Three Judges protocol......Page 407
21.1 Introduction to The Three Judges......Page 408
21.2.1 First attempt......Page 409
21.2.2 Second development attempt (sketch)......Page 410
21.2.3 Successful development......Page 411
21.2.4 Two-party exclusive-or......Page 413
21.2.5 Summary......Page 414
21.4 Chapter notes......Page 417
22.1 Elections and privacy risks......Page 420
22.2.1 The tallying......Page 421
22.2.2 The casting......Page 422
22.2.3 The Dalenius perspective: casting then tallying......Page 423
22.3.1 QIF channels for simple-majority elections: two examples......Page 424
22.4 Election by preferences: instant run-off......Page 425
22.5 Gain functions for privacy of elections: a first example......Page 426
22.6 The effect of small electorates in general......Page 428
22.7.1 First past the post, in small electorates......Page 429
22.7.2 Instant run-off in small electorates......Page 433
22.8 Chapter notes......Page 436
Chapter 23 Differential privacy......Page 439
23.1 Notation and definition......Page 440
23.2 Mechanisms as information-theoretic channels......Page 441
23.3 The relation between differential privacy and multiplicative g-leakage......Page 442
23.3.1 Bounds on leakage do not imply differential privacy......Page 444
23.4 Exercises......Page 445
23.5 Chapter notes......Page 447
Glossary and Index......Page 451