Learning to impersonate

ABSTRACT

Consider Alice and Bob, who have some shared secret which helps Alice to identify Bob-impersonators, and Eve, who does not know their secret. Eve wants to impersonate Bob and "fool" Alice. If Eve is computationally unbounded, how long does she need to observe Bob before she can impersonate him? What is a good strategy for Eve? If (cryptographic) one-way functions exist, an efficient Eve cannot impersonate even very simple Bobs, but if they do not exist, can Eve learn to impersonate any efficient Bob?We formalize these questions in a new computational learning model, which we believe captures a wide variety of natural learning tasks, and tightly bound the number of observations Eve makes in terms of the secret's entropy. We then show that if one-way functions do not exist, then an efficient Eve can learn to impersonate any efficient Bob nearly as well as an unbounded Eve.For the full version of this work see (Naor & Rothblum, 2006).

REFERENCES

• 1: Naoki Abe , Manfred K. Warmuth, On the Computational Complexity of Approximating Distributions by Probabilistic Automata, Machine Learning, v.9 n.2-3, p.205-260, July 1992 [doi>10.1007/BF00992677]
• 2: Benny Applebaum , Yuval Ishai , Eyal Kushilevitz, Cryptography in NC", Proceedings of the 45th Annual IEEE Symposium on Foundations of Computer Science (FOCS'04), p.166-175, October 17-19, 2004 [doi>10.1109/FOCS.2004.20]
• 3: Baum, L. E. (1972) An inequality and associated maximization technique in statistical estimation of probabilistic functions of a Markov process. Inequalities 627(3): 1--8.
• 4: Baum, L. E., Petrie, T., Soules, G., & Weiss, N. (1970) A maximization technique occurring in the statistical analysis of probabilistic functions of Markov chains. Annals of Mathematical Statistics 41: 164--171.
• 5: David Gillman , Michael Sipser, Inference and minimization of hidden Markov chains, Proceedings of the seventh annual conference on Computational learning theory, p.147-158, July 12-15, 1994, New Brunswick, New Jersey, United States [doi>10.1145/180139.181091]
• 6: O. Goldreich, A note on computational indistinguishability, Information Processing Letters, v.34 n.6, p.277-281, May 1990 [doi>10.1016/0020-0190(90)90010-U]
• 7: Oded Goldreich, Foundations of Cryptography: Basic Tools, Cambridge University Press, New York, NY, 2000
• 8: Johan HÅstad , Russell Impagliazzo , Leonid A. Levin , Michael Luby, A Pseudorandom Generator from any One-way Function, SIAM Journal on Computing, v.28 n.4, p.1364-1396, Aug. 1999 [doi>10.1137/S0097539793244708]
• 9: David P. Helmbold , Philip M. Long, Tracking Drifting Concepts By Minimizing Disagreements, Machine Learning, v.14 n.1, p.27-45, Jan. 1994 [doi>10.1023/A:1022694620923]
• 10: R. Impagliazzo, A personal view of average-case complexity, Proceedings of the 10th Annual Structure in Complexity Theory Conference (SCT'95), p.134, June 19-22, 1995
• 11: Impagliazzo, R., & Levin, L. A. (1990) No Better Ways to Generate Hard NP Instances than Picking Uniformly at Random. FOCS 1990: 812--821.
• 12: Impagliazzo, R., & Luby, M. (1989) One-way Functions are Essential for Complexity Based Cryptography. FOCS 1989: 230--235.
• 13: Michael Kearns , Yishay Mansour , Dana Ron , Ronitt Rubinfeld , Robert E. Schapire , Linda Sellie, On the learnability of discrete distributions, Proceedings of the twenty-sixth annual ACM symposium on Theory of computing, p.273-282, May 23-25, 1994, Montreal, Quebec, Canada [doi>10.1145/195058.195155]
• 14: Michael J. Kearns , Robert E. Schapire, Efficient distribution-free learning of probabilistic concepts, Journal of Computer and System Sciences, v.48 n.3, p.464-497, June 1994 [doi>10.1016/S0022-0000(05)80062-5]
• 15: Michael J. Kearns , Umesh V. Vazirani, An introduction to computational learning theory, MIT Press, Cambridge, MA, 1994
• 16: Maurer, U. M. (2000) Authentication theory and hypothesis testing. IEEE Transactions on Information Theory 46(4): 1350--1356.
• 17: Moni Naor , Guy N. Rothblum, The Complexity of Online Memory Checking, Proceedings of the 46th Annual IEEE Symposium on Foundations of Computer Science, p.573-584, October 23-25, 2005 [doi>10.1109/SFCS.2005.71]
• 18: Naor, M., & Rothblum, G. N. (2006) Learning to Impersonate. Full version available at: www.wisdom.weizmann.ac.il/~naor/PAPERS/acd_abs.html.
• 19: Rabiner, L. R. (1989) "A tutorial on hidden Markov models and selected applications in speech recognition". Proceedings of the IEEE 77 (2): 257--286.
• 20: Dana Ron , Yoram Singer , Naftali Tishby, The power of amnesia: learning probabilistic automata with variable memory length, Machine Learning, v.25 n.2-3, p.117-149, Nov./Dec. 1996 [doi>10.1007/BF00114008]
• 21: Shannon, C. E. (1949) Communication Theory of Secrecy Systems. Bell System Technical Journal 28: 656--715.
• 22: Gustavus J Simmons, Authentication theory/coding theory, Proceedings of CRYPTO 84 on Advances in cryptology, p.411-431, August 1985, Santa Barbara, California, United States
• 23: 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:
  G. Mathematics of Computing
  G.3 PROBABILITY AND STATISTICS
      Subjects: Markov processes

Additional Classification:
  E. Data
  E.3 DATA ENCRYPTION

  G. Mathematics of Computing
  G.3 PROBABILITY AND STATISTICS
      Subjects: Statistical computing

General Terms:
Algorithms, Theory