Advances in Cryptology -- CRYPTO 2011: 31st Annual Cryptology Conference, Santa Barbara, CA, USA, August 14-18, 2011, Proceedings (Lecture Notes in Computer Science, 6841)

This book constitutes the refereed proceedings of the 31st Annual International Cryptology Conference, CRYPTO 2011, held in Santa Barbara, CA, USA in August 2011. The 42 revised full papers presented were carefully reviewed and selected from 230 submissions. The volume also contains the abstract of one invited talk. The papers are organized in topical sections on randomness and its use; computer-assisted cryptographic proofs; outsourcing and delegatin computation; symmetric cryptanalysis and constructions; secure computation: leakage and side channels; quantum cryptography; lattices and knapsacks; public-key encryption; symmetric schemes; signatures; obilvious transfer and secret sharing; and multivariate and coding-based schemes. Front Matter....Pages - Leftover Hash Lemma, Revisited....Pages 1-20 Random Oracle Reducibility....Pages 21-38 Time-Lock Puzzles in the Random Oracle Model....Pages 39-50 Physically Uncloneable Functions in the Universal Composition Framework....Pages 51-70 Computer-Aided Security Proofs for the Working Cryptographer....Pages 71-90 Optimal Verification of Operations on Dynamic Sets....Pages 91-110 Verifiable Delegation of Computation over Large Datasets....Pages 111-131 Secure Computation on the Web: Computing without Simultaneous Interaction....Pages 132-150 Memory Delegation....Pages 151-168 Automatic Search of Attacks on Round-Reduced AES and Applications....Pages 169-187 How to Improve Rebound Attacks....Pages 188-205 A Cryptanalysis of PRINTcipher : The Invariant Subspace Attack....Pages 206-221 The PHOTON Family of Lightweight Hash Functions....Pages 222-239 Perfectly-Secure Multiplication for Any t < n /3....Pages 240-258 The IPS Compiler: Optimizations, Variants and Concrete Efficiency....Pages 259-276 1/ p -Secure Multiparty Computation without Honest Majority and the Best of Both Worlds....Pages 277-296 Leakage-Resilient Zero Knowledge....Pages 297-315 A Comprehensive Evaluation of Mutual Information Analysis Using a Fair Evaluation Framework....Pages 316-334 Key-Evolution Schemes Resilient to Space-Bounded Leakage....Pages 335-353 Generic Side-Channel Distinguishers: Improvements and Limitations....Pages 354-372 Cryptography with Tamperable and Leaky Memory....Pages 373-390 Merkle Puzzles in a Quantum World....Pages 391-410 Classical Cryptographic Protocols in a Quantum World....Pages 411-428 Position-Based Quantum Cryptography: Impossibility and Constructions....Pages 429-446 Analyzing Blockwise Lattice Algorithms Using Dynamical Systems....Pages 447-464 Pseudorandom Knapsacks and the Sample Complexity of LWE Search-to-Decision Reductions....Pages 465-484 Tor and Circumvention: Lessons Learned....Pages 485-486 Fully Homomorphic Encryption over the Integers with Shorter Public Keys....Pages 487-504 Fully Homomorphic Encryption from Ring-LWE and Security for Key Dependent Messages....Pages 505-524 Bi-Deniable Public-Key Encryption....Pages 525-542 Better Security for Deterministic Public-Key Encryption: The Auxiliary-Input Setting....Pages 543-560 The Collision Security of Tandem-DM in the Ideal Cipher Model....Pages 561-577 Order-Preserving Encryption Revisited: Improved Security Analysis and Alternative Solutions....Pages 578-595 A New Variant of PMAC: Beyond the Birthday Bound....Pages 596-609 Authenticated and Misuse-Resistant Encryption of Key-Dependent Data....Pages 610-629 Round Optimal Blind Signatures....Pages 630-648 Optimal Structure-Preserving Signatures in Asymmetric Bilinear Groups....Pages 649-666 Constant-Rate Oblivious Transfer from Noisy Channels....Pages 667-684 The Torsion-Limit for Algebraic Function Fields and Its Application to Arithmetic Secret Sharing....Pages 685-705 Public-Key Identification Schemes Based on Multivariate Quadratic Polynomials....Pages 706-723 Inverting HFE Systems Is Quasi-Polynomial for All Fields....Pages 724-742 Smaller Decoding Exponents: Ball-Collision Decoding....Pages 743-760 McEliece and Niederreiter Cryptosystems That Resist Quantum Fourier Sampling Attacks....Pages 761-779 Back Matter....Pages -