When: Thursday and Friday, July 30-31.
How: A Zoom link was sent to the e-mail list. If you did not receive it, e-mail the organizers to ask for one.
Organizers: Ran Canetti, Yael Kalai, Vinod Vaikuntanathan and Daniel Wichs.
Program (All times are in ET)
Thursday, July 30 | |
---|---|
12:15–12:30p | Virtual Coffee / Hangout |
12:30–1:30p | Venkata Koppula, Weizmann Institute of Science Chosen Ciphertext Security from Injective Trapdoor Functions |
1:45–2:45p | Alex Lombardi, MIT Fiat-Shamir for Repeated Squaring with Applications to PPAD-Hardness and VDFs |
3:00–4:00p | Lisa Yang, MIT PPAD-Hardness and Delegation with Unambiguous Proofs |
Friday, July 31 | |
12:30-1:30p | Mark Bun, Boston University An Equivalence between Private Classification and Online Prediction |
1:45-2:45p | Jonathan Shafer, UC Berkeley Learning vs. Verifying: Interactive Proofs for Verifying Machine Learning |
3:00-4:00p | Mark Zhandry, Princeton Local Quantum Cryptography |
Chosen Ciphertext Security from Injective Trapdoor Functions
Venkata Koppula
Abstract: In this talk, I will present a construction of chosen ciphertext secure public-key encryption from (injective) trapdoor functions. This construction is black box and assumes no special properties (e.g. “lossy”, “correlated product secure”) of the trapdoor function.
Joint work with Susan Hohenberger and Brent Waters [ paper ]
Fiat-Shamir for Repeated Squaring with Applications to PPAD-Hardness and VDFs
Alex Lombardi
Abstract: The Fiat-Shamir transform is a methodology for compiling a (public-coin) interactive proof system for a language L into a non-interactive argument system for L. In this work, we consider the problem of compiling Pietrzak’s succinct interactive proof system (ITCS 2019) for the iterated squaring problem. We construct a hash function family (with evaluation time roughly 2^{\lambda^\epsilon}) that guarantees the soundness of Fiat-Shamir for this protocol assuming the sub-exponential (2^{-n^{1-\epsilon}})-hardness of the n-dimensional learning with errors problem. (The latter follows from the worst-case 2^{n^{1-\epsilon}} hardness of lattice problems.) More generally, we extend the “bad-challenge function” methodology of Canetti et al. for proving the soundness of Fiat-Shamir to a class of protocols whose bad-challenge functions are not efficiently computable.
As a corollary (following Choudhuri et al., ePrint 2019 and Ephraim et al., EUROCRYPT 2020), we construct hard-on-average problems in the complexity class CLS \subset PPAD under the 2^{\lambda^\epsilon}-hardness of the repeated squaring problem and the 2^{-n^{1-\epsilon}}-hardness of the learning with errors problem. Under the additional assumption that the repeated squaring problem is “inherently sequential”, we also obtain a Verifiable Delay Function (Boneh et al., EUROCRYPT 2018) in the standard model. Finally, we give additional PPAD-hardness and VDF instantiations demonstrating a broader tradeoff between the strength of the repeated squaring assumption and the strength of the lattice assumption.
Joint work with Vinod Vaikuntanathan.
Updatable Delegation and PPAD-Hardness
Lisa Yang
Abstract: In this work, we show the hardness of finding a Nash equilibrium, a PPAD-complete problem, based on the quasi-polynomial hardness of the decisional assumption on bilinear groups introduced by Kalai, Paneth and Yang [STOC 2019].Towards this goal, we construct an unambiguous and updatable delegation scheme that is of independent interest.
This delegation scheme is for super-polynomial time deterministic computations and is publicly verifiable and non-interactive in the common reference string (CRS) model. It is unambiguous meaning that it is hard to find two different proofs for the same statement. It is updatable meaning that given a proof for the statement that a Turing machine reaches some configuration C in T steps, one can efficiently update it into a proof for the statement that the machine reaches the next configuration C’ in T+1 steps.
Joint work with Yael Kalai and Omer Paneth.
An Equivalence between Private Classification and Online Prediction
Mark Bun
Abstract: Differential privacy enables rich statistical analyses on data while provably protecting individual-level privacy. The last decade of research has shown that, at least in principle, a number of fundamental statistical tasks are compatible with differential privacy. However, privacy-preserving analyses often require additional complexity over their non-private counterparts, for instance, in terms of the number of data samples one needs to collect in order to get accurate results. In fact, some infinite concept classes that are “easy” to learn in standard computational learning theory become impossible to learn under differential privacy using any finite number of samples.
In this talk, we will describe these impossibility results for private learning and place them in context. We will present a recent characterization of the privately learnable concept classes as exactly those that are learnable in Littlestone’s mistake-bound model of online learning. This equivalence opens new connections between privacy, combinatorics, and stability in learning theory.
Based primarily on work with contributions from Noga Alon, Roi Livni, Maryanthe Malliaris, Shay Moran, Kobbi Nissim, Uri Stemmer, and Salil Vadhan.
Learning vs. Verifying: Interactive Proofs for Verifying Machine Learning
Jonathan Shafer
Abstract: This talk will address the following question: Assume an untrusted party claims to have used machine learning to learn a classifier for a certain task. In what cases is it cheaper to verify that the proposed classifier is good (in the PAC sense), compared to independently learning a new classifier from scratch?
If verification is significantly cheaper than learning, that could have important practical implications for delegation of machine learning tasks in commercial settings, and might also have consequences for verification of scientific publications, and for AI safety. Two results will be discussed: (1) There exists a learning problem where verification requires quadratically less random samples than are required for learning. (2) The broad class of Fourier-sparse functions (which includes decision trees, for example) can be efficiently verified using random samples only, even though it is widely believed to be impossible to efficiently learn this class from random samples alone.
Jonathan is a PhD student at UC Berkeley. This talk covers joint work with Shafi Goldwasser (UC Berkeley), Guy Rothblum (Weizmann Institute of Science), and Amir Yehudayoff (Technion-IIT).
Local Quantum Cryptography
Mark Zhandry
Abstract: “Quantum cryptography” uses a quantum communication channel to achieve new functionalities. For example, the unclonability of quantum messages means an attacker cannot both record quantum communication and also pass it along to the recipient. This leads to a form of eavesdropping detection that is central to quantum key distribution.
In this talk, I will discuss some recent work in an emerging area that I call “local quantum cryptography.” Here, all communication channels remain classical, but the various parties leverage local quantum computing to achieve never-before-possible functionalities. Functionalities we achieve include unclonable cryptographic keys, quantum money with classical communication, rate-limited signatures, and more. The central challenge in this area is to take advantage of features of quantum mechanics such as unclonability, even though all “quantumness” is happening locally on the adversary’s device and therefore is entirely under the adversary’s control.
Based on joint works with Ryan Amos, Marios Georgiou, and Aggelos Kiayias