This book constitutes the refereed proceedings of the 27th Annual International Cryptology Conference, CRYPTO 2007, held in Santa Barbara, CA, USA in August 2007. The 33 revised full papers presented together with 1 invited lecture were carefully reviewed and selected from 186 submissions. The papers address all current foundational, theoretical and research aspects of cryptology, cryptography, and cryptanalysis as well as advanced applications. This volume constitutes the refereed proceedings of the 27th Annual International Cryptology Conference held in Santa Barbara, California, in August 2007. Thirty-three full papers are presented along with one important invited lecture. The papers address current foundational, theoretical, and research aspects of cryptology, cryptography, and cryptanalysis. In addition, readers will discover many advanced and emerging applications. Cryptanalysis I Practical Cryptanalysis of SFLASH 1(12) Vivien Dubois Pierre-Alain Fouque Adi Shamir Jacques Stern Full Key-Recovery Attacks on HMAC/NMAC-MD4 and NMAC-MD5 13(18) Pierre-Alain Fouque Gaetan Leurent Phong Q. Nguyen Secure Searching How Should We Solve Search Problems Privately? 31(19) Amos Beimel Tal Malkin Kobbi Nissim Enav Weinreb Public Key Encryption That Allows PIR Queries 50(18) Dan Boneh Eyal Kushilevitz Rafail Ostrovsky William E. Skeith III Invited Talk Information Security Economics -- and Beyond 68(24) Ross Anderson Tyler Moore Theory I Cryptography with Constant Input Locality 92(19) Benny Applebaum Yuval Ishai Eyal Kushilevitz Universally-Composable Two-Party Computation in Two Rounds 111(19) Omer Horvitz Jonathan Katz Indistinguishability Amplification 130(20) Ueli Maurer Krzysztof Pietrzak Renato Renner Lattices A Hybrid Lattice-Reduction and Meet-in-the-Middle Attack Against NTRU 150(20) Nick Howgrave-Graham Improved Analysis of Kannan's Shortest Lattice Vector Algorithm (Extended Abstract) 170(17) Guillaume Hanrot Damien Stehle Random Oracles Domain Extension of Public Random Functions: Beyond the Birthday Barrier 187(18) Ueli Maurer Stefano Tessaro Random Oracles and Auxiliary Input 205(19) Dominique Unruh Hash Functions Security-Amplifying Combiners for Collision-Resistant Hash Functions 224(20) Marc Fischlin Anja Lehmann Hash Functions and the (Amplified) Boomerang Attack 244(20) Antoine Joux Thomas Peyrin Amplifying Collision Resistance: A Complexity-Theoretic Treatment 264(20) Ran Canetti Ron Rivest Madhu Sudan Luca Trevisan Salil Vadhan Hoeteck Wee Theory II How Many Oblivious Transfers Are Needed for Secure Multiparty Computation? 284(19) Danny Harnik Yuval Ishai Eyal Kushilevitz Simulatable VRFs with Applications to Multi-theorem NIZK 303(20) Melissa Chase Anna Lysyanskaya Cryptography in the Multi-string Model 323(19) Jens Groth Rafail Ostrovsky Quantum Cryptography Secure Identification and QKD in the Bounded-Quantum-Storage Model 342(18) Ivan B. Damgard Serge Fehr Louis Salvail Christian Schaffner A Tight High-Order Entropic Quantum Uncertainty Relation with Applications 360(19) Ivan B. Damgard Serge Fehr Renato Renner Louis Salvail Christian Schaffner Cryptanalysis II Finding Small Roots of Bivariate Integer Polynomial Equations: A Direct Approach 379(16) Jean-Sebastien Coron A Polynomial Time Attack on RSA with Private CRT-Exponents Smaller Than N0.073 395(17) Ellen Jochemsz Alexander May Encryption Invertible Universal Hashing and the TET Encryption Mode 412(18) Shai Halevi Reducing Trust in the PKG in Identity Based Cryptosystems 430(18) Vipul Goyal Pirate Evolution: How to Make the Most of Your Traitor Keys 448(18) Aggelos Kiayias Serdar Pehlivanoglu Protocol Analysis A Security Analysis of the NIST SP 800-90 Elliptic Curve Random Number Generator 466(16) Daniel R.L. Brown Kristian Gjøsteen A Generalization of DDH with Applications to Protocol Analysis and Computational Soundness 482(18) Emmanuel Bresson Yassine Lakhnech Laurent Mazare Bogdan Warinschi Chernoff-Type Direct Product Theorems 500(17) Russell Impagliazzo Ragesh Jaiswal Valentine Kabanets Public-Key Encryption Rerandomizable RCCA Encryption 517(18) Manoj Prabhakaran Mike Rosulek Deterministic and Efficiently Searchable Encryption 535(18) Mihir Bellare Alexandra Boldyreva Adam O'Neill Secure Hybrid Encryption from Weakened Key Encapsulation 553(19) Dennis Hofheinz Eike Kiltz Multi-party Computation Scalable and Unconditionally Secure Multiparty Computation 572(19) Ivan Damgard Jesper Buus Nielsen On Secure Multi-party Computation in Black-Box Groups 591(22) Yvo Desmedt Josef Pieprzyk Ron Steinfeld Huaxiong Wang A Note on Secure Computation of the Moore-Penrose Pseudoinverse and Its Application to Secure Linear Algebra 613(18) Ronald Cramer Eike Kiltz Carles Padro Author Index 631