Cryptographic limitations on learning Boolean formulae and finite automata

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.

REFERENCES

• 1: ~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.
• 2: Alfred V. Aho , John E. Hopcroft, The Design and Analysis of Computer Algorithms, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1974
• 3: Werner Alexi , Benny Chor , Oded Goldreich , Claus P. Schnorr, RSA and Rabin functions: certain parts are as hard as the whole, SIAM Journal on Computing, v.17 n.2, p.194-209, April 1988 [doi>10.1137/0217013]
• 4: ~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.
• 5: Dana Angluin, Learning regular sets from queries and counterexamples, Information and Computation, v.75 n.2, p.87-106, November 1, 1987 [doi>10.1016/0890-5401(87)90052-6]
• 6: Dana Angluin , Michael Kharitonov, When won't membership queries help?, Proceedings of the twenty-third annual ACM symposium on Theory of computing, p.444-454, May 05-08, 1991, New Orleans, Louisiana, United States [doi>10.1145/103418.103420]
• 7: Dana Angluin, Queries and Concept Learning, Machine Learning, v.2 n.4, p.319-342, April 1988 [doi>10.1023/A:1022821128753]
• 8: ~ANGLUIN, D., AND VALIANT, m. C. 1979. Fast probabilistic algorithms for Hamdtoman circuits ~and matchings. J. Comput. Syst. Scl. 18, I55 193.
• 9: Paul W Beame , Stephen A Cook , H James Hoover, Log depth circuits for division and related problems, SIAM Journal on Computing, v.15 n.4, p.994-1003, Nov. 1986 [doi>10.1137/0215070]
• 10: A. Blum, An O(n^0.4)-approximation algorithm for 3-coloring, Proceedings of the twenty-first annual ACM symposium on Theory of computing, p.535-542, May 14-17, 1989, Seattle, Washington, United States [doi>10.1145/73007.73058]
• 11: Avrim Blum , Ronald L. Rivest, Training a 3-node neural network is NP-complete, Proceedings of the first annual workshop on Computational learning theory, p.9-18, August 03-05, 1988, MIT, Cambridge, Massachusetts, United States
• 12: Manuel Blum , Silvio Micali, How to generate cryptographically strong sequences of pseudo-random bits, SIAM Journal on Computing, v.13 n.4, p.850-864, Nov. 1984 [doi>10.1137/0213053]
• 13: Alselm Blumer , Andrzej Ehrenfeucht , David Haussler , Manfred K. Warmuth, Occam's razor, Information Processing Letters, v.24 n.6, p.377-380, 6 April 1987 [doi>10.1016/0020-0190(87)90114-1]
• 14: Anselm Blumer , A. Ehrenfeucht , David Haussler , Manfred K. Warmuth, Learnability and the Vapnik-Chervonenkis dimension, Journal of the ACM (JACM), v.36 n.4, p.929-965, Oct. 1989 [doi>10.1145/76359.76371]
• 15: ~CHANDRA, n. K., STOCKMEYER, L. J., AND VISHK1N, U. 1984. Constant depth reducibility. SIAM ~J. Comput. I3, 2, 423-432.
• 16: ~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.
• 17: ~DIFFIE, W., AND HELLMAN, M. 1976. New directions in cryptography. IEEE Trans. Inf. TheoO, ~22, 644-654.
• 18: Michael R. Garey , David S. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness, W. H. Freeman & Co., New York, NY, 1979
• 19: ~GOLD, E. M. 1978. Complexity of automaton identification from given data. bTf. Cont. 37, ~302-320.
• 20: Oded Goldreich , Shafi Goldwasser , Silvio Micali, How to construct random functions, Journal of the ACM (JACM), v.33 n.4, p.792-807, Oct. 1986 [doi>10.1145/6490.6503]
• 21: ~HANCOCK, T. 1989. On the difficulty of finding small consistent decision trees. Harvard Univer- ~sity, unpublished manuscript.
• 22: David Haussler , Michael Kearns , Nick Littlestone , Manfred K. Warmuth, Equivalence of models for polynomial learnability, Proceedings of the first annual workshop on Computational learning theory, p.42-55, August 03-05, 1988, MIT, Cambridge, Massachusetts, United States
• 23: J. Stephen Judd, Learning in neural networks, Proceedings of the first annual workshop on Computational learning theory, p.2-8, August 03-05, 1988, MIT, Cambridge, Massachusetts, United States
• 24: M. Kearns , M. Li , L. Pitt , L. Valiant, On the learnability of Boolean formulae, Proceedings of the nineteenth annual ACM conference on Theory of computing, p.285-295, January 1987, New York, New York, United States [doi>10.1145/28395.28426]
• 25: Michael Kearns , Leonard Pitt, A polynomial-time algorithm for learning k-variable pattern languages from examples, Proceedings of the second annual workshop on Computational learning theory, p.57-71, December 1989, Santa Cruz, California, United States
• 26: L A Levin, One-way functions and pseudorandom generators, Proceedings of the seventeenth annual ACM symposium on Theory of computing, p.363-365, May 06-08, 1985, Providence, Rhode Island, United States [doi>10.1145/22145.22185]
• 27: Ming Li , Umest Vazirani, On the learnability of finite automata, Proceedings of the first annual workshop on Computational learning theory, p.359-370, August 03-05, 1988, MIT, Cambridge, Massachusetts, United States
• 28: Leonard Pitt , Leslie G. Valiant, Computational limitations on learning from examples, Journal of the ACM (JACM), v.35 n.4, p.965-984, Oct. 1988 [doi>10.1145/48014.63140]
• 29: ~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.
• 30: L. Pitt , M. K. Warmuth, The minimum consistent DFA problem cannot be approximated within and polynomial, Proceedings of the twenty-first annual ACM symposium on Theory of computing, p.421-432, May 14-17, 1989, Seattle, Washington, United States [doi>10.1145/73007.73048]
• 31: M. O. Rabin, DIGITALIZED SIGNATURES AND PUBLIC-KEY FUNCTIONS AS INTRACTABLE AS FACTORIZATION, Massachusetts Institute of Technology, Cambridge, MA, 1979
• 32: ~RE1F, J. 1987. On threshold circuits and polynomial computations. In Proceedings of the 2nd ~Structure m Complextty Theory Conference. pp. 118-125.
• 33: R. L. Rivest , A. Shamir , L. Adleman, A method for obtaining digital signatures and public-key cryptosystems, Communications of the ACM, v.21 n.2, p.120-126, Feb. 1978 [doi>10.1145/359340.359342]
• 34: ~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.
• 35: L. G. Valiant, A theory of the learnable, Communications of the ACM, v.27 n.11, p.1134-1142, Nov. 1984 [doi>10.1145/1968.1972]
• 36: Avi Wigderson, A new approximate graph coloring algorithm, Proceedings of the fourteenth annual ACM symposium on Theory of computing, p.325-329, May 05-07, 1982, San Francisco, California, United States [doi>10.1145/800070.802207]
• 37: ~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.

INDEX TERMS

Primary Classification:
  E. Data
  E.3 DATA ENCRYPTION
      Subjects: Public key cryptosystems

Additional Classification:
  F. Theory of Computation
  F.1 COMPUTATION BY ABSTRACT DEVICES
      F.1.1 Models of Computation
          Subjects: Automata (e.g., finite, push-down, resource-bounded)

  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE
      I.2.6 Learning
          Subjects: Connectionism and neural nets; Concept learning

General Terms:
Theory