Advances in Cryptology - CRYPTO 2004: 24th Annual International Cryptology Conference, Santa Barbara, California, USA, August 15-19, 2004, Proceedings (Lecture Notes in Computer Science)

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. Linear Cryptanalysis -- On Multiple Linear Approximations -- Feistel Schemes And Bi-linear Cryptanalysis -- Group Signatures -- Short Group Signatures -- Signature Schemes And Anonymous Credentials From Bilinear Maps -- Foundations -- Complete Classification Of Bilinear Hard-core Functions -- Finding Collisions On A Public Road, Or Do Secure Hash Functions Need Secret Coins? -- Security Of Random Feistel Schemes With 5 Or More Rounds -- Efficient Representations -- Signed Binary Representations Revisited -- Compressed Pairings -- Asymptotically Optimal Communication For Torus-based Cryptography -- How To Compress Rabin Ciphertexts And Signatures (and More) -- Public Key Cryptanalysis -- On The Bounded Sum-of-digits Discrete Logarithm Problem In Finite Fields -- Computing The Rsa Secret Key Is Deterministic Polynomial Time Equivalent To Factoring -- Zero-knowledge --^ Multi-trapdoor Commitments And Their Applications To Proofs Of Knowledge Secure Under Concurrent Man-in-the-middle Attacks -- Constant-round Resettable Zero Knowledge With Concurrent Soundness In The Bare Public-key Model -- Zero-knowledge Proofs And String Commitments Withstanding Quantum Attacks -- The Knowledge-of-exponent Assumptions And 3-round Zero-knowledge Protocols -- Hash Collisions -- Near-collisions Of Sha-0 -- Multicollisions In Iterated Hash Functions. Application To Cascaded Constructions -- Secure Computation -- Adaptively Secure Feldman Vss And Applications To Universally-composable Threshold Cryptography -- Round-optimal Secure Two-party Computation -- Invited Talk -- Security, Liberty, And Electronic Communications -- Stream Cipher Cryptanalysis -- An Improved Correlation Attack Against Irregular Clocked And Filtered Keystream Generators -- Rewriting Variables: The Complexity Of Fast Algebraic Attacks On Stream Ciphers --^ Faster Correlation Attack On Bluetooth Keystream Generator E0 -- Public Key Encryption -- A New Paradigm Of Hybrid Encryption Scheme -- Secure Identity Based Encryption Without Random Oracles -- Bounded Storage Model -- Non-interactive Timestamping In The Bounded Storage Model -- Key Management -- Ipake: Isomorphisms For Password-based Authenticated Key Exchange -- Randomness Extraction And Key Derivation Using The Cbc, Cascade And Hmac Modes -- Efficient Tree-based Revocation In Groups Of Low-state Devices -- Computationally Unbounded Adversaries -- Privacy-preserving Datamining On Vertically Partitioned Databases -- Optimal Perfectly Secure Message Transmission -- Pseudo-signatures, Broadcast, And Multi-party Computation From Correlated Randomness. Edited By Matt Franklin. 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 - This book constitutes the refereed proceedings of the 24th Annual International Cryptology Conference, CRYPTO 2004, held in Santa Barbara, California, USA in August 2004. The 33 revised full papers presented together with one invited paper were carefully reviewed and selected from 211 submissions. The papers are organized in topical sections in linear cryptanalysis, group signatures, foundations, efficient representations, public key cryptanalysis, zero-knowledge, hash collision, secure computation, stream cipher cryptanalysis, public key encryption, bounded storage model, key management, and computationally unbounded adversaries