Learning to impersonate

  • Moni Naor ,
  • Guy Rothblum

ICML |

Consider Alice, who is interacting with Bob. Alice and Bob have some shared secret which helps Alice identify Bob-impersonators. Now consider Eve, who knows Alice and Bob, but does not know their shared secret. Eve would like to impersonate Bob and \fool” Alice without knowing the secret. If Eve is computationally unbounded, how long does she need to observe Alice and Bob interacting before she can successfully impersonate Bob? What is a good strategy for Eve in this setting? If Eve runs in polynomial time, and if there exists a one-way function, then it is not hard to see that Alice and Bob may be \safe” from impersonators, but is the existence of one-way functions an essential condition? Namely, if one-way functions do not exist, can an efficient Eve always impersonate Bob? In this work we consider these natural questions from the point of view of Ever, who is trying to observe Bob and learn to impersonate him. We formalize this setting in a new computational learning model of learning adaptively changing distributions (ACDs), which we believe captures a wide variety of natural learning tasks and is of interest from both cryptographic and computational learning points of view. We present a learning algorithm that Eve can use to successfully learn to impersonate Bob in the information-theoretic setting. We also show that in the computational setting an efficient Eve can learn to impersonate any efficient Bob if and only if one-way function do not exist.