TCC 2016-A: Program
Sunday, January 10
18:00—20:00 Welcome Reception ( Will be held at The Porter School of Environmental Studies Building)
Monday, January 11
08:50—09:00 Opening Remarks
09:00—10:40 Obfuscation I (Chair: Christina Brzuska)
09:00—09:20
Impossibility of VBB Obfuscation with Ideal Constant-Degree Graded Encodings
Rafael Pass and abhi shelat 
Joint slot with
On the Impossibility of Virtual Black-Box Obfuscation in Idealized Models
Mohammad Mahmoody, Ameer Mohammed, and Soheil Nematihaji
09:20—09:40
Lower Bounds on Assumptions behind Indistinguishability Obfuscation
Mohammad Mahmoody, Ameer Mohammed, Soheil Nematihaji, Rafael
Pass, and abhi shelat
09:40—10:00
Indistinguishability Obfuscation: from Approximate to Exact
Nir Bitansky and Vinod Vaikuntanathan
10:00—10:20
Output-Compressing Randomized Encodings and Applications
Huijia Lin, Rafael Pass, Karn Seth, and Sidharth Telang
10:20—10:40
Functional Encryption for Turing
Machines
Prabhanjan Ananth and Amit Sahai 10:40—11:10
Coffee Break 11:10—12:10
Invited Talk (Test of Time Award, Chair: Tal Malkin) Differential Privacy: Ten Years of Making Noise Cynthia Dwork, Frank McSherry, Kobbi Nissim, Adam Smith 12:10—13:40
Lunch Break 13:40—14:20
Differential Privacy (Chair: Adam Smith) 13:40—14:00 The Complexity of Computing the
Optimal Composition of Differential Privacy Jack Murtagh and Salil Vadhan 14:00—14:20 Order-Revealing Encryption and the
Hardness of Private Learning Mark Bun and Mark Zhandry 14:20—15:00
LWR and LPN (Chair: Vinod Vaikuntanathan) 14:20—14:40 On the Hardness of Learning with
Rounding over Small Modulus Andrej Bogdanov, Siyao Guo, Daniel Masny, Silas Richelson,
and Alon Rosen 14:40—15:00 Two-Round Man-in-the-Middle
Security from LPN David Cash, Eike Kiltz, and Stefano Tessaro 15:00—15:30
Coffee Break 15:30—16:50
Public Key Encryption, Signatures, and VRF (Chair: Nir Bitansky) 15:30—15:50 Algebraic partitioning: Fully
compact and (almost) tightly secure Cryptography Dennis Hofheinz 15:50—16:10 Standard Security Does Imply
Security Against Selective Opening for Markov Distributions Georg Fuchsbauer, Felix Heuer, Eike Kiltz, and Krzysztof
Pietrzak 16:10—16:30 Non-Malleable Encryption: Simpler,
Shorter, Stronger Sandro Coretti, Yevgeniy Dodis, Bjorn Tackmann, and Daniele
Venturi 16:30—16:50 Verifiable Random Functions from
Standard Assumptions Dennis Hofheinz and Tibor Jager 16:50—17:30
Complexity of Cryptographic Primitives (Chair:Amos Beimel) 16:50—17:10 Homomorphic evaluation requires
depth Andrej Bogdanov and Chin Ho Lee 17:10—17:30 On Basing Private Information
Retrieval on NP-Hardness Tianren Liu and Vinod Vaikuntanathan Tuesday, January 12 09:00—10:20
Obfuscation II (Chair: Zvika Brakerski) 09:00—09:20 On the Correlation Intractability
of Obfuscated Pseudorandom Functions Ran Canetti, Yilei Chen, and Leonid Reyzin 09:20—09:40 Reconfigurable Cryptography: A flexible
approach to long-term security Julia Hesse, Dennis Hofheinz, and Andy Rupp 09:40—10:00 Multilinear Maps from Obfuscation Martin R. Albrecht, Pooya Farshim, Dennis Hofheinz, Enrique Larraia,
and Kenneth G. Paterson 10:00—10:20 Perfect Structure on the Edge of
Chaos Nir Bitansky, Omer Paneth, and Daniel Wichs 10:20—10:50
Coffee Break 10:50—12:20
Cryptographic Assumptions: Invited Talk and Panel 10:50—11:10 Cryptographic Assumptions: A
Position Paper (Invited Talk) Shafi Goldwasser and Yael Tauman Kalai 11:10—12:20 Panel: Shai Halevi, Yael Tauman Kalai, Moni Naor 12:20—13:50
Lunch Break 13:50—15:10
Multiparty Computation (Chair: Yuval Ishai) 13:50—14:10 Adaptive Security with
Quasi-Optimal Rate Brett Hemenway, Rafail Ostrovsky, Silas Richelson, and Alon
Rosen 14:10—14:30 On the Complexity of Additively
Homomorphic UC Commitments Tore Kasper Frederiksen, Thomas P. Jakobsen, Jesper Buus
Nielsen, and Roberto Trifiletti 14:30—14:50 Simplified Universal Composability
Framework Douglas Wikström 14:50—15:10 Characterization of Secure
Multiparty Computation Without Broadcast Ran Cohen, Iftach Haitner, Eran Omri, and Lior Rotem 15:10—15:40
Coffee Break 15:40—17:20
Zero Knowledge and PCP (Chair: Masa Abe) 15:40—16:00 Making the Best of a Leaky
Situation: Zero-Knowledge PCPs from Leakage-Resilient Circuits Yuval Ishai, Mor Weiss, and Guang Yang 16:00—16:20 Quasi-Linear Size Zero Knowledge
from Linear-Algebraic PCPs Eli Ben-Sasson, Alessandro Chiesa, Ariel Gabizon, and Madars
Virza 16:20—16:40 From Private Simultaneous Messages
to Zero-Information Arthur-Merlin Protocols and Back Benny Applebaum and Pavel Raykov 16:40—17:00 Michele Ciampi, Giuseppe Persiano, Luisa Siniscalchi, and
Ivan Visconti 17:00—17:20 Improved OR Composition of
Sigma-Protocols Michele Ciampi, Giuseppe Persiano, Alessandra Scafuro, Luisa
Siniscalchi, and Ivan Visconti 18:30—21:00
Business Meeting & Rump Session (Chair: Abhi Shelat) Wednesday, January 13 09:00—10:00
Oblivious RAM (Chair: Melissa Chase) 09:00—09:20 Onion ORAM: A Constant Bandwidth
Blowup Oblivious RAM Srinivas Devadas, Marten van Dijk, Christopher W. Fletcher,
Ling Ren, Elaine Shi, and Daniel Wichs 09:20—09:40 Oblivious Parallel RAM and
Applications Elette Boyle, Kai-Min Chung, and Rafael Pass 09:40—10:00 Oblivious Parallel RAM: Improved Efficiency
and Generic Constructions Binyi Chen, Huijia Lin, and Stefano Tessaro 10:00—10:40
ABE and IBE (Chair: Gil Segev) 10:00—10:20 Hoeteck Wee 10:20—10:40 A Study of Pair Encodings:
Predicate Encryption in Prime Order Groups Shashank Agrawal and Melissa Chase 10:40—11:10
Coffee Break 11:10—12:10
Invited Talk (Chair: Eyal Kushilevitz) Non-Malleable Codes Yevgeniy Dodis 12:10—13:40
Lunch Break 13:40—15:20
Codes and Interactive Proofs (Chair: Guy Rothblum) 13:40—14:00 Optimal Amplification of Noisy
Leakages Stefan Dziembowski, Sebastian Faust, and Maciej Skórski 14:00—14:20 Siyao Guo, Pavel Hubacek, Alon Rosen, and Margarita Vald 14:20—14:40 Interactive Coding for Interactive
Proofs Allison Bishop and Yevgeniy Dodis 14:40—15:00 Information-theoretic Local
Non-malleable Codes and their Applications Nishanth Chandran, Bhavana Kanukurthi, and Srinivasan Raghuraman 15:00—15:20 Optimal Computational Split-state
Non-malleable Codes Divesh Aggarwal, Shashank Agrawal, Divya Gupta, Hemanta K. Maji,
Omkant Pandey, and Manoj Prabhakaran 15:20—15:50
Coffee Break 15:50—17:10
Obfuscation III (Chair: Nishanth Chandran) 15:50—16:10 How to Avoid Obfuscation Using
Witness PRFs Mark Zhandry Joint slot
with Cutting-Edge Cryptography Through
the Lens of Secret Sharing Ilan Komargodski and Mark Zhandry 16:10—16:30 Functional Encryption without
Obfuscation Sanjam Garg, Craig Gentry, Shai Halevi, and Mark Zhandry 16:30—16:50 On Constructing OWPs from
Indistinguishability Obfuscation Gilad Asharov and Gil Segev 16:50—17:10 Contention in Cryptoland: Obfuscation,
Leakage and UCE Mihir Bellare, Igors Stepanovs, and Stefano Tessaro Joint slot
with Point-Function Obfuscation: A
Framework and Generic Constructions Mihir Bellare and Igors Stepanovs 17:10
Farewell
(Chair Hugo Krawczyk), Rafi Ostrovsky