More Web Proxy on the site http://driver.im/

article

Free access

Cryptographic limitations on learning Boolean formulae and finite automata

Authors:

Michael Kearns,

Leslie ValiantAuthors Info & Claims

Journal of the ACM (JACM), Volume 41, Issue 1

Pages 67 - 95

https://doi.org/10.1145/174644.174647

Published: 02 January 1994 Publication History

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]

~AHO, A., HOPCROFr, J., AND ULLMAN, J. 1974. The Deszgn and Analyszs of Computer Algorithms. ~Addison-Wesley, Reading, Mass.

[3]

~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.

[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]

~ANGLUIN, D. 1987. Learning regular sets from queries and counterexamples. Inf. Cornpztt. 75, ~87-106.

[6]

~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.

[7]

~ANGLUIN, D., AND LAIRD, P. 1988. Learning from noisy exarnples. Mach. Learn. 2, 319-342.

[8]

~ANGLUIN, D., AND VALIANT, m. C. 1979. Fast probabilistic algorithms for Hamdtoman circuits ~and matchings. J. Comput. Syst. Scl. 18, I55 193.

[9]

~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.

[10]

~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.

[11]

~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.

[12]

~BLUM, M., AND MICALI, S. 1984. How to generate cryptographically strong sequences of ~pseudo-random bits. SIAM J. Comput. 13, 4, 850-864.

[13]

~BLUMER, A., EHRENFEUCHT, A., HAUSSLER, D., AND WARMUTH, M. 1987. Occam's razor, h~f. ~Proc. Lett. 24, 377-380.

[14]

~BLUMER, A., EHRENFEUCHT, A., HAUSSLER, D., AND WARMUTH, M. 1989. Learnability and the ~Vapnik Chervonenkis &mension. J. ACM 36, 4, (Oct.) 929 965.

[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]

~GAREY, M., AND JOHNSON, D. 1979. Computers and intractubihty: A guide to the theory of ~NP-completeness. Freeman.

[19]

~GOLD, E. M. 1978. Complexity of automaton identification from given data. bTf. Cont. 37, ~302-320.

[20]

~GOLDREICH, O., GOLDWASSER, S., AND MICAL1, S. 1986. How to construct random functions. ~J. ACM 33, 4 (Oct.), 792-807.

[21]

~HANCOCK, T. 1989. On the difficulty of finding small consistent decision trees. Harvard Univer- ~sity, unpublished manuscript.

[22]

~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.

[23]

~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.

[24]

~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.

[25]

~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.

[26]

~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.

[27]

~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.

[28]

~PITT, L., AND VALIArqr, L. G. 1988. Computational limitations on learning from examples. ~J. ACM 35, 4 (Oct.) 965-984.

[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]

~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.

[31]

~RAmN, M. O., 1979. Digital signatures and public key functions as intractable as factoring. Tech. ~Rep. TM-212. Lab. Comput. Sci., MIT Cambridge, Mass.

[32]

~RE1F, J. 1987. On threshold circuits and polynomial computations. In Proceedings of the 2nd ~Structure m Complextty Theory Conference. pp. 118-125.

[33]

~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.

[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]

~VALIANT, L. G. 1989. A theory of the learnable. Commun. ACM 27, 11 (Nov.) 1134-1142.

[36]

~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.

[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.

Cited By

Rajgopal NSanthanam R(2025)On the Structure of Learnability beyond P/polycomputational complexity10.1007/s00037-024-00260-534:1Online publication date: 6-Jan-2025
https://doi.org/10.1007/s00037-024-00260-5
Liu ZLiu Z(2025)Ensemble LearningArtificial Intelligence for Engineers10.1007/978-3-031-75953-6_9(221-242)Online publication date: 4-Jan-2025
https://doi.org/10.1007/978-3-031-75953-6_9
Liu ZLiu Z(2025)Deep LearningArtificial Intelligence for Engineers10.1007/978-3-031-75953-6_8(191-220)Online publication date: 4-Jan-2025
https://doi.org/10.1007/978-3-031-75953-6_8
Show More Cited By

Index Terms

Cryptographic limitations on learning Boolean formulae and finite automata

Recommendations

A satisfiability procedure for quantified boolean formulae
The renesse issue on satisfiability

We present a satisfiability tester QSAT for quantified Boolean formulae and a restriction QSAT_CNF 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 ...
Alternating finite automata and related problems

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image Journal of the ACM

Journal of the ACM Volume 41, Issue 1

Jan. 1994

202 pages

ISSN:0004-5411

EISSN:1557-735X

DOI:10.1145/174644

Issue’s Table of Contents

Copyright © 1994 ACM.

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 02 January 1994

Published in JACM Volume 41, Issue 1

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

446
Total Citations
View Citations
2,822
Total Downloads

Downloads (Last 12 months)389
Downloads (Last 6 weeks)44

Reflects downloads up to 09 Jan 2025

Other Metrics

View Author Metrics

Citations

Cited By

Rajgopal NSanthanam R(2025)On the Structure of Learnability beyond P/polycomputational complexity10.1007/s00037-024-00260-534:1Online publication date: 6-Jan-2025
https://doi.org/10.1007/s00037-024-00260-5
Liu ZLiu Z(2025)Ensemble LearningArtificial Intelligence for Engineers10.1007/978-3-031-75953-6_9(221-242)Online publication date: 4-Jan-2025
https://doi.org/10.1007/978-3-031-75953-6_9
Liu ZLiu Z(2025)Deep LearningArtificial Intelligence for Engineers10.1007/978-3-031-75953-6_8(191-220)Online publication date: 4-Jan-2025
https://doi.org/10.1007/978-3-031-75953-6_8
Liu ZLiu Z(2025)Artificial Neural NetworksArtificial Intelligence for Engineers10.1007/978-3-031-75953-6_7(175-190)Online publication date: 4-Jan-2025
https://doi.org/10.1007/978-3-031-75953-6_7
Liu ZLiu Z(2025)Bayesian AlgorithmsArtificial Intelligence for Engineers10.1007/978-3-031-75953-6_6(141-173)Online publication date: 4-Jan-2025
https://doi.org/10.1007/978-3-031-75953-6_6
Liu ZLiu Z(2025)Support Vector MachinesArtificial Intelligence for Engineers10.1007/978-3-031-75953-6_5(129-140)Online publication date: 4-Jan-2025
https://doi.org/10.1007/978-3-031-75953-6_5
Liu ZLiu Z(2025)Decision TreesArtificial Intelligence for Engineers10.1007/978-3-031-75953-6_4(115-128)Online publication date: 4-Jan-2025
https://doi.org/10.1007/978-3-031-75953-6_4
Liu ZLiu Z(2025)Linear ModelsArtificial Intelligence for Engineers10.1007/978-3-031-75953-6_3(95-114)Online publication date: 4-Jan-2025
https://doi.org/10.1007/978-3-031-75953-6_3
Liu ZLiu Z(2025)Tools for Artificial IntelligenceArtificial Intelligence for Engineers10.1007/978-3-031-75953-6_2(45-93)Online publication date: 4-Jan-2025
https://doi.org/10.1007/978-3-031-75953-6_2
Liu ZLiu Z(2025)Policy-Based Reinforcement LearningArtificial Intelligence for Engineers10.1007/978-3-031-75953-6_15(357-378)Online publication date: 4-Jan-2025
https://doi.org/10.1007/978-3-031-75953-6_15
Show More Cited By

View Options

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Article

Media

Figures

Other

Tables

View Issue’s Table of Contents