CCSI Reading Group: Learning and Crypto

I plan to give a broad overview of cryptographic notions and techniques that have been used to argue computational hardness (and easiness) of learning:

• pseudorandom generators, pseudorandom functions, public key encryption
• relation between distinguishability and predictability
• examples based on Discrete Log, Learning with Errors, Goldreich's construction

Based on interest and time constraints we can also discuss some of the following topics:

• one-way functions and hardness-to-randomness reductions
• barriers: worst-case versus average-case, private-key versus public-key
• hardness of refutation

I plan to give a broad overview of cryptographic notions and techniques that have been used to argue computational hardness (and easiness) of learning:

• pseudorandom generators, pseudorandom functions, public key encryption
• relation between distinguishability and predictability
• examples based on Discrete Log, Learning with Errors, Goldreich's construction

Based on interest and time constraints we can also discuss some of the following topics:

• one-way functions and hardness-to-randomness reductions
• barriers: worst-case versus average-case, private-key versus public-key
• hardness of refutation

In this talk, we will discuss the exact characterization of the threshold density at which a random instance of a constraint satisfaction problem becomes easy to refute as well as evidence of hardness under these thresholds. Based on works by Allen-O'Donnell-Witmer, Raghavendra-Rao-Schramm, and Kothari-Mori-O'Donnell-Witmer.

In this talk, I will introduce the Continuous Learning with Errors (CLWE) problem, which can be seen as a continuous variant of the Learning with Errors (LWE) problem from lattice-based cryptography. Then, I will give a high-level overview of a polynomial-time quantum reduction from worst-case lattice problems to CLWE, which establishes average-case hardness guarantees similar to those of LWE. This result can be leveraged to further establish the (conditional) computational hardness of canonical unsupervised and supervised learning problems, such as density estimation for Gaussian mixtures and learning one-hidden-layer neural networks on the standard Gaussian distribution. This is based on joint work with Joan Bruna, Oded Regev, Yi Tang, and Ilias Zadik.

In this talk, we are going to discuss a new polynomial-time algorithmic framework for inference, based on the celebrated Lenstra-Lenstra-Lovasz lattice basis reduction algorithm. Potentially surprisingly this algorithmic framework is able to successfully bypass multiple notions of "computational hardness for inference" for a number of "exponentially-low-noise" inference settings. Such examples include the algorithm provably succeeding in previously believed "hard" regimes of 1) sparse regression, where there is Overlap Gap Property and Low-Degree failure, 2) phase retrieval, where AMP fails, and 3) cosine neuron learning, where SQ-methods fail. Time permitted, we are going to present the framework, and study the details of some of the mentioned applications. This is based on joint works with David Gamarnik, Eren Kizildag, Min Jae Song, and Joan Bruna.

I will explain how to build a public-key encryption scheme whose security is based on the assumed hardness of solving a random system of sparse linear equations mod 2. This assumption is in contrast with those made in other constructions of public-key cryptography, which are typically based on algebraic or lattice problems. In order to prove security and correctness of this scheme, I will discuss a search-to-distinguishing problem reduction as well as a connection to non-deterministic refutation of random CSPs. To conclude, I will give a survey of evidence supporting the hardness assumption. Based on a paper of Applebaum-Barak-Wigderson.

Given the costs of training ML models, users often elect to delegate learning to service providers whom they do not fully trust. In this talk, we explore possible abuses of power by such untrusted ML trainers. We show how a malicious trainer can plant *undetectable backdoors* in classifiers. The trainer produces a backdoored classifier together with a backdoor key. Given an input and the backdoor key, there is an efficient algorithm for computing a backdoored input---a small perturbation to the original input, for which the model output is arbitrarily inaccurate. Importantly, without the backdoor key, the planted backdoor *cannot be detected*---a property we formalize and prove under standard cryptographic assumptions. Our construction of undetectable backdoors sheds light on the related issue of robustness to adversarial examples. Paradoxically, undetectable backdoors can be planted into classifiers that are certified to be robust against adversarial examples---not only under existing, but also future certifiably-robust classifiers. In the extreme, our results imply the existence of classifiers where every input has an adversarial example, but no efficient algorithm can find any such examples. In all, our findings represent a significant theoretical roadblock to certifying adversarial robustness. Joint work with Shafi Goldwasser, Vinod Vaikuntanathan, and Or Zamir.

TBA