Theory of Cryptography

1. Front Matter

   PDF

2. An Optimally Fair Coin Toss

   • Tal Moran, Moni Naor, Gil Segev

   Pages 1-18

3. Complete Fairness in Multi-party Computation without an Honest Majority

   • S. Dov Gordon, Jonathan Katz

   Pages 19-35

4. Fairness with an Honest Minority and a Rational Majority

   • Shien Jin Ong, David C. Parkes, Alon Rosen, Salil Vadhan

   Pages 36-53

5. Purely Rational Secret Sharing (Extended Abstract)

   • Silvio Micali, abhi shelat

   Pages 54-71

6. Some Recent Progress in Lattice-Based Cryptography

   • Chris Peikert

   Pages 72-72

7. Non-malleable Obfuscation

   • Ran Canetti, Mayank Varia

   Pages 73-90

8. Simulation-Based Concurrent Non-malleable Commitments and Decommitments

   • Rafail Ostrovsky, Giuseppe Persiano, Ivan Visconti

   Pages 91-108

9. Proofs of Retrievability via Hardness Amplification

   • Yevgeniy Dodis, Salil Vadhan, Daniel Wichs

   Pages 109-127

10. Security Amplification for Interactive Cryptographic Primitives

    • Yevgeniy Dodis, Russell Impagliazzo, Ragesh Jaiswal, Valentine Kabanets

    Pages 128-145

11. Composability and On-Line Deniability of Authentication

    • Yevgeniy Dodis, Jonathan Katz, Adam Smith, Shabsi Walfish

    Pages 146-162

12. Authenticated Adversarial Routing

    • Yair Amir, Paul Bunn, Rafail Ostrovsky

    Pages 163-182

13. Adaptive Zero-Knowledge Proofs and Adaptively Secure Oblivious Transfer

    • Yehuda Lindell, Hila Zarosim

    Pages 183-201

14. On the (Im)Possibility of Key Dependent Encryption

    • Iftach Haitner, Thomas Holenstein

    Pages 202-219

15. On the (Im)Possibility of Arthur-Merlin Witness Hiding Protocols

    • Iftach Haitner, Alon Rosen, Ronen Shaltiel

    Pages 220-237

16. Secure Computability of Functions in the IT Setting with Dishonest Majority and Applications to Long-Term Security

    • Robin Künzler, Jörn Müller-Quade, Dominik Raub

    Pages 238-255

17. Complexity of Multi-party Computation Problems: The Case of 2-Party Symmetric Secure Function Evaluation

    • Hemanta K. Maji, Manoj Prabhakaran, Mike Rosulek

    Pages 256-273

18. Realistic Failures in Secure Multi-party Computation

    • Vassilis Zikas, Sarah Hauser, Ueli Maurer

    Pages 274-293

19. Secure Arithmetic Computation with No Honest Majority

    • Yuval Ishai, Manoj Prabhakaran, Amit Sahai

    Pages 294-314

20. Universally Composable Multiparty Computation with Partially Isolated Parties

    • Ivan Damgård, Jesper Buus Nielsen, Daniel Wichs

    Pages 315-331

TCC 2009, the 6th Theory of Cryptography Conference, was held in San Fr- cisco, CA, USA, March 15–17, 2009. TCC 2009 was sponsored by the Inter- tional Association for Cryptologic Research (IACR) and was organized in - operation with the Applied Crypto Group at Stanford University. The General Chair of the conference was Dan Boneh. The conference received 109 submissions, of which the Program Comm- tee selected 33 for presentation at the conference. These proceedings consist of revised versions of those 33 papers. The revisions were not reviewed, and the authors bear full responsibility for the contents of their papers. The conference program also included two invited talks: “The Di?erential Privacy Frontier,” given by Cynthia Dwork and “Some Recent Progress in Lattice-Based Crypt- raphy,” given by Chris Peikert. I thank the Steering Committee of TCC for entrusting me with the resp- sibility for the TCC 2009 program. I thank the authors of submitted papers for their contributions. The general impression of the Program Committee is that the submissions were of very high quality, and there were many more papers we wanted to accept than we could. The review process was therefore very - warding but the selection was very delicate and challenging. I am grateful for the dedication, thoroughness,and expertise ofthe ProgramCommittee. Obse- ing the way the members of the committee operated makes me as con?dent as possible of the outcome of our selection process.

• Cisco
• Shannon
• adaptive security
• algorithm
• algorithms
• authentication
• black-box reductions
• communication complexity
• complexity
• cryptographic paradigms
• cryptographic primitives
• cryptographic protocols
• cryptography
• encryption
• privacy
• algorithm analysis and problem complexity

• Faculty of Mathematics and Computer Science, The Weizmann Institute of Science, Rehovot, Israel

  Omer Reingold

Policies and ethics