Cryptographic limitations on learning Boolean formulae and finite automata

TLDR

The paper proves that learning several classes of Boolean functions in the distribution‑free PAC model is intractable. The authors reduce breaking several public‑key cryptosystems to learning these Boolean classes, proving the latter’s hardness. They show that any polynomial‑time learning algorithm for Boolean formulae, deterministic finite automata, or constant‑depth threshold circuits would break RSA, factor Blum integers, detect quadratic residues, and yield strong intractability results for approximating a generalization of graph coloring, even with only a slight advantage over random guessing.

Abstract

In this paper, we prove the intractability of learning several classes of Boolean functions in the distribution-free model (also called the Probably Approximately Correct or PAC model) of learning from examples. These results are representation independent , in that they hold regardless of the syntactic form in which the learner chooses to represent its hypotheses. Our methods reduce the problems of cracking a number of well-known public-key cryptosystems to the learning problems. We prove that a polynomial-time learning algorithm for Boolean formulae, deterministic finite automata or constant-depth threshold circuits would have dramatic consequences for cryptography and number theory. In particular, such an algorithm could be used to break the RSA cryptosystem, factor Blum integers (composite numbers equivalent to 3 modulo 4), and detect quadratic residues. The results hold even if the learning algorithm is only required to obtain a slight advantage in prediction over random guessing. The techniques used demonstrate an interesting duality between learning and cryptography. We also apply our results to obtain strong intractability results for approximating a generalization of graph coloring.