Theory of Cryptography

1. Front Matter

   PDF

2. Hardness Amplification and Error Correction

   1. Optimal Error Correction Against Computationally Bounded Noise

      • Silvio Micali, Chris Peikert, Madhu Sudan, David A. Wilson

      Pages 1-16

   2. Hardness Amplification of Weakly Verifiable Puzzles

      • Ran Canetti, Shai Halevi, Michael Steiner

      Pages 17-33

   3. On Hardness Amplification of One-Way Functions

      • Henry Lin, Luca Trevisan, Hoeteck Wee

      Pages 34-49

3. Graphs and Groups

   1. Cryptography in Subgroups of \(\mathbb{Z}_{n}^{*}\)

      • Jens Groth

      Pages 50-65

   2. Efficiently Constructible Huge Graphs That Preserve First Order Properties of Random Graphs

      • Moni Naor, Asaf Nussboim, Eran Tromer

      Pages 66-85

4. Simulation and Secure Computation

   1. Comparing Two Notions of Simulatability

      • Dennis Hofheinz, Dominique Unruh

      Pages 86-103

   2. Relaxing Environmental Security: Monitored Functionalities and Client-Server Computation

      • Manoj Prabhakaran, Amit Sahai

      Pages 104-127

   3. Handling Expected Polynomial-Time Strategies in Simulation-Based Security Proofs

      • Jonathan Katz, Yehuda Lindell

      Pages 128-149

5. Security of Encryption

   1. Adaptively-Secure, Non-interactive Public-Key Encryption

      • Ran Canetti, Shai Halevi, Jonathan Katz

      Pages 150-168

   2. Adaptive Security of Symbolic Encryption

      • Daniele Micciancio, Saurabh Panjwani

      Pages 169-187

   3. Chosen-Ciphertext Security of Multiple Encryption

      • Yevgeniy Dodis, Jonathan Katz

      Pages 188-209

6. Steganography and Zero Knowledge

   1. Public-Key Steganography with Active Attacks

      • Michael Backes, Christian Cachin

      Pages 210-226

   2. Upper and Lower Bounds on Black-Box Steganography

      • Nenad Dedić, Gene Itkis, Leonid Reyzin, Scott Russell

      Pages 227-244

   3. Fair-Zero Knowledge

      • Matt Lepinski, Silvio Micali, Abhi Shelat

      Pages 245-263

7. Secure Computation I

   1. How to Securely Outsource Cryptographic Computations

      • Susan Hohenberger, Anna Lysyanskaya

      Pages 264-282

   2. Secure Computation of the Mean and Related Statistics

      • Eike Kiltz, Gregor Leander, John Malone-Lee

      Pages 283-302

   3. Keyword Search and Oblivious Pseudorandom Functions

      • Michael J. Freedman, Yuval Ishai, Benny Pinkas, Omer Reingold

      Pages 303-324

8. Secure Computation II

   1. Evaluating 2-DNF Formulas on Ciphertexts

      • Dan Boneh, Eu-Jin Goh, Kobbi Nissim

      Pages 325-341

   2. Share Conversion, Pseudorandom Secret-Sharing and Applications to Secure Computation

      • Ronald Cramer, Ivan Damgård, Yuval Ishai

      Pages 342-362

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.

• Information
• Secret-Sharing
• Symbol
• Zero Knowledge
• cryptanalysis
• cryptographic primitives
• cryptographic protocols
• cryptography
• cryptology
• digital signatures
• entropy
• privacy
• public key encryption
• quantum computing
• secure computation
• algorithm analysis and problem complexity

• Rutgers University, New Brunswick, USA

  Joe Kilian

Policies and ethics