Advances in Cryptology - ASIACRYPT 2009: 15th International Conference on the Theory and Application of Cryptology and Information Security, Tokyo, Japan, ... Computer Science / Security and Cryptology)

Front Matter......Page 1
Preface......Page 3
Table of Contents......Page 8
1 Introduction......Page 12
2 AES Description and Notation......Page 13
3 Local Collisions in AES......Page 14
4.1 Related-Key Attack Model......Page 16
4.2 Boomerang Switch......Page 17
5.1 The Trail......Page 18
5.2 The Attack......Page 21
6.1 The Trail......Page 23
6.2 The Attack......Page 27
References......Page 28
1 Introduction......Page 30
2 The Key-Dependent Attack......Page 32
3 The IDEA Block Cipher......Page 36
4 The Key-Dependent Distribution of IDEA......Page 37
5.1 The Attack on 5.5-Round Variant of IDEA......Page 40
5.3 Two Key-Dependent Attacks on 5-Round IDEA Starting from......Page 44
References......Page 45
1 Introduction......Page 48
2.1 Basic Notation......Page 49
2.2 Random Systems......Page 50
2.3 Ideal Blockciphers and Chains......Page 53
3.1 Proof of the Main Result......Page 54
3.2 Examining the Relevant Keys......Page 56
3.3 Distinguishing Independent and Correlated Permutations......Page 58
References......Page 60
A Problems with the Proof in [4]......Page 61
1 Introduction......Page 63
2.1 Notation......Page 65
2.2 Definition of Security......Page 66
3.1 The Coin-Flip Protocol......Page 67
3.2 Security......Page 68
4.1 Interactive Quantum Zero-Knowledge......Page 72
4.2 Generating Commitment Keys for Improved Quantum......Page 76
5 On Effcient Simulation in the CRS Model......Page 77
Acknowledgments......Page 78
References......Page 79
A Watrous’ Quantum Rewinding Lemma......Page 80
1 Introduction......Page 81
2 Preliminaries......Page 86
3.1 Correctness......Page 88
3.2 Regular Embeddings......Page 89
3.3 Trivial Classical Primitives and Trivial Embeddings......Page 90
4.1 Definition and Basic Properties of Leakage......Page 91
4.2 Leakage as Measure of Privacy and Hardness of Implementation......Page 93
5 The Leakage of Universal Cryptographic Primitives......Page 94
6 Conclusion and Open Problems......Page 96
References......Page 97
Introduction......Page 99
1 The Decoding Problem in Cryptology......Page 100
2.1 A Decoding Algorithm Using the Birthday Paradox......Page 101
3.1 A New Variant of Stern’s Algorithm......Page 103
3.2 Estimation of the Cost of the New Variant......Page 104
4.1 General Principle......Page 106
4.2 GBA under Constraints......Page 108
5.2 Attacking the CFS Signature Scheme......Page 110
5.3 Attacking the FSB Hash Function......Page 112
Conclusion......Page 113
References......Page 114
A Comments on the Assumptions......Page 115
B A Sketch of the Proof of Proposition 2......Page 116
1 Introduction......Page 117
2 Description of Lane......Page 118
2.3 The Permutations......Page 119
3.2 Outline of the Rebound Attack on......Page 120
3.4 The Outbound Phase......Page 123
4.1 First Inbound Phase......Page 125
4.4 Merge Lanes......Page 126
4.5 Message Expansion......Page 127
4.8 Complexity......Page 128
5 Semi-Free-Start Collision for Lane-512......Page 129
5.2 Merge Lanes......Page 130
5.5 Merge Inbound Phases......Page 132
5.10 Merge Inbound Phases......Page 133
5.13 Complexity......Page 134
References......Page 135
1 Introduction......Page 137
3 The Rebound Attack......Page 139
3.2 Preliminaries for the Rebound Attack on Whirlpool......Page 140
3.3 Application to Round-Reduced Whirlpool......Page 141
3.4 Previous Results on Round-Reduced Whirlpool......Page 142
4.1 Inbound Phase......Page 143
4.2 Outbound Phase......Page 146
5 A Subspace Distinguisher for 10 Rounds......Page 147
5.2 Solving Problem 1 for a Random Function......Page 148
5.3 Complexity of the Distinguishing Attack......Page 150
References......Page 151
A Attacks on the Hash Function......Page 153
1 Introduction......Page 155
2 Definitions......Page 157
3.1 Collision Attack of Type 3......Page 158
3.2 Attack on the Combiner......Page 159
4.2 State Update Transformation......Page 161
5.2 Reviewing the Path Search of De Canni`ere/Rechberger......Page 163
5.3 The Path Search for MD5......Page 164
6 Practical Realization and Results......Page 165
6.2 A Type 3 Collision Attack Based on Actually Generated Paths......Page 166
6.3 On Memory Requirements......Page 167
7 Conclusions and Open Problems......Page 168
References......Page 169
A Supplementary Material for Obtained Results......Page 171
1 Introduction......Page 173
2.1 What Operations Can We Use AES-NI for?......Page 174
2.2 The “In-Scope” SHA-3 Candidates......Page 175
3 Implementation and Measurements......Page 176
3.1 Replacement Instructions Pattern......Page 177
4 Candidate Descriptions and AES-NI Implementations......Page 179
5 Implementation Results......Page 183
6 Conclusions......Page 184
References......Page 185
Appendix A: Instructions......Page 186
Appendix B: Rationale Behind the Replacements......Page 187
1 Introduction......Page 190
2.1 Complexity Assumptions......Page 193
2.2 Model and Security Notions......Page 194
2.3 Groth-Sahai Proof Systems......Page 197
3.1 A Trapdoor Commitment to Group Elements......Page 198
3.2 A Public Key Certification Scheme......Page 199
4 A GE Scheme with Non-interactive Proofs......Page 202
References......Page 205
A Sketch of the Proof of Theorem 1......Page 207
1 Introduction......Page 208
1.1 Our Results......Page 209
2.1 Predicate Encryption......Page 211
2.2 A Random Trapdoor Permutation Oracle......Page 212
3 An Impossibility Result for Predicate Encryption......Page 213
3.1 The Attack......Page 214
4 Impossibility for Specific Cases......Page 215
5 A Possibility Result for Predicate Encryption......Page 218
References......Page 221
A Proof Details......Page 222
1.1 Background......Page 225
1.2 Our Results......Page 226
1.4 Related Works on Our Approach......Page 227
2 Dual Pairing Vector Spaces......Page 228
3 Assumptions......Page 229
4 Definition of Hierarchical Predicate Encryption (HPE)......Page 231
5.1 Key Idea in Constructing the Proposed HPE......Page 233
5.2 HPE Scheme......Page 234
5.1, where the parameters are the same as above.......Page 235
5.3 Security......Page 236
References......Page 241
1 Introduction......Page 243
2 Preliminaries......Page 247
3 Security against Chosen Distribution Attack......Page 250
4 Constructions......Page 252
5 Non-adaptive Hedge Security......Page 254
6 Anonymity for Chosen Distribution Attacks......Page 256
7 Adaptive Hedge Security......Page 257
Acknowledgements......Page 258
References......Page 259
1 Introduction......Page 261
2 Yao’s Garbled Circuit Construction......Page 264
2.1 Garbled Circuits......Page 265
2.2 Required Implementation Details......Page 266
4 Optimisations with Free XORs, When the KDF Is Correlation Robust......Page 268
5 Optimisations without Free Xors, When the KDF Is Not Correlation Robust......Page 270
5.2 Even 2-to-1 Gates......Page 271
6 Some Experimental Results......Page 272
References......Page 277
Secure Multi-party Computation Minimizing Online Rounds......Page 279
1.1 Motivation......Page 280
1.2 Our Results......Page 281
1.3 Related Work......Page 283
2 Preliminaries......Page 285
3.1 First Protocol (P......Page 287
3.2 Second Protocol (P......Page 289
3.3 Discussion......Page 291
References......Page 292
A Explicit Preprocessing of P......Page 294
1 Introduction......Page 298
1.1 Our Results......Page 299
2 Overview of Our Constructions......Page 302
3 Preliminaries......Page 304
4 Trapdoor Simulatable Public Key Encryption......Page 305
5 Non-Committing Encryption from Weaker Assumptions......Page 306
6 Trapdoor Simulatable PKE from Hardness of Factoring......Page 309
References......Page 312
1 Introduction......Page 314
1.2 Our Result......Page 315
2.2 Commitment Schemes......Page 316
2.3 Non-malleable Commitments......Page 317
3.1 Tag-Based Witness-Indistinguishable Proof......Page 318
3.2 Non-malleable Statistically Hiding Commitment Scheme......Page 320
References......Page 327
A A Content-Based Non-malleable Commitment Scheme......Page 328
1 Introduction......Page 330
1.1 Our Contributions......Page 331
2.1 Homomorphic Linear Authenticators......Page 332
2.2 Homomorphic Identification Protocols......Page 333
2.3 Proofs of Storage......Page 335
3 From Homomorphic Identification Protocols to HLAs......Page 336
4 From HLAs to Efficient Proofs of Storage......Page 337
5 A Concrete Instantiation Based on Factoring......Page 341
References......Page 343
1 Introduction......Page 345
2.2 Proof Systems......Page 347
3.1 Non-adaptive......Page 348
3.2 Adaptive......Page 349
4 Our Fully Simulatable Adaptive OT......Page 350
5.1 How to Prove Many DDH-Tuples......Page 351
6.1 Security against Sender Corruption......Page 352
6.2 Security against Receiver Corruption......Page 354
References......Page 356
1 Introduction......Page 358
2 Known Algorithm for 3-Collisions......Page 360
4 Detailed Complexity Analysis of Algorithms 1 and 2......Page 362
5 A Second Algorithm with More Tradeoff Options......Page 365
6 Parallelizable 3-Collision Search......Page 367
7 Extension to r-Collisions, for r > 3......Page 368
8 Conclusion......Page 369
References......Page 370
A Practical Implementation......Page 371
B Applications......Page 372
1 Introduction......Page 375
2 Preliminaries......Page 380
3.1 Description......Page 382
3.2 Preimage Awareness......Page 384
4 A Length-Preserving Mixing Stage: Random Permutation Oracles......Page 386
4.1 Making Block-Ciphers Non-invertible: The......Page 387
4.2 Extension of Random Permutation Oracles......Page 389
5 Conclusions......Page 390
References......Page 391
1 Introduction......Page 393
2.1 Merkle-Damg˚ard Construction......Page 397
2.4 Indifferentiability......Page 398
3.1 Definition of Variants of Random Oracles......Page 399
3.2 Relationships among......Page 400
4 Relationship between MD and ERO in the Indifferentiability Framework......Page 401
4.1 Proof of Theorem 5......Page 402
4.2 Proof of Theorem 6......Page 405
4.3 MGF1 Transform......Page 407
5.2 Security of RSA-KEM in......Page 408
References......Page 409
1 Introduction......Page 410
2.2 Uniform Closure......Page 412
2.4 Generic Ring Algorithms......Page 413
2.5 Some Lemmas on Straight Line Programs over Z......Page 414
3 Subset Membership Problems in Generic Rings......Page 415
3.2 Bounding the Probability of Simulation Failure......Page 416
3.4 The Factoring Algorithm......Page 418
4 Computing the Jacobi Symbol with Generic Ring Algorithms......Page 420
6 The Generic Subgroup Decision Problem and Factoring......Page 421
6.1 Generic Equivalence to Factoring......Page 422
7 Analyzing Search Problems in the Generic Ring Model......Page 423
References......Page 424
A Proof Sketch for Lemma 3......Page 425
B Proof Sketch for Proposition 1......Page 427
1 Introduction......Page 428
1.1 Programmability in the Random Oracle Model......Page 429
1.2 Our Contributions and Techniques......Page 430
1.3 Discussion......Page 431
3 Zero Knowledge in the Random Oracle Model......Page 433
4 Zero-Knowledge Protocols and Separations......Page 436
5 Sequential Composition Fails without Dependent Auxiliary Input......Page 438
6 Sequential Composition with Dependent Auxiliary Input......Page 439
7 Proofs of Knowledge with Dependent Auxiliary Input......Page 441
8 Circuit Obfuscation in the Random Oracle Model......Page 442
References......Page 444
1 Introduction......Page 446
2 Notations......Page 447
3.1 Syntax and Standard Security Notions......Page 448
4.1 Functionality F......Page 449
4.2 Impossibility in the Plain Model......Page 451
5.1 Blindness Based on Simulatability......Page 453
5.3 Equivalence......Page 456
6.1 Overview......Page 457
6.2 Building Blocks......Page 458
6.3 The Scheme......Page 459
References......Page 460
1 Introduction......Page 462
2.1 The HFE Cryptosystem......Page 463
2.2 The UOV Signature Scheme......Page 464
2.3 The Square-Vinegar Signature Scheme......Page 465
3.1 Alternative Decompositions......Page 466
3.2 Using the Multiplicative Property of the Differential......Page 467
3.3 Extracting the Vinegar Vector Space......Page 469
3.4 Complexity Analysis and Practical Parameters......Page 470
4.2 Looking for Invariant Subspaces......Page 471
References......Page 473
A Simple Auxiliary Functions for Our Magma Scripts......Page 475
B Magma Script to Attack the Signature Scheme......Page 476
C Magma Script to Attack the Encryption Scheme......Page 479
1 Introduction......Page 480
2.1 Quadratic Fields......Page 483
2.2 Representation of the Classes......Page 484
2.3 Reduction of the Forms [......Page 486
3 A Rigorous Homogeneous Variant of Coppersmith’s Root Finding Method......Page 489
4.2 Heuristic Correctness and Analysis of Our Algorithm......Page 491
5 Cryptanalysis of the NICE Cryptosystems......Page 492
5.1 Polynomial-Time Key Recovery in the Real Setting......Page 493
5.2 Polynomial-Time Key Recovery of the Original......Page 494
References......Page 495
1 Introduction......Page 498
2 Basics on Lattices......Page 501
3 Power Generators with e = 2 and Two Iterations......Page 502
4 Generalization to Lattices of Arbitrary Dimension......Page 504
5 Using an Arbitrary Fixed Number of PRG Iterations......Page 505
5.1 Arbitrary Number of PRG Iterations......Page 507
6 Extending to Higher Powers......Page 508
7 Experiments......Page 509
A Describing the Set of Monomials......Page 510
B Relations among Exponent Polynomials......Page 513
1 Introduction......Page 516
2 Juels and Brainard Puzzles......Page 521
3 Client Puzzles......Page 522
4 Security Notions for Client Puzzles......Page 524
5 An Attack on the Juels and Brainard Puzzles......Page 526
6 A Generic Client Puzzle Construction......Page 528
References......Page 532
1 Introduction......Page 535
2 Preliminaries......Page 539
3 Non-malleability of Hash and One-Way Functions......Page 540
4 Constructing Non-malleable Hash Functions......Page 543
5.1 On the Impossibility of Black-Box Reductions......Page 546
6 Applications......Page 548
References......Page 551
1 Introduction......Page 553
2 Brief Description of Threefish-512......Page 555
3.1 Adapting Differences in the Key and the Tweak......Page 556
3.3 Optimizing the Search......Page 557
4.1 Forward Differential......Page 559
4.3 Miss-in-the-Middle......Page 560
5 Improved Key-Recovery Attacks......Page 561
6 Boomerang Attacks......Page 562
6.2 Related-Key Distinguishers......Page 563
6.4 Extension to Key-Recovery......Page 564
7 Conclusion......Page 567
References......Page 568
A Conforming Pair for the 4-Round Differential......Page 569
B Examples of Near Collisions......Page 570
1 Introduction......Page 571
2.1 Computing the Raw Probability......Page 573
3 Finding a Conforming Message Pair Efficiently......Page 575
3.2 Dependency Table for Freedom Degrees Use......Page 576
4.1 CubeHash Description......Page 579
4.3 Collision Construction......Page 580
4.4 Linear Differentials for CubeHash-......Page 581
4.5 Collision Attacks on CubeHash Variants......Page 582
5 Generalization......Page 584
6 Application to MD6......Page 585
References......Page 587
1 Introduction......Page 589
2 SHA-2 Specification......Page 591
3 Overview of the Meet-in-the-Middle Preimage Attack......Page 593
4.3 Partial-Matching......Page 594
4.4 Partial-Fixing......Page 595
4.5 Indirect-Partial-Matching......Page 596
4.6 Initial Structure......Page 597
4.8 Message Compensation......Page 598
5.1 Number of Attacked Steps......Page 600
5.3 Complexity Estimation......Page 602
6.2 Chunk Separation......Page 603
6.4 Attack Overview......Page 604
7.2 SHA-224 and SHA-384......Page 605
References......Page 606
1 Introduction......Page 609
1.1 Contributions and Comparisons......Page 611
1.2 Techniques......Page 613
1.3 Intuition for Aborting......Page 614
2.1 Notation......Page 615
2.2 Lattices and Algebra......Page 616
2.4 Cryptographic Definitions......Page 617
3 Lattice-Based Constructions......Page 619
3.1 Identification Scheme......Page 620
3.2 Signature Scheme......Page 622
3.3 Concrete Parameters......Page 623
4 Factoring-Based Constructions......Page 624
References......Page 625
1 Introduction......Page 628
2 Reminders and Background Results on Lattices......Page 631
3 Hiding a Trapdoor in Ideal-SIS......Page 634
3.1 A Trapdoor for Ideal-SIS......Page 635
3.2 An Analogue to the Second Alwen-Peikert Construction......Page 636
4 From LWE to SIS......Page 637
4.1 From LWE to BDD......Page 638
4.2 A New Interpretation of Regev’s Quantum Reduction......Page 639
5.1 Effcient Public-Key Encryption Scheme......Page 641
5.2 Further Applications......Page 643
References......Page 644
1 Password-Based Authenticated Key Exchange......Page 647
1.1 Our Results......Page 648
2 Approximate Smooth Projective Hash Functions......Page 649
3 A PAKE Protocol from Approximate SPH......Page 650
4 The Learning with Errors Problem......Page 653
4.1 Some Supporting Lemmas......Page 654
5.1 A CPA-Secure Encryption Scheme......Page 655
5.2 An Approximate SPH System......Page 657
6.1 A CCA-Secure Encryption Scheme......Page 660
6.2 An Approximate SPH System......Page 661
References......Page 662
1 Introduction......Page 664
2 Security Model......Page 666
2.1 Why Random Faults?......Page 667
3.1 The PSS Scheme......Page 668
3.2 Security Proof......Page 669
4.1 The PSS-R Scheme......Page 675
5 Conclusion......Page 676
References......Page 677
1 Introduction......Page 678
2.1 Data Caches......Page 679
2.2 Published Attacks......Page 680
3.1 ECC in OpenSSL......Page 681
3.2 Cache Attack Vulnerability......Page 682
4.2 Cache-Timing Data Templates......Page 684
5.1 Elements of an HMM......Page 685
5.3 Use of HMMs in Side-Channel Attacks......Page 687
6 Results......Page 690
8 Conclusion......Page 692
References......Page 694
1 Introduction......Page 696
3 Memory Attacks......Page 699
4 Physically Unclonable Functions......Page 700
5.1 PUF-(w)PRFs......Page 702
5.2 A Luby-Rackoff Cipher Based on PUF-wPRFs......Page 704
6 SRAM PRFs......Page 707
References......Page 710
1 Introduction......Page 714
1.1 Modeling Leakage Resilience......Page 715
1.2 Our Results......Page 717
1.3 Overview of Our Techniques......Page 718
be constructed based on a variety of concrete assumptions (see Section 4.3). The......Page 719
2 Definitions and Preliminaries......Page 720
2.1 A Technical Lemma......Page 721
3 A Leakage-Resilient Signature Scheme......Page 722
4.1 A Construction Based on One-Way Functions......Page 724
4.2 A Construction from Homomorphic Collision-Resistant Hashing......Page 726
4.3 Constructing (Strong) Homomorphic CRHFs......Page 728
References......Page 729
Author Index......Page 732