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)


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


Lower Bounds on Assumptions behind Indistinguishability Obfuscation

Mohammad Mahmoody, Ameer Mohammed, Soheil Nematihaji, Rafael Pass, and abhi shelat


Indistinguishability Obfuscation: from Approximate to Exact

Nir Bitansky and Vinod Vaikuntanathan


Output-Compressing Randomized Encodings and Applications

Huijia Lin, Rafael Pass, Karn Seth, and Sidharth Telang


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)


The Complexity of Computing the Optimal Composition of Differential Privacy

Jack Murtagh and Salil Vadhan


Order-Revealing Encryption and the Hardness of Private Learning

Mark Bun and Mark Zhandry

14:20—15:00 LWR and LPN (Chair: Vinod Vaikuntanathan)


On the Hardness of Learning with Rounding over Small Modulus

Andrej Bogdanov, Siyao Guo, Daniel Masny, Silas Richelson, and Alon Rosen


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)


Algebraic partitioning: Fully compact and (almost) tightly secure Cryptography

Dennis Hofheinz


Standard Security Does Imply Security Against Selective Opening for Markov Distributions

Georg Fuchsbauer, Felix Heuer, Eike Kiltz, and Krzysztof Pietrzak


Non-Malleable Encryption: Simpler, Shorter, Stronger

Sandro Coretti, Yevgeniy Dodis, Bjorn Tackmann, and Daniele Venturi


Verifiable Random Functions from Standard Assumptions

Dennis Hofheinz and Tibor Jager

16:50—17:30 Complexity of Cryptographic Primitives (Chair:Amos Beimel)


Homomorphic evaluation requires depth

Andrej Bogdanov and Chin Ho Lee


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)


On the Correlation Intractability of Obfuscated Pseudorandom Functions

Ran Canetti, Yilei Chen, and Leonid Reyzin


Reconfigurable Cryptography: A flexible approach to long-term security

Julia Hesse, Dennis Hofheinz, and Andy Rupp


Multilinear Maps from Obfuscation

Martin R. Albrecht, Pooya Farshim, Dennis Hofheinz, Enrique Larraia, and Kenneth G. Paterson


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
(Chair Hugo Krawczyk)


Cryptographic Assumptions: A Position Paper (Invited Talk)

 Shafi Goldwasser and Yael Tauman Kalai


 Panel: Shai Halevi, Yael Tauman Kalai, Moni Naor , Rafi Ostrovsky

12:20—13:50 Lunch Break

13:50—15:10 Multiparty Computation (Chair: Yuval Ishai)


Adaptive Security with Quasi-Optimal Rate

Brett Hemenway, Rafail Ostrovsky, Silas Richelson, and Alon Rosen


On the Complexity of Additively Homomorphic UC Commitments

Tore Kasper Frederiksen, Thomas P. Jakobsen, Jesper Buus Nielsen, and Roberto Trifiletti


Simplified Universal Composability Framework

Douglas Wikström


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)


Making the Best of a Leaky Situation: Zero-Knowledge PCPs from Leakage-Resilient Circuits

Yuval Ishai, Mor Weiss, and Guang Yang


Quasi-Linear Size Zero Knowledge from Linear-Algebraic PCPs

Eli Ben-Sasson, Alessandro Chiesa, Ariel Gabizon, and Madars Virza


From Private Simultaneous Messages to Zero-Information Arthur-Merlin Protocols and Back

Benny Applebaum and Pavel Raykov


A Transform for NIZK Almost as Efficient and General as the Fiat-Shamir Transform Without Programmable Random Oracles

Michele Ciampi, Giuseppe Persiano, Luisa Siniscalchi, and Ivan Visconti


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)


Onion ORAM: A Constant Bandwidth Blowup Oblivious RAM

Srinivas Devadas, Marten van Dijk, Christopher W. Fletcher, Ling Ren, Elaine Shi, and Daniel Wichs


Oblivious Parallel RAM and Applications

Elette Boyle, Kai-Min Chung, and Rafael Pass


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)


Déjà Q: Encore! Un Petit IBE

Hoeteck Wee


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)


Optimal Amplification of Noisy Leakages

Stefan Dziembowski, Sebastian Faust, and Maciej Skórski


Rational Sumchecks

Siyao Guo, Pavel Hubacek, Alon Rosen, and Margarita Vald


Interactive Coding for Interactive Proofs

Allison Bishop and Yevgeniy Dodis


Information-theoretic Local Non-malleable Codes and their Applications

Nishanth Chandran, Bhavana Kanukurthi, and Srinivasan Raghuraman


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)


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


Functional Encryption without Obfuscation

Sanjam Garg, Craig Gentry, Shai Halevi, and Mark Zhandry


On Constructing OWPs from Indistinguishability Obfuscation

Gilad Asharov and Gil Segev


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