Cryptographic limitations on learning Boolean formulae and finite automata
- 2 January 1994
- journal article
- Published by Association for Computing Machinery (ACM) in Journal of the ACM
- Vol. 41 (1), 67-95
- https://doi.org/10.1145/174644.174647
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.Keywords
This publication has 16 references indexed in Scilit:
- Learnability and the Vapnik-Chervonenkis dimensionJournal of the ACM, 1989
- Computational limitations on learning from examplesJournal of the ACM, 1988
- Learning regular sets from queries and counterexamplesInformation and Computation, 1987
- Occam's RazorInformation Processing Letters, 1987
- How to construct random functionsJournal of the ACM, 1986
- A theory of the learnableCommunications of the ACM, 1984
- Constant Depth ReducibilitySIAM Journal on Computing, 1984
- Complexity of automaton identification from given dataInformation and Control, 1978
- A method for obtaining digital signatures and public-key cryptosystemsCommunications of the ACM, 1978
- A Measure of Asymptotic Efficiency for Tests of a Hypothesis Based on the sum of ObservationsThe Annals of Mathematical Statistics, 1952