Theory of Cryptography: Second Theory of Cryptography Conference, TCC 2005, Cambridge, MA, USA, February 10-12, 2005. Proceedings

Silvio Micali, Chris Peikert, Madhu Sudan, David A. Wilson (auth.), Joe Kilian (eds.)3540245731, 9783540245735, 9783540305767

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.

---

Table of contents :
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 –