This book constitutes the refereed proceedings of the 13th International Conference on the Theory and Application of Cryptology and Information Security, ASIACRYPT 2007, held in Kuching, Malaysia, in December 2007. The 33 revised full papers presented together with 2 invited talks were carefully reviewed and selected from 223 submissions. The papers are organized in topical sections on number theory and elliptic curve, protocol, hash function design, group/broadcast cryptography, mac and implementation, multiparty computation, block ciphers, foundation, public key encryption, and cryptanalysis. ASIACRYPT 2007 was held in Kuching, Sarawak, Malaysia, during December 2¿6, 2007. This was the 13th ASIACRYPT conference, and was sponsored by the International Association for Cryptologic Research (IACR), in cooperation with the Information Security Research (iSECURES) Lab of Swinburne University of Technology (Sarawak Campus) and the Sarawak Development Institute (SDI), and was ?nancially supported by the Sarawak Government. The General Chair was Raphael Phan and I had the privilege of serving as the Program Chair. The conference received 223 submissions (from which one submission was withdrawn). Each paper was reviewed by at least three members of the Program Committee, while submissions co-authored by a Program Committee member were reviewed by at least ?ve members. (Each PC member could submit at most one paper.) Many high-quality papers were submitted, but due to the relatively small number which could be accepted, many very good papers had to be rejected. After 11 weeks of reviewing, the Program Committee selected 33 papers for presentation (two papers were merged). The proceedings contain the revised versions of the accepted papers. These revised papers were not subject to editorial review and the authors bear full responsibility for their contents. Number Theory and Elliptic Curve A Kilobit Special Number Field Sieve Factorization 1 Kazumaro Aoki, Jens Franke, Thorsten Kleinjung, Arjen K. Lenstra, and Dag Arne Osvik When e-th Roots Become Easier Than Factoring 13 Antoine Joux, David Naccache, and Emmanuel Thom TD> Faster Addition and Doubling on Elliptic Curves 29 Daniel J. Bernstein and Tanja Lange Protocol A Non-interactive Shuffle with Pairing Based Verifiability 51 Jens Groth and Steve Lu On Privacy Models for RFID 68 Serge Vaudenay Invited Talk I Obtaining Universally Compoable Security: Towards the Bare Bones of Trust 88 Ran Canetti Hash Function Design A Simple Variant of the Merkle-Danigiird Scheme with a Permutation 113 Shoichi Hirose, Je Hong Park, and Aaram Van Seven-Property-Preserving Iterated lashing: ROX 130 Elena Andreeva, Gregory Neven, Bart Preneel, and Thomas Shrimpton How to Build a Hash Function from Any Collision-Resistant Function 147 Thomas Ristenpart and Thomas Shrimpton Group/Broadcast Cryptography Fully Anonymous Group Signatures Without Random Oracles 164 Jens Groth Group Encryption 181 Aggelos Kiayias, Yiannis Tsiounis, and Moti Yung Identity-Based Broadcast Encryption with Constant Size Ciphertexts and Private Keys 200 C le Delerabl /TD> MAC and Implementation Boosting Merkle-Damgard Hashing for Message Authentication 216 Kan Yasuda On Efficient Message Authentication Via Block Cipher Design Techniques 232 G. Jakimoski and K.P. Subbalakshmi Symmetric Key Cryptography on Modern Graphics Hardware 249 Jason Yang and James Goodman Multiparty Computation I Blind Identity-Based Encryption and Simulatable Oblivious Transfer 265 Matthew Green and Susan Hohenberger Multi-party Indirect Indexing and Applications 283 Matthew Franklin. Mark Gondree, and Payman Mohassel Two-Party Computing with Encrypted Data 298 Seung Geol Choi, Ariel Elbaz, Ari fuels, Tal Malkin, and Moti Yang Block Ciphers Known-Key Distinguishers for Some Block Ciphers 315 Lars R. Knudsen and Vincent Rijmen Generic Attacks on Unbalanced Feistel Schemes with Expanding Functions 325 Jacques Patarin, Val e Nachef, and C me Berbain On Tweaking Luby-Rackoff Blockciphers 342 David Goldenberg, Susan Hohenberger, Moses Liskov, Elizabeth Cramp Schwartz, and Hakan Seyalioglu Multiparty Computation II Secure Protocols with Asymmetric Trust 357 Ivan Damg , Yvo Desmedt, Matthias Fitzi, and Jesper Buns Nielsen Simple and Efficient Perfectly-Secure Asynchronous MPC 376 Zuzana Beerliov rubiniov nd Martin Hirt Efficient Byzantine Agreement with Faulty Minority 393 Zuzana Beerliov rubiniov Martin Hirt, and Micha Riser Information-Theoretic Security Without an Honest Majority 410 Anne Broadbent and Alain Tapp Foundation Black-Box Extension Fields and the Inexistence of Field-Homomorphic One-Way Permutations 427 Ueli Maurer and Dominik Raub Concurrent Statistical Zero-Knowledge Arguments for NP from One Way Functions 444 Vipul Goyal, Ryan Moriarty, Rafail Ostrovsky, and Amit Sahai Anonymous Quantum Communication 460 Gilles Brassard, Anne Broadbent, Joseph Fitzsimons, S stien Gambs, and Alain Tapp Invited Talk II Authenticated Key Exchange and Key Encapsulation in the Standard Model 474 Tatsuaki Okamoto Public Key Encryption Miniature CCA2 PK Encryption: Tight Security Without Redundancy 485 Xavier Boyen Bounded CCA2-Secure Encryption 502 Ronald Cramer, Goichiro Hanaoka, Dennis Hofheinz, Hideki Imai, Eike Kiltz, Rafael Pass, Abhi Shelat, and Vinod Vaikuntanathan Relations Among Notions of Non-malleability for Encryption 519 Rafael Pass, Abhi Shelat, and Vinod Vaikuntanathan Cryptanalysis Cryptanalysis of the Tiger Hash Function 536 Florian Mendel and Vincent Rijmen Cryptanalysis of GRINDAHL 551 Thomas Peyrin A Key Recovery Attack on Edon80 568 Martin Hell and Thomas Johansson Author Index 583