Advances in Cryptology - CRYPTO 2009: 29th Annual International Cryptology Conference, Santa Barbara, CA, USA, August 16-20, 2009, Proceedings (Lecture ... Computer Science Security and Cryptology)

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. 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