Title Page 1
Preface 4
Organization 5
Table of Contents 8
Practical Cryptanalysis of SFLASH 12
Introduction 12
Description of SFLASH 13
The Multiplicative Property of the Differential 14
Recovering Multiplications from the Public Key 16
Recovering a Full $C*$ Public Key 18
Breaking SFLASH When the Number of Deleted Quadratic Equations $r$ Is Up to $n/2$ 20
Comparison with the Method of Dubois $et al$.[1] 21
Conclusion 22
Full Key-Recovery Attacks on HMAC/NMAC-MD4 and NMAC-MD5 24
Introduction 24
Background and Notation 28
MD4 and MD5 28
Collision Attacks Based on Differential Cryptanalysis 28
Key-Recovery Attacks on HMAC and NMAC 29
Extracting Hash Collisions from NMAC Collisions 30
IV-Recovery Attacks 31
Subtleties Between the Inner and Outer Keys 33
Summary 33
Attacking HMAC/NMAC-MD4 34
Our IV-Recovery Attack Against MD4 34
Deriving a Composite IV-Recovery Attack Against MD4 35
MD4 Attack Summary 36
Attacking NMAC-MD5 36
The IV-Recovery Attack Against MD5 37
Deriving a Composite IV-Recovery Against MD5 37
MD5 Attack Summary 37
Improving the MD4 IV-Recovery 39
Reducing the Online Cost 39
Reducing the Offline Cost 39
IV-Dependent Differential Path 40
How Should We Solve Search Problems Privately? 42
Introduction 42
This Work 44
Definitions 47
Equivalence Protecting Privacy Definition 48
Private Algorithms for Monotone Search Problems 49
Applications of the Construction 50
Resemblance Preserving Algorithms 51
Generic Constructions of Resemblance Preserving Algorithms 53
Resemblance Preserving Using Pairwise Independence 55
Applications of the Pairwise Independence Construction 55
Deterministic vs. Randomized Private Algorithms 60
Public Key Encryption That Allows PIR Queries 61
Introduction 61
Reference Table of Notation 64
Ingredients 65
Bloom Filters 65
Oblivious Modification 68
Modifying Encrypted Data in a Communication-Efficient Way 69
Definitions 70
Extensions 72
Main Construction 73
Information Security Economics \u2013 and Beyond 79
Introduction 79
Foundational Concepts 80
Misaligned Incentives 80
Security as an Externality 82
Applications 84
Economics of Vulnerabilities 84
Economics of Privacy 86
Incentives and the Deployment of Security Mechanisms 88
Protecting Computer Systems from Rational Adversaries 89
The Role of Governments 90
Open Problems 92
Algorithmic Mechanism Design 92
Network Topology and Information Security 93
Large Project Management 94
Psychology and Security 95
Conclusions 97
Cryptography with Constant Input Locality (Extended Abstract) 103
Introduction 103
Our Results 105
Our Techniques 105
Previous Work 106
Preliminaries 107
Randomized Encoding 108
Randomized Encoding with Constant Input Locality 109
Primitives with Constant Input Locality and Output Locality 111
Main Assumption: Intractability of Decoding Random Linear Code 111
Pseudorandom Generator in Local^3_3 112
Commitment in Local_3^4 114
Semantically Secure Public-Key Encryption in Local_3^$O$(1) 115
Negative Results for Cryptographic Primitives 117
MACs and Signatures 118
Non-malleable Encryption 118
Negative Results for Randomized Encodings 119
A Necessary Condition for Encoding with Low Input Locality 119
Impossibility of Universal Encoding for Linear Functions 120
Universally-Composable Two-Party Computation in Two Rounds 122
Introduction 122
Framework, Tools, and Assumptions 125
Round-Efficient UC Two-Party Computation 127
A Two-Round Protocol for Single-Output Functionalities 127
A Two-Round Protocol for Two-Output Functionalities 130
Two Rounds Are Necessary 136
Two-Round Universally-Composable Blind Signatures 136
Indistinguishability Amplification 141
Introduction 141
Indistinguishability Amplification for Random Variables 141
Contributions of This Paper 142
Discrete Systems, Indistinguishability, and Game-Winning 143
Related Work and Applications 144
Random Systems 145
Random Systems 145
Special Random Systems 146
Distinguishing Random Systems 147
Game-Winning and Monotone Binary Outputs 149
Relating Indistinguishability and Game-Winning 150
From Game-Winning to Indistinguishability 150
From Indistinguishability to Game-Winning 150
Amplification of the Distinguishing Advantage 153
Neutralizing Constructions 153
Winning Independent Games 154
The Product Theorem 155
Implications of the Product Theorem 156
Amplification of the Distinguisher Class 158
A Hybrid Lattice-Reduction and Meet-in-the-Middle Attack Against NTRU 161
Introduction 161
Roadmap 162
The NTRU Cryptosystem 162
Lattice Attacks Against NTRU 163
Odlyzko's Meet-in-the-Middle Attack on NTRU 164
Choosing NTRUEncrypt Parameters 165
Lattice Basis Representation and Lattice Reduction 166
Reducing the NTRU Public Basis 167
The Hybrid Lattice-Reduction and Meet-in-the-Middle Method 169
Results 173
A Small Example 173
$ees251ep6$ with $m=302$ 174
A Table of Results with an Extrapolation 174
Lessening Storage Requirements 175
Generalizations 176
Conclusions 178
Improved Analysis of Kannan\u2019s Shortest Lattice Vector Algorithm (Extended Abstract) 181
Introduction 181
Background on Lattice Reduction 184
Kannan's SVP Algorithm 185
Short Lattice Points Enumeration 185
Solving SVP 186
Cost of Kannan's SVP Solver 187
Complexity of the Enumeration Procedure 188
Integer Points in Hyper-Ellipsoids 189
The Case of Quasi-HKZ-Reduced Bases 190
A Property on the Geometry of HKZ-Reduced Bases 190
CVP and Other Related Problems 192
Practical Implications 193
Pre-processing Before Enumerating 193
Estimating the Cost of Solving SVP 194
Domain Extension of Public Random Functions: Beyond the Birthday Barrier 198
Introduction 198
Secret vs. Public Random Functions 198
Domain Extension and the Birthday Barrier 199
Significance of Domain Extension for Public Random Functions 200
Contributions and Outline of This Paper 202
Preliminaries 203
Notation and Probabilities 203
Indistinguishability of Random Systems 203
Indifferentiability, Reductions, and Public Random Primitives 205
Beyond-Birthday Domain Extension for Public Random Functions 206
The Construction 206
Input-Restricting Functions 207
Main Result 208
Proof of Theorem 1 209
Existence of Input-Restricting Function Families 211
Constructing Public Random Oracles 213
Random Oracles and Auxiliary Input 216
Introduction 216
Our Results 221
Related Work 222
Further Applications 223
Organisation 223
Notation 223
Lazy Sampling with Auxiliary Input 224
Example: One-Wayness of the Random Oracle 228
Security Amplification 230
OAEP Encryption 232
Open Questions 233
Security-Amplifying Combiners for Collision-Resistant Hash Functions 235
Introduction 235
Preliminaries 238
Hash Functions and Combiners 238
Our Model 239
Lucky Collisions 240
Security Amplification 241
Warming Up: Attack on the Classical Combiner 241
Basic Conclusions 243
A Security-Amplifying Combiner 246
Proof of Security Amplification 247
Proof of Chosen Pre-image Resistance (Lemma 3) 249
Proof of $\\collfinder$-Replication Resistance (Lemma 5) 251
Proof of Security Amplification (Theorem 1) 251
Hash Functions and the (Amplified) Boomerang Attack 255
Introduction 255
The Boomerang Attack 256
Adapting the Boomerang Attack to Hash Functions 257
Neutral Bits Approach 259
Explicit Conditions Approach 260
Application to $SHA-1$ 261
A Short Description of $SHA-1$ 261
Previous Attacks on $SHA-1$ 262
Building Auxiliary Differential Paths 263
Placing Auxiliary Differential Paths 266
Using Auxiliary Differential Paths 267
Complexity Analysis for a Full Collision Attack 268
Conclusion 269
Amplifying Collision Resistance: A Complexity-Theoretic Treatment 275
Introduction 275
This Work 276
Preliminaries 281
Quantitative Definitions of Collision Resistance 281
Black-Box Combiners for Collision Resistance 282
Constructions 283
Amplification Via Concatenation 283
Amplification Via Codes 285
Reducing the Key Size 286
Reducing the Output Length 288
Limitations 290
How Many Oblivious Transfers Are Needed for Secure Multiparty Computation? 295
Introduction 295
Our Contribution 297
Preliminaries 298
Counting OT Channels: Upper and Lower Bounds 299
Upper Bounds for $t = (1-\\delta)n$: The Committees Method 300
Lower Bounds for $t=n-1$: Full OT Network Is Necessary 302
Lower Bounds for Corruption of $t = n-d$ Parties 303
Upper Bounds for the Case of $t = n-1$ 304
The Tables Method 304
Applying the Tables Method 305
Oblivious Linear Branching Programs 306
Functions Captured by Linear Branching Programs 307
Secure Computation for Non-deterministic LBP 308
Simulatable VRFs with Applications to Multi-theorem NIZK 314
Introduction 314
On Defining sVRFs 318
Simplifying the Definition 319
Weak Trapdoor-Indistinguishable sVRF 320
Construction Based on General Assumptions 323
Efficient Construction 324
Multi-theorem NIZK from One-Theorem NIZK Via sVRFs 329
Cryptography in the Multi-string Model 334
Introduction 335
Non-interactive Zero-Knowledge 336
Multi-party Computation 337
Definitions 338
Multi-string NIZK Proofs Based on General Assumptions 341
Multi-string NIZK Proofs from Groups with a Bilinear Map 343
UC Commitment in the Multi-string Model 347
Multi-party Computation 349
Secure Identification and QKD in the Bounded-Quantum-Storage Model 353
Introduction 353
Preliminaries 357
Notation and Terminology 357
Tools 359
The Identification Scheme 360
The Setting 360
The Intuition 360
The Basic Scheme 361
An Error-Tolerant Scheme 363
Defeating Man-in-the-Middle Attacks 365
The Approach 365
The Setting 365
An Additional Tool: Extractor MACs 366
The Scheme 366
Application to QKD 369
A Tight High-Order Entropic Quantum Uncertainty Relation with Applications 371
Introduction 371
Preliminaries 376
Notation and Terminology 376
Smooth R茅nyi Entropy 377
Azuma's Inequality 377
The Uncertainty Relation 378
Application: Oblivious Transfer 380
Privacy Amplification and a Min-Entropy-Splitting Lemma 380
The Definition 381
The Protocol 382
Security Against Memory-Bounded Dishonest Receivers 383
Application: Quantum Bit Commitment 384
Application: Quantum Key Distribution 385
Open Problems 387
Finding Small Roots of Bivariate Integer Polynomial Equations: A Direct Approach 390
Introduction 390
Preliminaries 392
Our New Algorithm 393
Computing a Basis of $L_2$ 399
Difference with the Algorithm in [9] 399
Extension to More Variables 400
Practical Experiments 400
Conclusion 402
Proof of Lemma 1 403
Proof of Lemma 3 403
A Polynomial Time Attack on RSA with Private CRT-Exponents Smaller Than N^0.073 406
Introduction 406
Finding Small Roots of Polynomials 408
The Bleichenbacher-May Attack 409
The New Attack on RSA-CRT 410
Extending the Attack to Other Values of $\\alpha$ 411
Implementation Using Coppersmith's Original Method 412
Extracting the Common Root 415
Experiments 416
Experiments for Small $e$ 417
Experiments for Full Size $e$ 418
Calculating the Bound and Finding More Polynomials 421
A Related Attack by Galbraith, Heneghan, and McKee 422
Invertible Universal Hashing and the TET Encryption Mode 423
Introductions 423
The Underlying Hashing Scheme 426
BPE: A Blockwise Universal Hashing Scheme 426
The TET Mode of Operation 429
Tweaks and Variable Input Length 430
Partial Blocks 430
The PRF Function 431
Some Other Details 431
Performance of TET 433
Security of TET 436
Conclusions 437
Preliminaries 438
Intellectual-Property Issues 439
Reducing Trust in the PKG in Identity Based Cryptosystems 441
Introduction 441
Preliminaries 445
Bilinear Maps 445
Complexity Assumptions 445
Miscellaneous Primitives 446
The Definitions and the Model 447
Construction Based on Gentry's Scheme 449
The Construction 450
Security Proofs 451
Construction Based on Decisional BDH Assumption 453
The Construction 454
Future Work 456
Efficient Ciphertext Sanity Check in the Second Construction 458
Pirate Evolution: How to Make the Most of Your Traitor Keys 459
Introduction 459
The Subset-Cover Revocation Framework 462
Pirate Evolution 464
A Trace and Revoke Scheme Immune to Pirate-Evolution 466
Pirate Evolution for the Complete Subtree Method 467
Pirate Evolution for the Subset Difference Method 469
A Security Analysis of the NIST SP 800-90 Elliptic Curve Random Number Generator 477
Introduction 477
The Elliptic Curve Random Number Generator 479
Lemmas on Indistinguishability 480
The Decisional Diffie-Hellman Problem 481
The x-Logarithm Problem 481
Security of the Raw ECRNG Outputs Points 485
Truncated Point Problem and Security of the Full ECRNG 487
Unpredictability of the Next State from the Current Output 491
A Caution About the Truncated Point Problem for Binary Curves 492
A Generalization of DDH with Applications to Protocol Analysis and Computational Soundness 493
Introduction 493
A Generalization of the Decisional Diffie-Hellman Problem 496
The $DDH$ Problem 496
The (P,Q)-$DDH$ Problem 497
Our Main Result: $DDH$ Implies (P,Q)-$DDH$ 498
Applications: Simple Proofs for Diffie-Hellman-Based Protocols 503
A Symbolic Logic for Diffie-Hellman Exponentials and Encryption 505
Conclusion 509
Chernoff-Type Direct Product Theorems 511
Introduction 511
Weakly Verifiable Puzzles 513
Related Work 514
Techniques 515
Preliminaries 515
Proof of the Main Theorem 516
Assuming Oracle $\\mathcal{O}^{G}$ Exists 516
Removing the Oracle $\\mathcal{O}^{G}$ 518
Open Problems 525
Rerandomizable RCCA Encryption 528
Introduction 528
Definitions 530
Encryption and Security Definitions 530
Decisional Diffie-Hellman (DDH) Assumption 532
Motivating the Double-Strand Construction 533
Our Construction 534
Double-Strand Malleable Encryption Scheme 534
Double-Strand Cramer-Shoup Encryption Scheme 535
Complexity 537
Replayable Message Posting 537
Results 539
Extensions 541
Anonymity 543
Conclusions and Future Directions 543
Deterministic and Efficiently Searchable Encryption 546
Introduction 546
Notation and Conventions 550
Deterministic Encryption and Its Security 550
Secure Deterministic Encryption Schemes 552
Encrypt-with-Hash 552
RSA-DOAEP, a Length-Preserving Deterministic Scheme 553
Efficiently Searchable Encryption (ESE) 555
Encrypt-and-Hash ESE 557
CCA and Other Extensions 558
Secure Hybrid Encryption from Weakened Key Encapsulation 564
Introduction 564
Our Contributions 565
Discussion and Related Work 567
Hybrid Encryption from Constrained CCA Secure KEMs 567
Key Encapsulation Mechanisms 567
Authenticated Encryption 569
Hybrid Encryption 570
Efficient Key Encapsulation from DDH 572
Building Blocks 572
The Key-Encapsulation Mechanism 573
Comparison with Cramer-Shoup and Kurosawa-Desmedt 574
Efficiency 575
Key Encapsulation from $n$-Linear 576
Linear Assumptions 576
The Key-Encapsulation Mechanism 576
Key Encapsulation from Hash Proof Systems 577
Hash Proof Systems 577
Key Encapsulation from HPS 578
Computational Hash Proof Systems 579
A Computational HPS from $n$-Linear 579
Scalable and Unconditionally Secure Multiparty Computation 583
Introduction 583
Preliminaries 586
Private, $t$ < $n/2$ 588
Random Double Sharings 588
Opening Sharings 589
Multiplication Triples 589
Circuit Evaluation 589
Robust, $t$ < $n/4$ 591
Error Points 591
Coin-Flip 592
Dispute Control 592
Dealing Consistent Sharings 593
Random Double Sharings 594
Opening Sharings 595
Circuit Evaluation 595
Robust, $t$ < $n/3$ 596
Robust, $t$ < $n/2$ 597
On Secure Multi-party Computation in Black-Box Groups 602
Introduction 602
Preliminaries 605
Honest Majority Is Necessary for n-Product in Non-abelian Groups 605
Constructions 607
Our Approach: Black Box Non-abelian Group Protocols 607
Construction of $n$-Product Protocol from a Shared 2-Product Subprotocol 607
Construction of a $t$-Private $n$-Party Shared 2-Product Subprotocol from a $t$-Reliable $n$-Colouring of a Planar Graph 609
Constructions of $t$-Reliable $n$-Colourings of Planar Graphs 612
Generalisations and Other Results 621
Conclusions 622
A Note on Secure Computation of the Moore-Penrose Pseudoinverse and Its Application to Secure Linear Algebra 624
Introduction 625
Our Results 625
Related Work 628
Preliminaries 628
The Model 628
Some Known Techniques 629
Secure Polynomial Evaluation 630
Known Solution 630
Chebyshev Polynomials 631
Perfectly Secure Polynomial Evaluation of a Shared Field Element 632
Perfectly Secure Polynomial Evaluation of a Shared Matrix 633
Solving Linear Systems of Equations 634
Computing the Rank of a Matrix 634
Moore-Penrose Pseudoinverse 636
The Algorithm 637
The Secure Multi-party Protocols 638
Protocol for the Characteristic Polynomial 640
Author Index 642