This book constitutes the refereed proceedings of the 26th Annual International Conference on the Theory and Applications of Cryptographic Techniques, EUROCRYPT 2007, held in Barcelona, Spain in May 2007.The 33 revised full papers presented were carefully reviewed and selected from 173 submissions. The papers address all current foundational, theoretical and research aspects of cryptology, cryptography, and cryptanalysis as well as advanced applications. This book constitutes the refereed proceedings of the 26th Annual International Conference on the Theory and Applications of Cryptographic Techniques, EUROCRYPT 2007, held in Barcelona, Spain in May 2007. The 33 revised full papers address all current foundational, theoretical and research aspects of cryptology, cryptography, and cryptanalysis as well as advanced applications. Chosen-Prefix Collisions for MD5 and Colliding X.509 Certificates for Different Identities 1 Marc Stevens, Arjen Lenstra, and Benne de Weyer Non-trivial Black-Box Combiners for Collision-Resistant Hash-Functions Don't Exist 23 Krzysztof Pietrzak The Collision Intractability of MDC-2 in the Ideal-Cipher Model 34 John P. Steinberger An Efficient Protocol for Secure Two-Party Computation in the Presence of Malicious Adversaries 52 Yehuda Lindell and Benny Pinkas Revisiting the Efficiency of Malicious Two-Party Computation 79 David P. Woodruff Efficient Two-Party Secure Computation on Committed Inputs 97 Stanislaw Jarecki and Vitaly Shmatikov Universally Composable Multi-party Computation Using Tamper-Proof Hardware 115 Jonathan Katz Generic and Practical Resettable Zero-Knowledge in the Bare Public-Key Model 129 Moti Yung and Yunlei Zhao Instance-Dependent Verifiable Random Functions and Their Application to Simultaneous Resettability 148 Yi Deng and Dongdai Lin Conditional Computational Entropy, or Toward Separating Pseudoentropy from Compressibility 169 Chun- Yuan Hsiao, Chi-Jen Lu, and Leonid Reyzin Zero Knowledge and Soundness Are Symmetric 187 Shien Jin Ong and Salil Vadhan Mesh Signatures 210 Xavier Boyen The Power of Proofs-of-Possession: Securing Multiparty Signatures against Rogue-Key Attacks 228 Thomas Ristenpart and Scott Yilek Batch Verification of Short Signatures 246 Jan Camenisch, Susan Hohenberger, and Michael tergaard Pedersen Cryptanalysis of SFLASH with Slightly Modified Parameters 264 Vivien Dubois, Pierre-Alain Fouque, and Jacques Stern Differential Cryptanalysis of the Stream Ciphers Py, Py6 and Pypy 276 Hongjun Wu and Bart Preneel Secure Computation from Random Error Correcting Codes 291 Hao Chen, Ronald Cramer, Shafi Goldwasser, Robbert de Haan, and Vinod Vaikuntanathan Round-Efficient Secure Computation in Point-to-Point Networks 311 Jonathan Katz and Chiu- Yuen Koo Atomic Secure Multi-party Multiplication with Low Communication 329 Ronald Cramer, Ivan Damg , and Robbert de Haan Cryptanalysis of the Sidelnikov Cryptosystem 347 Lorenz Minder and Amin Shokrollahi Toward a Rigorous Variation of Coppersmith's Algorithm on Three Variables 361 Aur e Bauer and Antoine Joux An L(1/3 + epsilon) Algorithm for the Discrete Logarithm Problem for Low Degree Curves 379 Andreas Enge and Pierrick Gaudry General Ad Hoc Encryption from Exponent Inversion IBE 394 Xavier Boyers Non-interactive Proofs for Integer Multiplication 412 Ivan Damg and Rune Thorbek Ate Pairing on Hyperelliptic Curves 430 Robert Granger, Florian Hess, Roger Oyono, Nicolas Th ault, and Frederik Vercauteren Ideal Multipartite Secret Sharing Schemes 448 Oriol Farr Jaume Marti-Farr and Carles Padr Non-wafer-Scale Sieving Hardware for the NFS: Another Attempt to Cope with 1024-Bit 466 Willi Geiselmann and Rainer Steinwandt Divisible E-Cash Systems Can Be Truly Anonymous 482 S stien Canard and Aline Gouget Fast and Key-Efficient Reduction of Chosen-Ciphertext to Known-Plaintext Security 498 Ueli Maurer and Johan Sj din Range Extension for Weak PRFs; The Good, the Bad, and the Ugly 517 Krzysztof Pietrzak and Johan Sj din Vristel Networks Made Public, and Applications 534 Yevgeniy Dodis and Prashant Puniya Hdivious-Transfer Amplification 555 J rg Wullschleger Stilulatable Adaptive Oblivious Transfer 573 Jan Camenisch, Gregory Neven, and abhi shelat Author Index 591