Thesis Defense: Katerina Sotiraki: New hardness results for total search problems and non-interactive lattice protocols

Abstract:
We investigate new hardness results for total search problems, namely search problems that always have a solution, and non-interactive lattice protocols.

1. A question of particular importance, raised together with the definition of the class of total search problems, is to identify complete problems that do not have explicitly a Turing machine or a circuit as a part of their input. We provide natural complete problems for various TFNP subclasses. We first consider the classes PPP and PWPP, where our complete problems are inspired by lattice theory and lead towards answering important questions in cryptography. Additionally, we identify complete problems for classes that generalize  the class PPA, called PPA_q. In this case, our results have connections to number theory, and in particular to the Chevalley-Warning theorem.

2. The Learning With Errors (LWE) problem, introduced by Regev has had a profound impact on cryptography. We consider non-interactive protocols that are secure under the LWE assumption, such as non-interactive zero-knowledge and non-interactive key-exchange. We show new strategies and new barriers towards constructing such protocols.

Thesis Committee: Yael Kalai, Ron Rivest & Vinod Vaikuntanathan