Theory of Cryptography

1. Front Matter

   PDF

2. Overcoming Weak Expectations

   • Yevgeniy Dodis, Yu Yu

   Pages 1-22

3. A Counterexample to the Chain Rule for Conditional HILL Entropy

   • Stephan Krenn, Krzysztof Pietrzak, Akshay Wadia

   Pages 23-39

4. Hardness Preserving Reductions via Cuckoo Hashing

   • Itay Berman, Iftach Haitner, Ilan Komargodski, Moni Naor

   Pages 40-59

5. Concurrent Zero Knowledge in the Bounded Player Model

   • Vipul Goyal, Abhishek Jain, Rafail Ostrovsky, Silas Richelson, Ivan Visconti

   Pages 60-79

6. Public-Coin Concurrent Zero-Knowledge in the Global Hash Model

   • Ran Canetti, Huijia Lin, Omer Paneth

   Pages 80-99

7. Succinct Malleable NIZKs and an Application to Compact Shuffles

   • Melissa Chase, Markulf Kohlweiss, Anna Lysyanskaya, Sarah Meiklejohn

   Pages 100-119

8. Encrypted Messages from the Heights of Cryptomania

   • Craig Gentry

   Pages 120-121

9. Attribute-Based Functional Encryption on Lattices

   • Xavier Boyen

   Pages 122-142

10. When Homomorphism Becomes a Liability

    • Zvika Brakerski

    Pages 143-161

11. Garbling XOR Gates “For Free” in the Standard Model

    • Benny Applebaum

    Pages 162-181

12. Why “Fiat-Shamir for Proofs” Lacks a Proof

    • Nir Bitansky, Dana Dachman-Soled, Sanjam Garg, Abhishek Jain, Yael Tauman Kalai, Adriana López-Alt et al.

    Pages 182-201

13. On the (In)security of Fischlin’s Paradigm

    • Prabhanjan Ananth, Raghav Bhaskar, Vipul Goyal, Vanishree Rao

    Pages 202-221

14. Signatures of Correct Computation

    • Charalampos Papamanthou, Elaine Shi, Roberto Tamassia

    Pages 222-242

15. A Full Characterization of Functions that Imply Fair Coin Tossing and Ramifications to Fairness

    • Gilad Asharov, Yehuda Lindell, Tal Rabin

    Pages 243-262

16. Characterizing the Cryptographic Properties of Reactive 2-Party Functionalities

    • R. Amzi Jeffs, Mike Rosulek

    Pages 263-280

17. Feasibility and Completeness of Cryptographic Tasks in the Quantum World

    • Serge Fehr, Jonathan Katz, Fang Song, Hong-Sheng Zhou, Vassilis Zikas

    Pages 281-296

18. Languages with Efficient Zero-Knowledge PCPs are in SZK

    • Mohammad Mahmoody, David Xiao

    Pages 297-314

19. Succinct Non-interactive Arguments via Linear Interactive Proofs

    • Nir Bitansky, Alessandro Chiesa, Yuval Ishai, Omer Paneth, Rafail Ostrovsky

    Pages 315-333

20. Unprovable Security of Perfect NIZK and Non-interactive Non-malleable Commitments

    • Rafael Pass

    Pages 334-354

This book constitutes the thoroughly refereed proceedings of the 10th Theory of Cryptography Conference, TCC 2013, held in Tokyo, Japan, in March 2013. The 36 revised full papers presented were carefully reviewed and selected from 98 submissions. The papers cover topics such as study of known paradigms, approaches, and techniques, directed towards their better understanding and utilization; discovery of new paradigms, approaches and techniques that overcome limitations of the existing ones; formulation and treatment of new cryptographic problems; study of notions of security and relations among them; modeling and analysis of cryptographic algorithms; and study of the complexity assumptions used in cryptography.

• NIZK
• concurrent zero knowledge
• functional encryption
• multiparty computation
• privacy
• algorithm analysis and problem complexity

• UCLA, Los Angeles, USA

  Amit Sahai

Policies and ethics