The Tenth Theory of Cryptography Conference (TCC2013) , March 3-6, 2013, Tokyo, Japan



Program at-a-glance March 3(Sun) Registration & Reception @ Forest Hongo
March 4(Mon) March 5(Tue) March 6(Wed)
Morning I Session 1 Session 5 Session 9
Morning II Session 2 Session 6 Session 10
Morning III Invited Talk 1 Invited Talk 2 Invited Talk 3
Afternoon I Session 3 Session 7 Session 11
Afternoon II Session 4 Session 8 Session 12
Evening Conference Dinner
@ Capo Pellicano
Rump Session
@ Fukutake Hall

TCC2013 has Welcome Reception, Conference Dinner, and Rump Session as social events. (There is no guided tour or sightseeing.) Social events are held in the campus except for the welcome reception held in the main hotel.

All technical sessions are done in the Koshiba Hall (main conference venue). Morning coffee will be served at the venue every day. Lunch is provided at the Chuo-Shokudo (Main Cafeteria) located within 2-min walk from the venue. Food restrictions should be noted at the time of on-line registration.

17:00-20:00 Registration @ Hotel Forest Hongo, Lobby

18:00-21:00 Welcome Reception @ Hotel Forest Hongo, Main Dining

8:20-8:50 Registration& Morning Coffee @ Koshiba Hall

8:50-9:00 Greetings from PC Chair

9:00-10:10 Session 1 (Chair: Tatsuaki Okamoto)

  • Overcoming Weak Expectations
    Yevgeniy Dodis, Yu Yu
  • A Counterexample to the Chain Rule for Conditional HILL Entropy: And What Deniable Encryption Has to Do with It
    Stephan Krenn, Krzysztof Pietrzak, Akshay Wadia
  • Hardness Preserving Reductions via Cuckoo Hashing
    Itay Berman, Iftach Haitner, Ilan Komargodski, Moni Naor

10:10-10:40 Coffee Break

10:40-11:50 Session 2 (Chair: Alon Rosen)

  • Concurrent Zero Knowledge in the Bounded Player Model [slides]
    Vipul Goyal, Abhishek Jain, Rafail Ostrovsky, Silas Richelson, Ivan Visconti
  • Public-Coin Concurrent Zero-Knowledge in the Global Hash Model
    Ran Canetti, Huijia Lin, Omer Paneth
  • Succinct Malleable NIZKs and an Application to Compact Shuffles
    Melissa Chase, Markulf Kohlweiss, Anna Lysyanskaya, Sarah Meiklejohn

11:50-12:50 Invited Talk 1 (Char: Yuval Ishai)

12:50-14:50 Lunch @ Main Cafeteria

14:50-16:00 Session 3 (Chair: Steve Myers)

  • Attribute-Based Functional Encryption on Lattices
    Xavier Boyen
  • When Homomorphism Becomes a Liability
    Zvika Brakerski
  • Garbling XOR Gates "For Free" in the Standard Model
    Benny Applebaum

16:00-16:30 Coffee Break

16:30-17:40 Session 4 (Chair: Krzysztof Pietrzak)

  • Why "Fiat-Shamir for Proofs" Lacks a Proof
    Nir Bitansky, Dana Dachman-Soled, Sanjam Garg, Abhishek Jain, Yael Tauman Kalai, Adriana López-Alt, Daniel Wichs
  • On the (In)security of Fischlin's Paradigm
    Prabhanjan Ananth, Raghav Bhaskar, Vipul Goyal, Vanishree Rao
  • Signatures of Correct Computation
    Charalampos Papamanthou, Elaine Shi, Roberto Tamassia

19:00-21:00 Conference Dinner @ Capo Pellicano (Drinks start from 18:20)

8:30-9:00 Registration& Morning Coffee @ Koshiba Hall

9:00-10:10 Session 5 (Chair: Ivan Damgård)

  • A Full Characterization of Functions that Imply Fair Coin Tossing and Ramifications to Fairness [slides]
    Gilad Asharov, Yehuda Lindell, Tal Rabin
  • Characterizing the Cryptographic Properties of Reactive 2-Party Functionalities
    R. Amzi Jeffs, Mike Rosulek
  • Feasibility and Completeness of Cryptographic Tasks in the Quantum World
    Serge Fehr, Jonathan Katz, Fang Song, Hong-Sheng Zhou, Vassilis Zikas

10:10-10:40 Coffee Break

10:40-11:50 Session 6 (Chair: abhi shelat)

  • Languages with Efficient Zero-Knowledge PCPs are in SZK [slides]
    Mohammad Mahmoody, David Xiao
  • Succinct Non-Interactive Arguments via Linear Interactive Proofs [slides]
    Nir Bitansky, Alessandro Chiesa, Yuval Ishai, Rafail Ostrovsky, Omer Paneth
  • Unprovable Security of Perfect NIZK and Non-interactive Non-malleable Commitments
    Rafael Pass

11:50-12:50 Invited Talk 2 (Char: Tal Rabin)

12:50-14:50 Lunch @ Main Cafeteria

14:50-16:00 Session 7 (Chair: Yuval Ishai)

  • Communication Locality in Secure Multi-Party Computation: How to Run Sublinear Algorithms in a Distributed Setting [slides]
    Elette Boyle, Shafi Goldwasser, Stefano Tessaro
  • Distributed Oblivious RAM for Secure Two-Party Computation [slides]
    Steve Lu, Rafail Ostrovsky
  • Black-Box Proof of Knowledge of Plaintext and Multiparty
    Computation with Low Communication Overhead
    Steven Myers, Mona Sergi, abhi shelat

16:00-16:30 Coffee Break

16:30-17:40 Session 8 (Chair: Masayuki Abe)

  • Testing the Lipschitz Property over Product Distributions with Applications to Data Privacy
    Kashyap Dixit, Madhav Jha, Sofya Raskhodnikova, Abhradeep Thakurta
  • Limits on the Usefulness of Random Oracles [slides]
    Iftach Haitner, Eran Omri, Hila Zarosim
  • Analyzing Graphs with Node Differential Privacy [slides]
    Shiva Prasad Kasiviswanathan, Kobbi Nissim, Sofya Raskhodnikova, Adam Smith

19:00-21:00 Rump Session @ Fukutake Hall (Food and Drinks start from 18:20)

For submission, send email to by 11pm, 3/4(Mon) with title, speaker name and amount of time (<10 min) for your talk. Program will be available on rump session page after 3/5(Tue) 5pm.

8:30-9:00 Registration& Morning Coffee @ Koshiba Hall

9:00-10:10 Session 9 (Chair: Tal Rabin)

  • Universally Composable Synchronous Computation
    Jonathan Katz, Ueli Maurer, Björn Tackmann, Vassilis Zikas
  • Multi-Client Non-Interactive Verifiable Computation
    Seung Geol Choi, Jonathan Katz, Ranjit Kumaresan, Carlos Cid
  • On the Feasibility of Extending Oblivious Transfer [slides]
    Yehuda Lindell, Hila Zarosim

10:10-10:40 Coffee Break

10:40-11:50 Session 10 (Chair: Alon Rosen)

  • Computational Soundness of Coinductive Symbolic Security under Active Attacks
    Mohammad Hajiabadi, Bruce M. Kapron
  • Revisiting Lower and Upper Bounds for Selective Decommitments [slides]
    Rafail Ostrovsky, Vanishree Rao, Alessandra Scafuro, Ivan Visconti
  • On the Circular Security of Bit-Encryption [slides]
    Ron D. Rothblum

11:50-12:50 Invited Talk 3 (Char: Ivan Damgård)

12:50-14:50 Lunch @ Main Cafeteria

14:50-16:00 Session 11 (Chair: abhi shelat)

  • On the Power of Correlated Randomness in Secure Computation
    Yuval Ishai, Eyal Kushilevitz, Sigurd Meldgaard, Claudio Orlandi , Anat Paskin-Cherniavsky
  • Constant-Overhead Secure Computation of Boolean Circuits using Preprocessing [slides]
    Ivan Damgård, Sarah Zakarias
  • Resettable UC-Functionalities with Untrusted Tamper-Proof Hardware-Tokens [slides]
    Nico Döttling, Thilo Mie, Jörn Müller-Quade, Tobias Nilges

16:00-16:30 Coffee Break

16:30-17:40 Session 12 (Chair: Mohammad Mahmoody)

  • A Cookbook for Black-Box Separations and a Recipe for UOWHFs
    Kfir Barhum, Thomas Holenstein
  • Algebraic (Trapdoor) One-Way Functions and their Applications
    Dario Catalano, Dario Fiore, Rosario Gennaro, Konstantinos Vamvourellis
  • Randomness-Dependent Message Security [slides]
    Eleanor Birrell, Kai-Min Chung, Rafael Pass, Sidharth Telang