Research

Broadly, I study theoretical computer science. I'm interested in cryptography theory, computational learning theory, and (meta-)complexity theory.

Here are some more specific questions that are major themes in my research. These are listed roughly in the chronological order that I have spent time studying them.

Q1. What does it mean to learn undetectably, or "covertly?" How, and under what conditions, could this possible?

--> Background. While few important classes of concepts are known to admit efficient PAC-learning algorithms, expressive classes such as polynomial size decision trees or DNF formulas can be learned efficiently with membership queries. However, the queries and answers used by these algorithms reveal full information about both the concept, and sometimes even prior information about the concept used by the learning algorithm. Thus, how and when can we transform known learning algorithms so that they don't suffer from this type of leakage?

--> A1. In a paper with my advisor and co-auther Ran Canetti, we define a new learning model (called covert learning) encompassing these privacy issues, and show several positive results for learning within. As a main result, we give an efficient membership query learning algorithm for decision trees that hides all information about the learned decision tree (unless given a trapdoor). In essence, the learning algorithm uses pseudo-random queries.

--> Q1.1 Can such a learning algorithm be used for classic cryptographic primitives, such as public key encryption?

--> A1.1 Yes, combined with a weak pseudo-random function.

--> Q1.2 Can learning with pseudo-random queries be used as a model extraction attack?

--> A1.2 Yes. See my recent paper "Thepretical Limits of Provable Security Against Model Extraction by Efficient Observational Defenses".

Q2. Can a gap between efficient PAC-learning and efficient membership query learning be used as a basis for public key encryption?

--> Background. It is clear that if a concept class is not learnable with membership queries, then covert learning is not possible. But, in order to make our privacy guarantees meaningful, learning with random examples should be computationally hard.

--> Q2.1 Can covert learning, and therefore public key encryption, be characterized by the existence of concept classes that admit weak pseudo-random functions, but not strong pseudo-random functions?

--> Q2.1.1 Concrete open question: does the existence of exponentially secure weak pseudo-random functions computable by AC0 with parity gates imply public key encryption?

--> A2.* Unknown.

Q3. Is there a learning vs. crypto dichotomy?

--> Background. It is well known how meaningful cryptography requires the existence of one-way functions. A major open problem is basing the existence of one-way functions off of standard worst-case hardness assumptions, such as NP != P. A relaxed version of this problem is to show that hardness of learning suffices to produce one-way functions. Since one-way functions imply hardness of learning, proving this would give an interesting dichotomy between learning and cryptography.

--> A3. Unknown.

Q4. Is there a heuristic learning vs. crypto dichotomy?

--> Background. Many have complained that Valiant's PAC model is too restrictive (requiring "double worst-case" guarantess). Hence, it can be argued that basing cryptography off hardness of PAC-learning could be very difficult. Recent proposals of learning models defining heuristic learning have been proposed. Thus, can cryptography be based on hardness of heuristic learning?

--> A4. Mikito Nanashima proved that hardness of heuristic learning implies infinitely-often one-way functions. The question of improving this to standard one-way functions, and thus showing a heuristic learning vs cryptogrography dichotomy, is a major focus of my current research.