Minimal Complexity Assumptions for Cryptography

Program

Meta-Complexity

Date

Monday, May 1 – Friday, May 5, 2023

Back to calendar

All talks are held in Pacific Time. ** Schedule subject to change.**

8:30 – 8:55 a.m.

Coffee and Check-in

8:55 – 9 a.m.

Opening Remarks

9 – 10 a.m.

Tutorial on Proof Systems

Abhishek Jain (Johns Hopkins University)

10 – 10:30 a.m.

Break

10:30 – 11:15 a.m.

Correlation Intractability and SNARGs from Sub-exponential DDH

Zhengzhong Jin (MIT)

11:15 a.m. – 12 p.m.

Constant-Round Arguments from One-Way Functions

Guy Rothblum (Apple)

12 – 1:30 p.m.

Lunch

1:30 – 2:15 p.m.

Rate-1 BARGs via fully-local SSB hash families

Lalita Devadas (MIT)

2:15 – 3 p.m.

Non-interactive Universal Arguments

Dana Shamir (Tel Aviv University)

3 – 3:30 p.m.

Break

3:30 – 4:15 p.m.

Hard Languages in NP ∩ coNP and NIZK Proofs from Unstructured Hardness

Alexis Korb (UCLA),
Amit Sahai (UCLA)

4:15 – 5 p.m.

New Techniques for Zero-Knowledge: Leveraging Inefficient Provers to Reduce Assumptions, Interaction, and Trust *Presented Virtually

Dana Dachman-Soled (University of Maryalnd)

5 – 6 p.m.

Reception

8:30 – 9 a.m.

Coffee and Check-in

9 – 9:30 a.m.

Cryptography and Kolmogorov Complexity: A Quick Tutorial

Yanyi Liu (Cornell University)

9:30 – 10 a.m.

Talk By

Yanyi Liu (Cornell University)

10 – 10:30 a.m.

Break

10:30 – 11:15 a.m.

Incompressiblity and Next-Block Pseudoentropy

Iftach Haitner (Tel Aviv University)

11:15 – 11:45 a.m.

Cryptographic Hardness of Correlated Sampling

Russell Impagliazzo (UC San Diego)

11:45 a.m. – 12:30 p.m.

SNARGs Beyond Non-Signaling

Yael Tauman Kalai (Microsoft Research)

12:30 – 2 p.m.

Lunch

2 – 2:30 p.m.

Derandomization: A Quick Tutorial

Lijie Chen (MIT)

2:30 – 3 p.m.

From Derandomization to Fiat-Shamir

Lijie Chen (MIT)

3 – 3:30 p.m.

Break

3:30 – 4:15 p.m.

Capturing One-Way Functions via NP-Hardness of Meta-Complexity

Shuichi Hirahara (National Institute of Informatics, Tokyo)

4:15 – 5 p.m.

NP-Hardness of Approximating Meta-Complexity: A Cryptographic Approach

Hanlin Ren (University of Oxford)

8:30 – 9 a.m.

Coffee and Check-in

9 – 10 a.m.

Communication Complexity, Streaming and Computational Assumptions

Moni Naor (Weizmann Institute of Science)

10 – 10:30 a.m.

Break

10:30 – 11:15 a.m.

On the Complexity of Two-Party Differential Privacy

Noam Mazor (Tel Aviv University)

11:15 a.m. – 12 p.m.

Fine-Grained Cryptography

Marshall Ball (NYU)

12 – 1:30 p.m.

Lunch

1:30 – 2:30 p.m.

Tutorial on obfuscation

Rachel Lin (University of Washington)

2:30 – 3 p.m.

Break

3 – 3:45 p.m.

Tales of Obfuscation in Bounded Arithmetic, Metacomplexity, and Differential Privacy

Rahul Ilango (MIT)

3:45 – 4:15 p.m.

Mutual Empowerment Between Circuit Obfuscation and Circuit Minimization

Ilya Volkovich (Boston College)

4:15 – 5 p.m.

Assumptions in cryptography and complexity theory

Panel Discussion ()

8:30 – 9 a.m.

Coffee and Check-in

9 – 10 a.m.

Doubly Efficient Private Information Retrieval and Fully Homomorphic RAM Computation from Ring LWE

Daniel Wichs (Northeastern University)

10 – 10:30 a.m.

Break

10:30 – 11 a.m.

Advisor-Verifier-Prover Games and the Hardness of Information Theoretic Cryptography *Presented Virtually

Benny Applebaum (Tel-Aviv University)

11 – 11:45 a.m.

Batch Proofs are Statistically Hiding

Prashant Vadusevan (National University of Singapore)

11:45 a.m. – 12:30 p.m.

Unclonable Polymers and Their Cryptographic Applications

Tal Malkin (Columbia University)

12:30 – 2:15 p.m.

Lunch

2:15 – 3 p.m.

New Ways to Garble Arithmetic Circuits

Rachel Lin (University of Washington)

3 – 3:30 p.m.

Break

3:30 – 4:15 p.m.

Collision-Resistance from Multi-Collision-Resistance

Ron Rothblum (Technion)

4:15 – 5 p.m.

Geometry of Secure Computation

Hemanta Maji (Purdue University)

8:30 – 9 a.m.

Coffee and Check-in

9 – 9:45 a.m.

Black-Hole Radiation Decoding as a Cryptographic Assumption

Zvika Brakerski (Weizmann Institute of Science)

9:45 – 10:30 a.m.

Cryptography with Certified Deletion *Presented Virtually

Dakshita Khurana (University of Illinois Urbana-Champaign)

10:30 – 11 a.m.

Break

11 – 11:30 a.m.

Quantum Minimalism

Mark Zhandry (NTT Research)

11:30 a.m. – 12:15 p.m.

Commitments to Quantum States

Fermi Ma (Princeton University)

12:15 – 2 p.m.

Lunch

2 – 2:45 p.m.

On the Computational Hardness Needed for Quantum Cryptography

Ran Canetti (Boston University)

2:45 – 3:30 p.m.

Quantum pseudorandomness in Algorithmica, and its implications to cryptography and complexity

Luowen Qian (Boston University)

3:30 – 4:15 p.m.

Black-Box Separations in Quantum Cryptography *Presented Virtually

Mohammad Mahmoody (University of Virginia)