DIMACS Workshop on Cryptography and its Interactions: Learning Theory, Coding Theory, and Data Structures

July 11 - 13, 2016
DIMACS Center, CoRE Building, Rutgers University

Organizers:

David Cash, Rutgers University, david.cash at cs.rutgers.edu

Yuval Ishai, Technion and UCLA, yuvali at cs.technion.ac.il

Amit Sahai, UCLA, sahai at cs.ucla.edu

Workshop Program:

Monday, July 11, 2016

 8:15 -  8:45  Breakfast and registration

 8:45 -  9:00  Welcome and overview

 9:00 -  9:30  Explicit Two-Source Extractors and Resilient Functions
               David Zuckerman, University of Texas at Austin 

 9:30 - 10:00  High Rate Locally-Correctable and Locally-Testable Codes with Sub-polynomial Query Complexity
               Shubhangi Saraf, Rutgers University 

10:00 - 10:30  Decoding Reed-Muller Codes on Product Sets
               Swastik Kopparty, Rutgers University

10:30 - 11:00  Break

11:00 - 11:30  Algorithms, Cryptosystems, and Unicorns
               Boaz Barak, Harvard University

11:30 - 12:00  How (Not) to Instantiate Ring-LWE
               Chris Peikert, University of Michigan

12:00 - 12:30  Random Local Functions as Pseudo-random Generators
               Shachar Lovett, UC San Diego 

12:30 -  1:50  Lunch

 1:50 -  2:00  Director's Welcome: Rebecca Wright, Director of DIMACS

 2:00 -  2:30  Interactive Coding with Optimal Round and Communication Blowup
               Yael Tauman Kalai, Microsoft Research

 2:30 -  2:50  Towards Optimal Deterministic Coding for Interactive Communication
               Noga Ron-Zewi, Institute for Advanced Study and DIMACS 

 2:50 -  3:20  Non-malleable Codes for Bounded Depth, Bounded Fan-In Circuits
               Tal Malkin, Columbia University

 3:20 -  3:50  Break

 3:50 -  4:20  Accessing Data While Preserving Privacy
               Kobbi Nissim, Harvard University and Ben-Gurion University

 4:20 -  4:50  Stealing Machine Learning Models and Using Them to Violate Privacy
               Tom Ristenpart, Cornell Tech

 4:50 -  5:10  Information Theoretically Secure Databases
               Gregory Valiant, Stanford University

 5:10 -  5:30  Applications and Limitations of the SFT Algorithm
               Barak Shani, The University of Auckland


Tuesday, July 12, 2016

 8:15 -  9:00  Breakfast and registration

 9:00 -  9:30  Non-Cryptographic Limitations on Learning
               Amit Daniely, Google 

 9:30 - 10:00  The Complexity of Learning Neural Network Architectures
               Adam Klivans, University of Texas at Austin 

10:00 - 10:30  Easiness: the More Interesting Phenomenon in Machine Learning
               Sanjeev Arora, Princeton University 

10:30 - 11:00  Break

11:00 - 11:30  Bloom Filters and Cryptography
               Moni Naor, Weizmann Institute of Science 

11:30 - 11:50  Searchable Symmetric Encryption: Optimal Locality in Linear Space via Two Dimensional Balanced Allocations
               Ido Shahaf, Hebrew University

11:50 - 12:20  Efficient Verifiable Range and Closest Point Queries in Zero-Knowledge
               Roberto Tamassia, Brown University

12:20 - 12:40  Taking Authenticated Range Queries to Arbitrary Dimensions
               Nikos Triandopoulos, Boston University

12:40 -  2:00  Lunch

 2:00 -  2:30  Constant Round Interactive Proofs for Delegating Computations
               Ron Rothblum, MIT

 2:30 -  3:00  Spooky Encryption and its Applications
               Yevgeniy Dodis, NYU

 3:00 -  3:30  From Obfuscation to the Security of Fiat-Shamir for Proofs
               Guy Rothblum, Samsung Research America

 3:30 -  4:00  Break

 4:00 -  4:20  2-Server PIR with Sub-polynomial Communication
               Sivakanth Gopi, Princeton University
               Video 	

 4:20 -  4:40  IntegriDB: Verifiable SQL for Outsourced Databases
               Charalampos Papamanthou, University of Maryland

 4:40 -  5:00  Arx: A Strongly Encrypted Database System
               Raluca Ada Popa, University of California, Berkeley

 5:00 -  5:20  SQL on Structurally-Encrypted Databases
               Seny Kamara, Brown University 

 5:20 -  5:30  Break

 5:30          Rump session, open problems session, and workshop dinner


Wednesday, July 13, 2016

 8:15 -  9:00  Breakfast and registration

 9:00 -  9:30  Public-Setup Computational Integrity from Quasi-linear PCPs
               Eli Ben Sasson, Technion 

 9:30 -  9:50  Testing Proximity to Codes with Interactive Oracle Proofs, with More Efficiency and in Zero Knowledge
               Alessandro Chiesa, UC Berkeley 
               Video 	

 9:50 - 10:20  Secret Sharing: A Probabilistic Perspective
               Andrej Bogdanov, The Chinese University of Hong Kong
               Video  

10:20 - 10:40  How to Share a Secret, Infinitely
               Ilan Komargodski, Weizmann Institute of Science
               Video 
              
10:40 - 11:10  Break

11:10 - 11:40  Simultaneous Secrecy and Reliability Amplification for a General Channel
               Russell Impagliazzo, University of California, San Diego
               Video  

11:40 - 12:00  Recent Advances in Non-malleable Extractors and Privacy Amplification Protocols
               Gil Cohen, Caltech 
               Video  

12:00 - 12:20  Almost Optimal Non-malleable Extractors and Privacy Amplification Protocols
               Xin Li, Johns Hopkins University
               Video 

12:20 - 12:40  Breaking the Three Round Barrier for Non-malleable Commitments
               Dakshita Khurana, UCLA
               Video 

12:40 -  2:00  Lunch

 2:00 -  2:30  Bootstrapping the Blockchain
               Juan Garay, Yahoo Labs 
               Video 

 2:30 -  2:50  Privacy-Preserving Smart Contracts
               Ranjit Kumaresan, MIT
               Video 

 2:50 -  3:10  Estimation-Theoretic Tools for Security and Privacy
               Flavio P. Calmon, IBM Research
               Video 

 3:10 -  3:40  Break

 3:40 -  4:00  Topology-Hiding Computation Beyond Logarithmic Diameter
               Adi Akavia, Academic College of Tel Aviv-Yafo
               Video 

 4:00 -  4:20  Overlaying Circuit Clauses for Secure Computation
               Vlad Kolesnikov, Bell Labs
               Video 

 4:20 -  4:40  Upending Stock Market Structure Using Secure Computation
               Charanjit Jutla, IBM Research
               Video 
 
 4:40 -  5:00  Oblivious RAM and Coding?
               Elette Boyle, IDC Herzlia

Previous: Participation

Next: Registration

Workshop Index

DIMACS Homepage