University of Massachusetts Amherst

Search Google Appliance


Seminar: Ahmad Beirami

“Guesswork, Computational Security, and Information Theory”


Friday, October 23, 2015 - 11:00am to 12:00pm


Ahmad Beirami, Massachusetts Institute of Technology


Gunness Student Center


This talk explores connections between computational security, probability, and information theory. If an object is randomly selected from a finite list and an inquisitor can ask "is the object x?", in cryptography it is deemed to be computationally secure so long as the list is large enough. If the distribution from which the object is picked is known, the optimal guessing strategy is to query the most likely object first, followed by the second most likely, and so on, until the unknown object is correctly identified. The number of queries after which the object is identified is called its Guesswork. Guesswork is intimately related to other problems in information theory, including the length of one-shot source coding, and the computational complexity of sequential decoding. Building on seminal work that began with J. Massey (1994) and E. Arıkan (1996), the two questions this talk addresses are: if the object was randomly selected with probabilistic properties known to the inquisitor, what is the distribution of Guesswork? If the probabilistic properties of the list were hidden from the inquisitor, what would be their best guessing strategy, and how hard would it be for them to identify the object? We use the geometry of guesswork to derive accurate approximations on its distribution, its large deviations performance, and its moments. One might expect that hiding the probabilistic properties of the list would render the inquisitor incapable of guessing the object efficiently. On the contrary, we show that for a large class of stochastic processes, in probabilistic ignorance, the inquisitor would be able to universally identify the object with an average guesswork that is negligibly larger than if they knew the probabilistic properties of the list. This talk is based on joint work with Robert Calderbank (Duke), Mark Christiansen (NUIM), Ken Duffy (NUIM), Ali Makhdoumi (MIT), and Muriel Médard (MIT).

Ahmad Beirami received the B.Sc. degree in electrical engineering from Sharif University of Technology, Tehran, Iran, in 2007 and the M.Sc. and Ph.D. degrees in electrical and computer engineering from Georgia Institute of Technology, Atlanta, GA, USA, in 2011 and 2014, respectively. He is currently a Postdoctoral Associate with the Research Laboratory of Electronics (RLE), MIT. His research interests broadly include information theory, cyber security, signal processing, statistics, and networks. His Ph.D. work received the Center for Signal and Information Processing Outstanding Research Award in 2014, the 2013-2014 School of ECE Graduate Research Excellence Award, and the 2015 Sigma Xi Best Ph.D. Thesis Award, all from Georgia Institute of Technology.