Michael Kearns
Leslie Valiant
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.
- ~ADLEMAN, L., MANDERS, K., AND MILLER: G. 1977. On taking roots m finite fields. In Proceed- ~ings of the 18th IEEE Symposzum on Foundations of Computer Science. IEEE, New York, pp. ~175-178.Google Scholar
- ~AHO, A., HOPCROFr, J., AND ULLMAN, J. 1974. The Deszgn and Analyszs of Computer Algorithms. ~Addison-Wesley, Reading, Mass. Google Scholar
- ~ALEXI, W., CHOR, B., GOLDREICH, O., AND SCHNORR, C. P. 1988. RSA and Rabm functions: ~Certain parts are as hard as the whole. SL4MJ. Comput. 17, 2, 194-209. Google Scholar
- ~ANGLUIN, D. 1982. Lecture notes on the complexity of some problems in number theory. Tech ~Rep. TR-243. Comput. Sci. Dept., Yale Univ., New Haven, Conn.Google Scholar
- ~ANGLUIN, D. 1987. Learning regular sets from queries and counterexamples. Inf. Cornpztt. 75, ~87-106. Google Scholar
- ~ANGIUIN, D., AND KHARITONOV, M. 1991. When won't membership queries help'~ In Proceedings ~of the 23rd ACM Symposium on the Theory of Computing {.New Orleans, La, May 6-8) ACM, ~New York, pp. 444-454. Google Scholar
- ~ANGLUIN, D., AND LAIRD, P. 1988. Learning from noisy exarnples. Mach. Learn. 2, 319-342. Google Scholar
- ~ANGLUIN, D., AND VALIANT, m. C. 1979. Fast probabilistic algorithms for Hamdtoman circuits ~and matchings. J. Comput. Syst. Scl. 18, I55 193.Google Scholar
- ~BEAME, P. W,, COOK, S. A., AND HOOVER, H. J. 1986. Log depth circuits for division and relatcd ~problems. SIAMJ. Comput. 15, 4 (1986), 994-1003. Google Scholar
- ~BLUM, A. 1989. An ()(n~4)-approximation algorithm for 3-coloring. In Proceedzn~s of the 21st ~ACM Symposium on the Theory of Computing (Seattle, Wash., May 15-17). ACM, New York, ~pp. 535-542. Google Scholar
- ~BLUM, A., AND RIVEST, R. L. 1988. Training a 3-node neural network is NP-complete. In ~Proceedings of the 1988 ~Vorkshop on Computational Learning Theory. Morgan-Kaufmann, San ~Mateo, Calif., pp. 9-18. Google Scholar
- ~BLUM, M., AND MICALI, S. 1984. How to generate cryptographically strong sequences of ~pseudo-random bits. SIAM J. Comput. 13, 4, 850-864. Google Scholar
- ~BLUMER, A., EHRENFEUCHT, A., HAUSSLER, D., AND WARMUTH, M. 1987. Occam's razor, h~f. ~Proc. Lett. 24, 377-380. Google Scholar
- ~BLUMER, A., EHRENFEUCHT, A., HAUSSLER, D., AND WARMUTH, M. 1989. Learnability and the ~Vapnik Chervonenkis &mension. J. ACM 36, 4, (Oct.) 929 965. Google Scholar
- ~CHANDRA, n. K., STOCKMEYER, L. J., AND VISHK1N, U. 1984. Constant depth reducibility. SIAM ~J. Comput. I3, 2, 423-432.Google Scholar
- ~CHERNOFF, H. 1952. A measure of asymptotic etfic~ency for tests of a hypothesis based on the ~sum of observations. Ann. Math. Stat. 23, 493-509.Google Scholar
- ~DIFFIE, W., AND HELLMAN, M. 1976. New directions in cryptography. IEEE Trans. Inf. TheoO, ~22, 644-654.Google Scholar
- ~GAREY, M., AND JOHNSON, D. 1979. Computers and intractubihty: A guide to the theory of ~NP-completeness. Freeman. Google Scholar
- ~GOLD, E. M. 1978. Complexity of automaton identification from given data. bTf. Cont. 37, ~302-320.Google Scholar
- ~GOLDREICH, O., GOLDWASSER, S., AND MICAL1, S. 1986. How to construct random functions. ~J. ACM 33, 4 (Oct.), 792-807. Google Scholar
- ~HANCOCK, T. 1989. On the difficulty of finding small consistent decision trees. Harvard Univer- ~sity, unpublished manuscript.Google Scholar
- ~HAUSSLER, D., KEARNS, M., L1TTLESTONE, N., AND WARMUTH, M. 1988. Equivalence of models ~for polynomial learnability. In Proceedings of the 1988 Workshop on Computational Learning ~Theory. Morgan-Kaufmann, San Mateo, Calif., pp. 42-55. Google Scholar
- ~JUDD, S. 1984. Learning in neural networks. In Proceedings of the 1988 Workshop on Computa- ~tional Learning Theory. Morgan-Kaufmann, San Mateo, Calif., pp. 2-8. Google Scholar
- ~KEARNS, M., Li, M., PITT, L., AND VALIANT, L. 1987. On the learnability of Boolean formulae. In ~Proceedings of the 19th ACM Symposium on the Theory of Computing (New York, N.Y., May ~25-27). ACM, New York, pp. 285-295. Google Scholar
- ~KEARNS, M., AND PITT, L. 1989. A polynomial-time algorithm for learning k-variable pattern ~languages from examples. In Proceedings of the 1989 Workshop on Computational Learning ~Theory. Morgan-Kaufmann, San Mateo, Calif., pp. 57-71. ~KRANAKIS, E. 1986. Primality and cryptography. Wiley, New York. Google Scholar
- ~LEVIN, L. A. 1985. One-way functions and pseudorandom generators. In Proceedings of the 17th ~ACM Symposium on the Theory of Computing (Providence, R.I., May 6-8), ACM, New York, pp. ~363-365. Google Scholar
- ~LI, M., AND VAZIRANI, U. 1988. On the learnability of finite automata. In Proceedings of the 1988 ~Workshop on ComputationalLearning Theory. Morgan-Kaufmann, San Mateo, Calif., pp. 359-370. Google Scholar
- ~PITT, L., AND VALIArqr, L. G. 1988. Computational limitations on learning from examples. ~J. ACM 35, 4 (Oct.) 965-984. Google Scholar
- ~PITT, L. AND WARMUTH, M. K. 1988. Reductions among prediction problems: on the difficulty ~of predicting automata. In Proceedings of the 3rd IEEE Conference on Stnwture in Complexity ~Theory. IEEE, New York, pp. 60-69.Google Scholar
- ~PITT, L., AND WARMUTH, M. K. 1989. The minimum consistent DFA problem cannot he ~approximated within any polynomial. In Proceedings of the 21st ACM Symposium on the Theory ~of Computing (Seattle, Wash., May 15-17). ACM, New York, pp. 421-432. Google Scholar
- ~RAmN, M. O., 1979. Digital signatures and public key functions as intractable as factoring. Tech. ~Rep. TM-212. Lab. Comput. Sci., MIT Cambridge, Mass. Google Scholar
- ~RE1F, J. 1987. On threshold circuits and polynomial computations. In Proceedings of the 2nd ~Structure m Complextty Theory Conference. pp. 118-125.Google Scholar
- ~RIVEST, R. L., SHAMIR, A., AND ADLEMAN, L. 1978. A method for obtaining digital signatures ~and public key cryptosystems. Commun. ACM 21, 2 (Feb.), 120-126. Google Scholar
- ~SCHAPmE, R. 1989. On the strength of weak learnability. In Proceedings of the 30th IEEE ~Symposium on the Foundations of Computer Sctence. IEEE, New York, pp. 28-33.Google Scholar
- ~VALIANT, L. G. 1989. A theory of the learnable. Commun. ACM 27, 11 (Nov.) 1134-1142. Google Scholar
- ~W1GDERSON, h. 1983. A new approximate graph coloring algorithm. In Proceedbtgs of the 14th ~ACM Symposium on the Theory of Computing (San Francisco, Calif., May 5-7). ACM, New ~York, pp. 325-329. Google Scholar
- ~YAO, A. C. 1982. Theory and application of trapdoor functions. In Proceedings of the 23rd IEEE ~Symposium on the Foundations of Computer Science. IEEE, New York, pp. 80-91.Google Scholar
Index Terms
- Cryptographic limitations on learning Boolean formulae and finite automata
Recommendations
A satisfiability procedure for quantified boolean formulae
The renesse issue on satisfiabilityWe present a satisfiability tester QSAT for quantified Boolean formulae and a restriction QSATCNF of QSAT to unquantified conjunctive normal form formulae. QSAT makes use of procedures which replace subformulae of a formula by equivalent formulae. By a ...
Oblivious two-way finite automata: Decidability and complexity
We investigate the descriptional complexity and decidability of obliviousness for two-way finite automata. In particular, we consider the simulation of two-way deterministic finite automata (2DFAs) by oblivious 2DFAs, the simulation of oblivious 2DFAs ...
Clause/term resolution and learning in the evaluation of quantified Boolean formulas
Resolution is the rule of inference at the basis of most procedures for automated reasoning. In these procedures, the input formula is first translated into an equisatisfiable formula in conjunctive normal form (CNF) and then represented as a set of ...
Comments