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

Takhanov R(2024)Almost pairwise independence and resilience to deep learning attacksIACR Communications in Cryptology10.62056/a3ksa69p1Online publication date: 7-Oct-2024
https://doi.org/10.62056/a3ksa69p1
Shakhmetova GBarlybayev ASaukhanova ZSharipbay ARaykul SKhassenov A(2024)Enhancing Visual Data Security: A Novel FSM-Based Image Encryption and Decryption MethodologyApplied Sciences10.3390/app1411434114:11(4341)Online publication date: 21-May-2024
https://doi.org/10.3390/app14114341
Wang XLiu DZhou LLi C(2024)A Compound Approach for Monitoring the Variation in Wind Turbine Power Performance with SCADA DataApplied Sciences10.3390/app1407296314:7(2963)Online publication date: 31-Mar-2024
https://doi.org/10.3390/app14072963
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

425
Total Citations
View Citations
2,778
Total Downloads

Downloads (Last 12 months)412
Downloads (Last 6 weeks)104

Reflects downloads up to 27 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

Takhanov R(2024)Almost pairwise independence and resilience to deep learning attacksIACR Communications in Cryptology10.62056/a3ksa69p1Online publication date: 7-Oct-2024
https://doi.org/10.62056/a3ksa69p1
Shakhmetova GBarlybayev ASaukhanova ZSharipbay ARaykul SKhassenov A(2024)Enhancing Visual Data Security: A Novel FSM-Based Image Encryption and Decryption MethodologyApplied Sciences10.3390/app1411434114:11(4341)Online publication date: 21-May-2024
https://doi.org/10.3390/app14114341
Wang XLiu DZhou LLi C(2024)A Compound Approach for Monitoring the Variation in Wind Turbine Power Performance with SCADA DataApplied Sciences10.3390/app1407296314:7(2963)Online publication date: 31-Mar-2024
https://doi.org/10.3390/app14072963
Wuthrich M(2024)Experience Rating in Insurance PricingSSRN Electronic Journal10.2139/ssrn.4726206Online publication date: 2024
https://doi.org/10.2139/ssrn.4726206
Qin HYe Y(2024)Algorithms of the Möbius function by random forests and neural networksJournal of Big Data10.1186/s40537-024-00889-711:1Online publication date: 21-Feb-2024
https://doi.org/10.1186/s40537-024-00889-7
Winkler JLunglmayr M(2024)A Resource-Efficient SoC Accelerator for Boosted Decision Trees2024 22nd IEEE Interregional NEWCAS Conference (NEWCAS)10.1109/NewCAS58973.2024.10666307(6-10)Online publication date: 16-Jun-2024
https://doi.org/10.1109/NewCAS58973.2024.10666307
Golowich NMoitra ARohatgi D(2024)Exploration is Harder than Prediction: Cryptographically Separating Reinforcement Learning from Supervised Learning2024 IEEE 65th Annual Symposium on Foundations of Computer Science (FOCS)10.1109/FOCS61266.2024.00117(1953-1967)Online publication date: 27-Oct-2024
https://doi.org/10.1109/FOCS61266.2024.00117
Gerbelot CKaragulyan AKarp SRavichandran KStern MSrebro N(2024)Applying statistical learning theory to deep learningJournal of Statistical Mechanics: Theory and Experiment10.1088/1742-5468/ad3a5f2024:10(104003)Online publication date: 30-Oct-2024
https://doi.org/10.1088/1742-5468/ad3a5f
Okolie CAdeleke AMills JSmit JMaduako IBagheri HKomar TWang S(2024)Assessment of explainable tree-based ensemble algorithms for the enhancement of Copernicus digital elevation model in agricultural landsInternational Journal of Image and Data Fusion10.1080/19479832.2024.232956315:4(430-460)Online publication date: 12-Apr-2024
https://doi.org/10.1080/19479832.2024.2329563
Geng Z(2024)Modelling additive extremile regression by iteratively penalized least asymmetric weighted squares and gradient descent boostingStatistics10.1080/02331888.2024.234807758:3(576-595)Online publication date: 30-Apr-2024
https://doi.org/10.1080/02331888.2024.2348077
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