Learning, cryptography, and the average case
Rocco A. Servedio, Tal Malkin, Andrew Wan · 2010
This thesis explores problems in computational learning theory from an average-case perspective. Through this perspective we obtain a variety of new results for learning theory and cryptography. Several major open questions in computational learning theory revolve around the problem of efficiently learning polynomial-size DNF formulas, which dates back to Valiant's introduction of the PAC learning model [Valiant, 1984]. We apply an average-case analysis to make progress on this problem in two ways. (1) We prove that Mansour's conjecture is true for random DNF. In 1994, Y. Mansour conjectured that for every DNF formula on n variables with t terms there exists a polynomial p with tO(log(1/e)) non-zero coefficients such that Ex∈0,1 n [(p(x) − f( x))2] ≤ e. We make the first progress on this conjecture and show that it is true for several natural subclasses of DNF formulas including randomly chosen DNF formulas and read-k DNF formulas. Our result yields the first polynomial-time query algorithm for agnostically learning these subclasses of DNF formulas with respect to the uniform distribution on {0, 1}n (for any constant error parameter and constant k). Applying recent work on sandwiching polynomials, our results imply that t −O(log 1/e)-biased distributions fool the above subclasses of DNF formulas. This gives pseudorandom generators for these subclasses with shorter seed length than all previous work. (2) We give an efficient algortihm that learns random monotone DNF. The problem of efficiently learning the monotone subclass of polynomial-size DNF formulas from random examples was also posed in [Valiant, 1984]. This notoriously difficult question is still open, despite much study and the fact that known impediments to learning the non-monotone class (cf. [Blum et al., 1994; Blum, 2003a]) do not exist for monotone DNF formulas. We give the first algorithm that learns randomly chosen monotone DNF formulas of arbitrary polynomial size, improving results which efficiently learn n2−e-size random monotone DNF formulas [Jackson and Servedio, 2005b]. Our main structural result is that most monotone DNF formulas reveal their term structure in their constant-degree Fourier coefficients. In this thesis, we also see that connections between learning and cryptography are naturally made through average-case analysis. First, by applying techniques from average-case complexity, we demonstrate new ways of using cryptographic assumptions to prove limitations on learning. As counterpoint, we also exploit the average-case connection in the service of cryptography. Below is a more detailed description of these contributions. (1) We show that monotone polynomial-sized circuits are hard to learn if one-way functions exist. We establish the first cryptographic hardness results for learning polynomial-size classes of monotone circuits, giving a computational analogue of the information-theoretic hardness results of [Blum et al., 1998]. Some of our results show the cryptographic hardness of learning polynomial-size monotone circuits to accuracy only slightly greater than 1/2 + 1/ n ; this is close to the optimal accuracy bound, by positive results of Blum, et al. Our main tool is a complexity-theoretic approach to hardness amplification vianoise sensitivity of monotone functions that was pioneered by O'Donnell [O'Donnell, 2004a]. (2) Learning an overcomplete basis: analysis of lattice-based signatures with perturbations. Lattice-based cryptographic constructions are desirable not only because they provide security based on worst-case hardness assumptions, but also because they can be extremely efficient and practical. We propose a general technique for recovering parts of the secret key in lattice-based signature schemes that follow the Goldreich-Goldwasser-Halevi (GGH) and NTRUSign design with perturbations. Our technique is based on solving a learning problem in the average-case. To solve the average-case problem, we propose a special-purpose optimization algorithm based on higher-order cumulants of the signature distribution, and give theoretical and experimental evidence of its efficacy. Our results suggest (but do not conclusively prove) that NTRUSign is vulnerable to a polynomial-time attack.