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


Accepted Papers

On the Circular Security of Bit-Encryption
Ron D. Rothblum

Distributed Oblivious RAM for Secure Two-Party Computation
Steve Lu; Rafail Ostrovsky

Computational Soundness of Coinductive Symbolic Security under Active Attacks
Mohammad Hajiabadi; Bruce M. Kapron

A Full Characterization of Functions that Imply Fair Coin Tossing and Ramifications to Fairness
Gilad Asharov; Yehuda Lindell; Tal Rabin

On the Feasibility of Extending Oblivious Transfer
Yehuda Lindell; Hila Zarosim

Signatures of Correct Computation
Charalampos Papamanthou; Elaine Shi; Roberto Tamassia

A Cookbook for Black-Box Separations and a Recipe for UOWHFs
Kfir Barhum; Thomas Holenstein

When Homomorphism Becomes a Liability
Zvika Brakerski

Characterizing the Cryptographic Properties of Reactive 2-Party Functionalities
R. Amzi Jeffs; Mike Rosulek

Languages with Efficient Zero-Knowledge PCPs are in SZK
Mohammad Mahmoody; David Xiao

Hardness Preserving Reductions via Cuckoo Hashing
Itay Berman; Iftach Haitner; Ilan Komargodski; Moni Naor

Limits on the usefulness of random oracles
Iftach Haitner; Eran Omri; Hila Zarosim

On The (In)security Of Fischlin's Paradigm
Prabhanjan Ananth; Raghav Bhaskar; Vipul Goyal; Vanishree Rao

On the Power of Correlated Randomness in Secure Computation
Yuval Ishai; Eyal Kushilevitz; Sigurd Meldgaard; Claudio Orlandi; Anat Paskin-Cherniavsky

Revisiting Lower and Upper Bounds for Selective Decommitments
Rafail Ostrovsky; Vanishree Rao; Alessandra Scafuro; Ivan Visconti

Constant-Overhead Secure Computation for Boolean Circuits in the Preprocessing Model
Ivan Damgard; Sarah Zakarias

Multi-Client Non-Interactive Verifiable Computation
Seung Geol Choi; Jonathan Katz; Ranjit Kumaresan; Carlos Cid

Succinct Malleable NIZKs and an Application to Compact Shuffles
Melissa Chase; Markulf Kohlweiss; Anna Lysyanskaya; Sarah Meiklejohn

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

Universally Composable Synchronous Computation
Jonathan Katz; Ueli Maurer; Bjoern Tackmann; Vassilis Zikas

Garbling XOR Gates ``For Free'' in the Standard Model
Benny Applebaum

Overcoming Weak Expectations
Yevgeniy Dodis; Yu Yu

Algebraic (Trapdoor) One Way Functions and their Applications
Dario Catalano; Dario Fiore; Rosario Gennaro; Konstantinos Vamvourellis

Succinct Non-Interactive Arguments via Linear Interactive Proofs
Nir Bitansky Alessandro Chiesa; Yuval Ishai; Rafail Ostrovsky; Omer Paneth

Why Fiat-Shamir for Proofs Lacks a Proof
Nir Bitansky; Dana Dachman-Soled; Sanjam Garg; Abhishek Jain; Yael Tauman Kalai; Adriana Lopez-Alt; Daniel Wichs

Implementing resettable UC-functionalities with untrusted tamper-proof hardware-tokens
Nico Döttling; Thilo Mie; Jörn Müller-Quade; Tobias Nilges

Black-Box Proof of Knowledge of Plaintext and Multiparty Computation with Low Communication Overhead
Steven Myers; Mona Sergi; abhi shelat

Testing the Lipschitz Property over Product Distributions with Applications to Data Privacy
Kashyap Dixit; Madhav Jha; Sofya Raskhodnikova; Abhradeep Thakurta

Concurrent Zero Knowledge in the Bounded Player Model
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

Feasibility and Completeness of Cryptographic Tasks in the Quantum World
Serge Fehr; Jonathan Katz; Fang Song; Hong-Sheng Zhou; Vassilis Zikas

Multi-Party Computation for Sublinear Algorithms
Elette Boyle; Shafi Goldwasser; Stefano Tessaro

Barriers to Provably-Secure Perfect NIZK and Non-interactive Non-malleable Commitments
Rafael Pass

Randomness-Dependent Message Security
Eleanor Birrell; Kai-Min Chung; Rafael Pass; Sidharth Telang

Attribute-Based Encryption from Lattices
Xavier Boyen

Analyzing Graphs with Node Differential Privacy
Shiva Kasiviswanathan; Kobbi Nissim; Sofya Raskhodnikova; Adam Smith