Advances in Cryptology – CRYPTO 2004: 24th Annual International Cryptology Conference, Santa Barbara, California, USA, August 15-19, 2004. Proceedings

Alex Biryukov, Christophe De Cannière, Michaël Quisquater (auth.), Matt Franklin (eds.)9783540226680, 9783540286288, 3540226680

Crypto 2004, the 24th Annual Crypto Conference, was sponsored by the Int- national Association for Cryptologic Research (IACR) in cooperation with the IEEE Computer Society Technical Committee on Security and Privacy and the Computer Science Department of the University of California at Santa Barbara. The program committee accepted 33 papers for presentation at the conf- ence. These were selected from a total of 211 submissions. Each paper received at least three independent reviews. The selection process included a Web-based discussion phase, and a one-day program committee meeting at New York U- versity. These proceedings include updated versions of the 33 accepted papers. The authors had a few weeks to revise them, aided by comments from the reviewers. However, the revisions were not subjected to any editorial review. Theconferenceprogramincludedtwoinvitedlectures.VictorShoup’sinvited talk was a survey on chosen ciphertext security in public-key encryption. Susan Landau’s invited talk was entitled “Security, Liberty, and Electronic Commu- cations”. Her extended abstract is included in these proceedings. We continued the tradition of a Rump Session, chaired by Stuart Haber. Those presentations (always short, often serious) are not included here.

---

Table of contents :
Front Matter….Pages –
On Multiple Linear Approximations….Pages 1-22
Feistel Schemes and Bi-linear Cryptanalysis….Pages 23-40
Short Group Signatures….Pages 41-55
Signature Schemes and Anonymous Credentials from Bilinear Maps….Pages 56-72
Complete Classification of Bilinear Hard-Core Functions….Pages 73-91
Finding Collisions on a Public Road, or Do Secure Hash Functions Need Secret Coins?….Pages 92-105
Security of Random Feistel Schemes with 5 or More Rounds….Pages 106-122
Signed Binary Representations Revisited….Pages 123-139
Compressed Pairings….Pages 140-156
Asymptotically Optimal Communication for Torus-Based Cryptography….Pages 157-178
How to Compress Rabin Ciphertexts and Signatures (and More)….Pages 179-200
On the Bounded Sum-of-Digits Discrete Logarithm Problem in Finite Fields….Pages 201-212
Computing the RSA Secret Key Is Deterministic Polynomial Time Equivalent to Factoring….Pages 213-219
Multi-trapdoor Commitments and Their Applications to Proofs of Knowledge Secure Under Concurrent Man-in-the-Middle Attacks….Pages 220-236
Constant-Round Resettable Zero Knowledge with Concurrent Soundness in the Bare Public-Key Model….Pages 237-253
Zero-Knowledge Proofs and String Commitments Withstanding Quantum Attacks….Pages 254-272
The Knowledge-of-Exponent Assumptions and 3-Round Zero-Knowledge Protocols….Pages 273-289
Near-Collisions of SHA-0….Pages 290-305
Multicollisions in Iterated Hash Functions. Application to Cascaded Constructions….Pages 306-316
Adaptively Secure Feldman VSS and Applications to Universally-Composable Threshold Cryptography….Pages 317-334
Round-Optimal Secure Two-Party Computation….Pages 335-354
Security, Liberty, and Electronic Communications….Pages 355-372
An Improved Correlation Attack Against Irregular Clocked and Filtered Keystream Generators….Pages 373-389
Rewriting Variables: The Complexity of Fast Algebraic Attacks on Stream Ciphers….Pages 390-406
Faster Correlation Attack on Bluetooth Keystream Generator E0….Pages 407-425
A New Paradigm of Hybrid Encryption Scheme….Pages 426-442
Secure Identity Based Encryption Without Random Oracles….Pages 443-459
Non-interactive Timestamping in the Bounded Storage Model….Pages 460-476
IPAKE : Isomorphisms for Password-Based Authenticated Key Exchange….Pages 477-493
Randomness Extraction and Key Derivation Using the CBC, Cascade and HMAC Modes….Pages 494-510
Efficient Tree-Based Revocation in Groups of Low-State Devices….Pages 511-527
Privacy-Preserving Datamining on Vertically Partitioned Databases….Pages 528-544
Optimal Perfectly Secure Message Transmission….Pages 545-561
Pseudo-signatures, Broadcast, and Multi-party Computation from Correlated Randomness….Pages 562-578
Back Matter….Pages –