[YPNG] YPNG 13 Nov 2015
sekhar
sekhar.tatikonda at yale.edu
Wed Nov 11 08:24:07 EST 2015
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
More information about the YPNG
mailing list