[YPNG] YPNG 13 Nov 2015

[sekhar]

Hi Folks,

This week in the YPNG seminar Ahmad Beirami (Duke and MIT) will talk about:

Title: Guesswork, computational security, and information theory

Abstract:
This talk explores connections between computational security, 
probability, and information theory. If a secret string is randomly 
selected from a finite list and an inquisitor can ask "is the string 
x?", in cryptography it is deemed to be computationally secure so long 
as the list is large enough. If the distribution from which the secret 
string is picked is known, the optimal guessing strategy is to query the 
most likely string first, followed by the second most likely, and so on, 
until the unknown secret string is correctly identified. The number of 
queries after which the secret string is identified is called its 
Guesswork. Guesswork is intimately related to other problems in 
information theory, including the length of one-shot source coding, the 
computational complexity of sequential decoding, and the probability of 
error in list 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 secret string 
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 secret string? We provide a geometric perspective on 
guesswork and 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 string 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 secret string 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).

See you Friday in the Stat's classroom at 11am.

Regards,
sekhar