This book constitutes the refereed proceedings of the 29th Annual International Cryptology Conference, CRYPTO 2009, held in Santa Barbara, CA, USA in August 2009. The 38 revised full papers presented were carefully reviewed and selected from 213 submissions. Addressing all current foundational, theoretical and research aspects of cryptology, cryptography, and cryptanalysis as well as advanced applications, the papers are organized in topical sections on key leakage, hash-function cryptanalysis, privacy and anonymity, interactive proofs and zero-knowledge, block-cipher cryptanalysis, modes of operation, elliptic curves, cryptographic hardness, merkle puzzles, cryptography in the physical world, attacks on signature schemes, secret sharing and secure computation, cryptography and game-theory, cryptography and lattices, identity-based encryption and cryptographers’ toolbox.
Author(s): Shai Halevi
Edition: 1
Year: 2009
Language: English
Pages: 703
3642033555......Page 1
Lecture Notes in Computer Science 5677......Page 2
Advances in Cryptology –
CRYPTO 2009......Page 3
Preface......Page 5
Table of Contents......Page 9
Introduction......Page 13
RSA Private Keys......Page 16
The Reconstruction Algorithm......Page 18
Algorithm Runtime Analysis......Page 20
Local Branching Behavior......Page 21
Global Branching Behavior at Each Step of the Program......Page 22
Bounding the Total Number of Keys Examined......Page 23
Missing Key Fields......Page 24
Implementation and Performance......Page 25
References......Page 27
Public-Key Cryptosystems Resilient to Key Leakage......Page 30
Introduction......Page 31
Our Contributions......Page 32
Related Work......Page 35
Randomness Extraction......Page 36
Hash Proof Systems......Page 37
Defining Key-Leakage Attacks......Page 39
A Generic Construction from Hash Proof Systems......Page 40
Improved Resilience Based on DDH and bold0mu mumu ddRawdddd-Linear......Page 41
Proposal bold0mu mumu 11Raw1111: A New Hash Proof System......Page 42
Proposal bold0mu mumu 22Raw2222: The BHHO Scheme......Page 43
Comparison......Page 44
Generalized Forms of Key-Leakage Attacks......Page 45
References......Page 46
Introduction......Page 48
Our Results......Page 50
Related Work......Page 53
Preliminaries......Page 55
Definition......Page 56
Construction 1: Generalized Okamoto Scheme......Page 57
Construction 2: Adding Flexibility through Direct-Products......Page 59
Construction 3: Saving Communication Using Compressed Direct-Products......Page 60
Existentially and Entropically Unforgeable Signatures......Page 62
Invisible Key Updates......Page 64
References......Page 65
Introduction......Page 67
MD5 Compression Function......Page 70
A New Family of Differential Paths......Page 71
Variable Birthday Search Space, Time-Memory Trade-Off......Page 73
Rogue CA Certificate Construction......Page 75
Independent Additional Improvement......Page 77
Conclusion......Page 79
Introduction......Page 82
Specification of SHA-0 and SHA-1......Page 84
Meet-in-the-Middle Attack......Page 85
Auxiliary Techniques with the Meet-in-the-Middle Attack......Page 86
Analysis of Linear Message Schedule......Page 87
Kernel and Neutral Words......Page 88
Application to SHA-b......Page 90
Chunk Partition for 52-Step SHA-0......Page 91
Partial-Fixing Technique for 52-Step SHA-0......Page 92
Attack Procedure for 52-Step SHA-0......Page 94
Complexity Estimation for 52-Step SHA-0......Page 95
Padding Issue......Page 96
Initial Structure and Partial-Fixing Technique......Page 97
Summary of Attack......Page 98
Conclusion......Page 99
References......Page 100
Introduction......Page 102
Technical Roadmap......Page 105
Definition of Private Conditional Oblivious Transfer......Page 107
Private COT Protocol for Relations on Representations......Page 109
(Unlinkable) Secret Handshakes: Definition......Page 112
Verifier-Local Revocable Group Signature (VLR-GS)......Page 115
Construction of SH's from VLR-GS and Private COT......Page 116
Introduction......Page 120
Randomizable NIZK Proof Systems......Page 124
Instantiating a Randomizable Proof System......Page 125
Malleable Proofs and Randomizable Commitments......Page 126
Partially Extractable Non-interactive Proofs of Knowledge......Page 127
Delegatable Anonymous Credentials......Page 128
Security Definition of Delegatable Credentials......Page 129
Construction of Delegatable Credentials......Page 131
Building Block Instantiations......Page 134
References......Page 135
Introduction......Page 138
Definitions......Page 141
Dense Sets and mall{IND-CDP}\ $\Rightarrow$ mall{SIM$_{\forall\exists}$-CDP}......Page 144
Definitions......Page 149
References......Page 153
Introduction......Page 155
Probabilistically Checkable Arguments......Page 156
From Interactive Proofs to One-Round Arguments......Page 157
Interactive-PCP......Page 159
Short PCAs for Satisfiability......Page 160
Definition of PCA......Page 161
Private Information Retrieval (PIR)......Page 162
From Interactive Proofs to One-Round Arguments......Page 163
From Interactive-PCPs to PCAs......Page 167
Corollaries......Page 169
References......Page 170
Introduction......Page 172
Preliminaries......Page 176
Impossibility......Page 177
Proof of Theorem ??: Zero-Knowledge Proofs......Page 178
Proof of Theorem ??: Zero-Knowledge Arguments......Page 179
A Bounded Concurrent Public-Coin ZK Protocol......Page 185
Black-Box Bounded Concurrent Zero-Knowledge......Page 186
Introduction......Page 189
The Basic Idea......Page 191
Set-Up and Assumptions......Page 193
Some $ igma$-Protocols......Page 195
Using Black-Box Secret-Sharing in the Framework......Page 199
Quadratic Residuosity......Page 200
Homomorphic Encryption......Page 201
Introduction......Page 204
Related Work......Page 205
Preliminaries......Page 206
Homomorphic Commitments......Page 207
Equations with Matrices and Vectors......Page 208
Reducing $\vz= um_{i=1}^ma_i\vx_iY_i$ to the Form $z= um_{i=1}^ma_i\vx_i\vy_i^{\top}$......Page 209
Reducing Equations with Hadamard Products to a Single Equation with a Bilinear Map......Page 210
The Minimal Case......Page 211
Constant-Round Reduction to the Minimal Case......Page 212
Trading Computation for Interaction......Page 213
Zero-Knowledge Arguments for Linear Algebra Equations......Page 216
Circuit Satisfiability......Page 218
Efficiency......Page 219
New Birthday Attacks on Some MACs Based on Block Ciphers......Page 221
Introduction to Part I......Page 222
Alred Construction......Page 223
Related Works......Page 224
Distinguishing Attack on Alred Construction......Page 225
Forgery Attack on Alred Construction......Page 226
Some Important Properties of Alpha-MAC......Page 227
Distinguishing Attack on Alpha-MAC......Page 229
Internal State Recovery of Alpha-MAC......Page 230
Introduction to Part II......Page 233
Pelican Algorithm......Page 234
PC-MAC-AES......Page 235
Message Pairs Collection Phase......Page 236
Internal State Recovery of Pelican......Page 237
Key Recovery Attack on PC-MAC-AES......Page 240
Conclusion......Page 241
Introduction......Page 243
Multicollision Distinguisher......Page 246
Proof of Lemma 1......Page 247
Proof of Theorem 1......Page 249
Pseudo-collisions for AES-Based Hashing......Page 252
Key Recovery......Page 254
New Design Criteria for Block Ciphers......Page 256
Conclusions......Page 257
Details on Trails......Page 258
Introduction......Page 262
Notation......Page 263
Recovering Secret S-box with Chosen Key Attack......Page 264
Generating Plaintexts That Fit for Seven Rounds......Page 267
Search for S-box Independent Characteristics......Page 268
Recovering Bits of the First Round Key......Page 270
Key and S-box Recovery with Chosen Ciphertext Attack......Page 272
Recovering Remaining Unknown Round Key Bits......Page 273
Attacking the Second Round......Page 275
Conclusions......Page 276
Introduction......Page 279
Inapplicability of Existing Solutions......Page 281
Our Results......Page 283
Security Definitions......Page 285
The SS-NMAC Construction......Page 286
Overview......Page 288
Proof Outline......Page 289
Security of SS-NMAC as a PRF......Page 293
Enhanced PRF Security in the Oracle Cipher Model......Page 294
Unpredictability vs. Pseudorandomness......Page 295
Introduction......Page 298
Variational Distance of the Projected Thorp Shuffle......Page 302
Pseudorandomness of the Thorp Shuffle......Page 306
Efficiently Realizing the Thorp Shuffle......Page 309
References......Page 312
Introduction......Page 315
Related Works......Page 316
An Explicit Encoding from $\FF_{q}$ to $E(\FF_{q})$......Page 318
Properties of Our New Encoding $f_{a,b}$......Page 319
One-Wayness......Page 322
Collision Resistance......Page 323
Making f Collision Free......Page 324
Practical Implementations......Page 325
Conclusion......Page 326
Introduction......Page 329
Polynomial Multiplication......Page 334
Elliptic-Curve Scalar Multiplication......Page 339
Introduction......Page 349
New Tool: Universally Finding Significant Fourier Coefficients......Page 350
Techniques Overview......Page 351
Paper Organization......Page 352
Fourier Transform......Page 353
Solving Hidden Number Problem with Advice......Page 354
Solving with Advice HNP$^{\P,\eps}$: Concentrated $\P$......Page 355
Solving with Advice HNP$^{\P,\eps}$: Segment Predicates $\P$......Page 356
Solving with Advice HNP$^{\P,\eps}$: The Single Most Significant Bit......Page 357
Universally Finding Significant Fourier Coefficients......Page 358
The SFT Algorithm......Page 359
Proof of Theorem 4......Page 361
Bit Security Implications......Page 364
Computational Indistinguishability Amplification: Tight Product Theorems for System Composition......Page 367
Security Amplification......Page 368
The XOR-Lemma and Amplification for PRGs......Page 369
Natural Questions and Previous Results......Page 370
Notational Preliminaries......Page 371
Discrete Systems and Constructions......Page 372
A General Product Theorem for Neutralizing Constructions......Page 374
The Generalized XOR-Lemma......Page 375
A Product Theorem from the XOR-Lemma......Page 377
Applications of Theorem 2......Page 378
A Product Theorem from Self-independence......Page 380
Applications of the Strong Product Theorem......Page 382
Introduction......Page 386
Our Techniques......Page 389
Comparison with ImpagliazzoRu89......Page 390
The Issue of Independence......Page 391
Our Approach......Page 392
Attacking Algorithm......Page 394
Success of Attack: Proof of Lemma 4......Page 396
Efficiency of Attack: Proof of Lemma 5......Page 399
Completing the Proof......Page 401
Position Based Cryptography......Page 403
Motivation......Page 404
The Two Models Considered......Page 406
Our Contributions......Page 407
The Model......Page 409
Lower Bound on Secure Positioning in the Vanilla Model......Page 410
Preliminaries......Page 412
Secure Positioning in 1-Dimension......Page 413
Secure Positioning in 3-Dimensions......Page 414
Information Theoretic Position Based Key-Exchange......Page 416
Introduction......Page 420
Preliminaries......Page 422
Information-Theoretic Security......Page 424
Computational Security in the CRS Model......Page 425
Security Against Benign Bob......Page 426
From Benign to Computational Security......Page 427
Completing the Proof: Bounding Entropy and Memory Size......Page 430
In the Presence of Noise......Page 433
Oblivious Transfer......Page 434
Password-Based Identification......Page 435
Doing without a Common Reference String......Page 438
Introduction......Page 440
Desmedt-Odlyzko's Attack......Page 442
Coron-Naccache-Stern's Attack......Page 444
Bernstein's Smoothness Detection Algorithm......Page 445
Constructing Smaller a (m)-b N Candidates......Page 446
The Amazon Grid......Page 447
The Experiment: Outline, Details and Results......Page 448
Cost Estimates......Page 451
Attacking sda-ipkd......Page 452
Conclusion......Page 454
Introduction......Page 457
The 1993 Instantiation by Bellare and Rogaway......Page 460
The 1996 Instantiation by Bellare and Rogaway......Page 462
Recent Instantiations by Coron et al. (CDMP)......Page 463
Instantiations in PKCS and IEEE Standards......Page 465
Signatures from Trapdoor One-Way Functions......Page 466
Paddings......Page 467
Derandomization......Page 468
Soundness......Page 469
Robustness to Collisions......Page 470
Robustness to Malleability......Page 471
RSA Signatures......Page 472
Rabin and Rabin-Williams......Page 473
Abstraction in Cryptography......Page 477
Asymptotically Good Ideal Linear Secret Sharing with Strong Multiplication over Any Fixed Finite Field......Page 478
Introduction......Page 479
Secret Sharing......Page 481
Algebraic Function Fields and Codes......Page 483
Connecting Secret Sharing and Codes......Page 484
Strongly Multiplicative LSSS from Codes......Page 487
Bounding $\widehat{\tau}(q)$ Away from Zero for Arbitrary $\FF_q$......Page 489
Consequences for LSSS with Strong Multiplication......Page 493
Asymptotically Bad Yet Elementary Schemes......Page 494
Upper Bounds on Optimal Corruption Tolerance......Page 495
Open Problems......Page 496
Introduction......Page 499
Preliminaries......Page 501
Verifiable Secret Sharing (VSS)......Page 502
Statistical-WSS, 2-Round Sharing, n=3t+1......Page 503
Statistical-VSS, 2-Round Sharing, n=3t+1......Page 507
Lower Bound for 2-Round Statistical-VSS, n$\leq$3t......Page 510
Lower Bound for 1-Round Statistical-VSS......Page 512
References......Page 515
Somewhat Non-committing Encryption and Efficient Adaptively Secure Oblivious Transfer......Page 517
Introduction......Page 518
Adaptive Security in Two-Party Protocols......Page 521
Defining $Somewhat$ Non-committing Encryption......Page 523
The $l$-NCE Scheme Construction......Page 525
The Adaptive Security Protocol Compiler for Two-Party SFE......Page 526
The PVW Oblivious Transfer Protocol......Page 528
Semi-adaptively Secure OT......Page 529
Efficient and Adaptively Secure OT......Page 533
Introduction......Page 536
Our Contributions......Page 538
Overview of Our Protocol......Page 539
Definitions......Page 540
Execution in the Real World (with an Honest Mediator)......Page 541
Execution in the Ideal World (with an Honest Mediator)......Page 542
Collusion-Freeness......Page 543
Building Blocks......Page 544
Mediator Broadcast......Page 545
A Protocol $Phi$ for Collusion-Free Secure Computation......Page 548
Proof of Security......Page 550
The Problem: Realizing Privacy-Enhanced Auctions......Page 553
Outline of Our Contribution......Page 555
Protocol Games......Page 558
Communication and Protocol Execution......Page 559
The Mediator and the Internet as Communication Devices......Page 560
Information and Monetary Utilities......Page 561
Privacy-Enhanced Nash Equilibrium......Page 562
Mediation with Reject and Predictable Mechanisms......Page 563
Rational Auctions for Internet-Like Networks......Page 564
Nash Implementation and Hybrid Proofs......Page 567
Introduction......Page 571
Definitions and Preliminaries......Page 575
Definitions......Page 577
U+-Independence vs Fairness and U$^f$-Independence vs Correctness......Page 579
Impossibility for U+-Independence......Page 580
Impossibility for U$^f$-Independence (Non-simultaneous)......Page 583
U$^f$-Dependent Reconstruction in the Non-simultaneous Model......Page 584
Full Independence for n$geq$3 with Relaxed Assumptions......Page 585
Introduction......Page 589
Discussion and Open Problems......Page 592
Preliminaries......Page 594
uSVP and BDD......Page 595
BDD Self-reduction......Page 597
Reducing BDD to uSVP......Page 598
Reducing uSVP to BDD......Page 600
Reducing uSVP to GapSVP......Page 601
Reducing GapSVP to BDD......Page 603
Reductions for Other $l_p$ Norms......Page 604
Fast Cryptographic Primitives and Circular-Secure Encryption Based on Hard Learning Problems......Page 607
Our Results......Page 608
Techniques......Page 611
Preliminaries......Page 612
Noisy Learning Problems......Page 613
Key-Dependent Message Security......Page 614
A Generic Transformation......Page 615
The Cryptosystem......Page 616
Proof of Security......Page 617
Amortized Extension......Page 620
Overview......Page 621
The Construction......Page 622
Weak Randomized PRF......Page 623
The Construction......Page 625
KDM Security......Page 627
Introduction......Page 631
Bilinear Maps......Page 635
Identity-Based Encryption......Page 636
Construction......Page 637
Semi-Functional Algorithms......Page 638
Proof of Security......Page 639
Discussion......Page 643
Hierarchical Identity-Based Encryption......Page 644
Construction......Page 645
Quadratic Residues......Page 649
Signed Quadratic Residues......Page 650
Hybrid ElGamal over the Signed Quadratic Residues......Page 651
Related Work......Page 652
Public-Key Encryption......Page 653
Quadratic Residues......Page 654
Factoring Assumption......Page 655
Strong Diffie-Hellman Assumption......Page 656
The Encryption Scheme......Page 657
The Computational Hardness Assumption......Page 658
Hash Proof Systems......Page 659
IND-CCA Secure Encryption via Randomness Extraction......Page 660
A Hash Proof System for DHIES'......Page 661
Extensions......Page 662
Introduction......Page 666
GMR Unforgeability......Page 669
Chameleon Hashes......Page 670
RSA Assumption and Other Facts......Page 671
A Weakly-Secure Scheme......Page 672
Proof of Security......Page 673
Short, Fully-Secure RSA Signatures......Page 675
Send Resolving Indices with the Signature......Page 676
The Waters Signatures......Page 677
Proof of Security......Page 678
Conclusion and Open Problems......Page 680
Introduction......Page 683
Commitments......Page 686
Smooth Hash Functions on Conjunctions and Disjunctions of Languages......Page 689
A Conditionally Extractable Commitment......Page 692
A Conditionally Extractable Equivocable Commitment......Page 695
References......Page 699
Author Index......Page 702
