Theory of Cryptography: Second Theory of Cryptography Conference, TCC 2005, Cambridge, MA, USA, February 10-12. 2005, Proceedings (Lecture Notes in Computer Science (3378))

TCC 2005, the 2nd Annual Theory of Cryptography Conference, was held in Cambridge,Massachusetts,onFebruary10–12,2005.Theconferencereceived84 submissions,ofwhichtheprogramcommitteeselected32forpresentation.These proceedings contain the revised versions of the submissions that were presented at the conference. These revisions have not been checked for correctness, and the authors bear full responsibility for the contents of their papers. The conference program also included a panel discussion on the future of theoretical cryptography and its relationship to the real world (whatever that is). It also included the traditional “rump session,” featuring short, informal talks on late-breaking research news. Much as hatters of old faced mercury-induced neurological damage as an occupational hazard, computer scientists will on rare occasion be a?icted with egocentrism, probably due to prolonged CRT exposure. Thus, you must view withpityandnotcontemptmyunalloyedelationathavingmynameonthefront cover of this LNCS volume, and my deep-seated conviction that I fully deserve the fame and riches that will surely come of it. However, having in recent years switched over to an LCD monitor, I would like to acknowledge some of the many who contributed to this conference. First thanks are due to the many researchers from all over the world who submitted their work to this conference. Lacking shrimp and chocolate-covered strawberries, TCC has to work hard to be a good conference. As a community, I think we have. Front Matter....Pages - Optimal Error Correction Against Computationally Bounded Noise....Pages 1-16 Hardness Amplification of Weakly Verifiable Puzzles....Pages 17-33 On Hardness Amplification of One-Way Functions....Pages 34-49 Cryptography in Subgroups of $\mathbb{Z}_{n}^{*}$ ....Pages 50-65 Efficiently Constructible Huge Graphs That Preserve First Order Properties of Random Graphs....Pages 66-85 Comparing Two Notions of Simulatability....Pages 86-103 Relaxing Environmental Security: Monitored Functionalities and Client-Server Computation....Pages 104-127 Handling Expected Polynomial-Time Strategies in Simulation-Based Security Proofs....Pages 128-149 Adaptively-Secure, Non-interactive Public-Key Encryption....Pages 150-168 Adaptive Security of Symbolic Encryption....Pages 169-187 Chosen-Ciphertext Security of Multiple Encryption....Pages 188-209 Public-Key Steganography with Active Attacks....Pages 210-226 Upper and Lower Bounds on Black-Box Steganography....Pages 227-244 Fair-Zero Knowledge....Pages 245-263 How to Securely Outsource Cryptographic Computations....Pages 264-282 Secure Computation of the Mean and Related Statistics....Pages 283-302 Keyword Search and Oblivious Pseudorandom Functions....Pages 303-324 Evaluating 2-DNF Formulas on Ciphertexts....Pages 325-341 Share Conversion, Pseudorandom Secret-Sharing and Applications to Secure Computation....Pages 342-362 Toward Privacy in Public Databases....Pages 363-385 The Universal Composable Security of Quantum Key Distribution....Pages 386-406 Universally Composable Privacy Amplification Against Quantum Adversaries....Pages 407-425 A Universally Composable Secure Channel Based on the KEM-DEM Framework....Pages 426-444 Sufficient Conditions for Collision-Resistant Hashing....Pages 445-456 The Relationship Between Password-Authenticated Key Exchange and Other Cryptographic Primitives....Pages 457-475 On the Relationships Between Notions of Simulation-Based Security....Pages 476-494 A New Cramer-Shoup Like Methodology for Group Based Provably Secure Encryption Schemes....Pages 495-509 Further Simplifications in Proactive RSA Signatures....Pages 510-528 Proof of Plaintext Knowledge for the Ajtai-Dwork Cryptosystem....Pages 529-555 Entropic Security and the Encryption of High Entropy Messages....Pages 556-577 Error Correction in the Bounded Storage Model....Pages 578-599 Characterizing Ideal Weighted Threshold Secret Sharing....Pages 600-619 Back Matter....Pages - TCC 2005, the 2nd Annual Theory of Cryptography Conference, was held in Cambridge, Massachusetts, onFebruary10-12,2005. Theconferencereceived84 submissions, ofwhichtheprogramcommitteeselected32forpresentation. These proceedings contain the revised versions of the submissions that were presented at the conference. These revisions have not been checked for correctness, and the authors bear full responsibility for the contents of their papers. The conference program also included a panel discussion on the future of theoretical cryptography and its relationship to the real world (whatever that is). It also included the traditional?rump session,? featuring short, informal talks on late-breaking research news. Much as hatters of old faced mercury-induced neurological damage as an occupational hazard, computer scientists will on rare occasion be a?icted with egocentrism, probably due to prolonged CRT exposure. Thus, you must view withpityandnotcontemptmyunalloyedelationathavingmynameonthefront cover of this LNCS volume, and my deep-seated conviction that I fully deserve the fame and riches that will surely come of it. However, having in recent years switched over to an LCD monitor, I would like to acknowledge some of the many who contributed to this conference. First thanks are due to the many researchers from all over the world who submitted their work to this conference. Lacking shrimp and chocolate-covered strawberries, TCC has to work hard to be a good conference. As a community, I think we have

This book constitutes the refereed proceedings of the Second Theory of Cryptography Conference, TCC 2005, held in Cambridge, MA, USA in February 2005.

The 32 revised full papers presented were carefully reviewed and selected from 84 submissions. The papers are organized in topical sections on hardness amplification and error correction, graphs and groups, simulation and secure computation, security of encryption, steganography and zero knowledge, secure computation, quantum cryptography and universal composability, cryptographic primitives and security, encryption and signatures, and information theoretic cryptography.

This book constitutes the refereed proceedings of the Second Theory of Cryptography Conference, TCC 2005, held in Cambridge, MA, USA in February 2005. The 32 revised full papers presented were carefully reviewed and selected from 84 submissions. The papers are organized in topical sections on hardness amplification and error correction, graphs and groups, simulation and secure computation, security of encryption, steganography and zero knowledge, secure computation, quantum cryptography and universal composability, cryptographic primitives and security, encryption and signatures, and information theoretic cryptography The theory of error correction is concerned with sending information reliably over a ''noisy channel" that introduces errors into the transmitted data.