Brute force searching, the typical set and Guesswork

Kenneth Duffy

Ken Duffy received the B.A.(mod) and Ph.D. degrees in mathematics from Trinity College Dublin, Ireland. He is a member of faculty at the Hamilton Institute of the National University of Ireland Maynooth where his main research interests encompass probability theory and its application to science and engineering

Abstract:

The talk explores murky water between computational security, probability and information theory. If an object is 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. Implicit in this is there is no prior information known to the inquisitor about the likely nature of the object selected.

The two questions this talk addresses are: if the object was selected stochastically with probabilistic properties known to the inquisitor, what is the distribution for how many attempts it takes them to correctly guess the object? If the object is selected from a source subject to typical set coding, does the Asymptotic Equipartition Property mean we can assume it was uniformly distributed?

Building on curious work that began with J. Massey in '94 and E. Arikan in '96, answering the first question gives a surprising estimate in the field of stochastic orders based on a Legendre-Fenchel transform of Renyi entropy. Worryingly, the second answer transpires to be negative: the uniform AEP ansatz leads to a guessing problem that's exponentially harder in word length than the true typical set guesswork problem.

This talk is based on work with M. Christiansen (NUIM), as well as with with M. Christiansen, F. du Pin Calmon & M. Medard (MIT).

cryptography it is deemed to be computationally secure so long as the list is large enough. Implicit in this is there is no prior information known to the inquisitor about the likely nature of the object selected.

The two questions this talk addresses are: if the object was selected stochastically with probabilistic properties known to the inquisitor, what is the distribution for how many attempts it takes them to correctly guess the object? If the object is selected from a source subject to typical set coding, does the Asymptotic Equipartition Property mean we can assume it was uniformly distributed?

Building on curious work that began with J. Massey in '94 and E. Arikan in '96, answering the first question gives a surprising estimate in the field of stochastic orders based on a Legendre-Fenchel transform of Renyi entropy. Worryingly, the second answer transpires to be negative: the uniform AEP ansatz leads to a guessing problem that's exponentially harder in word length than the true typical set guesswork problem.

This talk is based on work with M. Christiansen (NUIM), as well as with with M. Christiansen, F. du Pin Calmon & M. Medard (MIT).

Theme by Danetsoft and Danang Probo Sayekti inspired by Maksimer