Cryptographic lower bounds for learnability of Boolean functions on the uniform distribution

ABSTRACT

We investigate cryptographic lower bounds on the number of samples and on computational resources required to learn several classes of boolean circuits on the uniform distribution. Under the assumption that solving n x n1+&egr; subset sum is hard, we construct (using the results of Impagliazzo and Naor [IN89] and Goldreich, Goldwasser, and Micali[GGM86] a pseudo-random function generator that can be computed by shallow boolean circuits. From this we conclude that learning AC1 circuits on the uniform distribution requires &OHgr;(nlog log n) different samples, or, alternatively, that learning AC1 circuits on the uniform distribution with a polynomial number of samples is as hard as solving n x n1+&egr; subset sum. We also show that no algorithm can learn NC1 circuits on the uniform distribution with a polynomial number of samples. Using the weaker assumption that solving n x (1+&egr;)nsubset sum is hard, we show that the class of NC circuits can not be learned with nlogcn samples for any c.

REFERENCES

• AK91: 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]
• Blum89: A. Blum. Separating Distribution-Free and Mistake-Bounded Learning Models over the Boolean Domain In Proceedings of the 31st IEEE Symposium on Foundations of Computer Science, pp. 211-218. IEEE, 1990. 444-454. ACM, 1991.
• Br83: E. F. Brickell, Solving low density knapsacks, In Proceedings of Crypto 83, pp. 25-37.
• CR88: B. Chor and R. L. Rivest, A Knapsack Type Public Key Crypto-System Based on arithmetic in finite fields, In IEEE Transaction on Information Theory Vol 34, pp. 901-909, 1988.
• GGM86: 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]
• GL89: O. Goldreich , L. A. Levin, A hard-core predicate for all one-way functions, Proceedings of the twenty-first annual ACM symposium on Theory of computing, p.25-32, May 14-17, 1989, Seattle, Washington, United States [doi>10.1145/73007.73010]
• Has86: Johan Håstad, Computational limitations of small-depth circuits, MIT Press, Cambridge, MA, 1987
• IN89: R. Impagliazzo and M. Naor. Efficient Cryptographic Schemes Provably as Secure as Subset Sum. In Proceedings of the 30th IEEE Symposium on Foundations of Computer Science, pp. 236-243. IEEE, 1989
• KV89: M. Kearns , L. G. Valiant, Crytographic limitations on learning Boolean formulae and finite automata, Proceedings of the twenty-first annual ACM symposium on Theory of computing, p.433-444, May 14-17, 1989, Seattle, Washington, United States [doi>10.1145/73007.73049]
• LO85: J. C. Lagarias , A. M. Odlyzko, Solving low-density subset sum problems, Journal of the ACM (JACM), v.32 n.1, p.229-246, Jan. 1985 [doi>10.1145/2455.2461]
• LLL82: A. K. Lenstra, tt. W. Lenstra and L. Lovasz, Factoring polynomials woth rational coeffiecients. Math. Ann., vol 261, pp. 515-534, 1982.
• Lev87: Leonid A. Levin, One-way functions and Pseudorandom generators, Combinatorica, v.7 n.4, p.357-363, Dec, 1987 [doi>10.1007/BF02579323]
• LMN89: N. Linial, Y. Mansour, and N. Nisan. Constant depth circuits, Fourier transform, and learnability. In Proceedings of the 30th IEEE Symposzum on Foundations of Computer Science, pp. 574-579. IEEE, 1989
• Man92: Yishay Mansour, An O(nlog log n) learning algorithm for DNF under the uniform distribution, Proceedings of the fifth annual workshop on Computational learning theory, p.53-61, July 27-29, 1992, Pittsburgh, Pennsylvania, United States [doi>10.1145/130385.130391]
• PW88: L. Pitt and M. Warmuth. Reductions among prediction problems: On the diff~culty of predicting automata. In Proceedings of the Thzrd Annual Structure in Complexity Theory Conference, pp. 60-69. IEEE Computer Society Press, 1988.
• Sch89: R. E. Schapire. The strength of weak learnability. In Proceedings of the SOth Annual Symposium on Foundations of Computer Science, pp. 28-33. IEEE, 1989.
• Val84: 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]

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.1 COMPUTATION BY ABSTRACT DEVICES

Additional Classification:
  E. Data
  E.3 DATA ENCRYPTION

  F. Theory of Computation
  F.1 COMPUTATION BY ABSTRACT DEVICES

  G. Mathematics of Computing
  G.3 PROBABILITY AND STATISTICS
      Subjects: Random number generation

General Terms:
Theory, Verification