Brute force searching, the typical set and Guesswork
Event details
| Date | 20.06.2013 |
| Hour | 10:00 › 11:00 |
| Speaker | Prof. Ken Duffy, National University of Ireland Maynooth |
| Location | |
| Category | Conferences - Seminars |
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 distribution of the object that 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 (with a significant contribution from EPFL's Charles Pfister, in collaboration with W. Sullivan in '04), answering the first question gives a surprising estimate, related to stochastic orders, based on a Legendre-Fenchel transform of a function 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 F. du Pin Calmon & M. Medard (MIT).
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 (with a significant contribution from EPFL's Charles Pfister, in collaboration with W. Sullivan in '04), answering the first question gives a surprising estimate, related to stochastic orders, based on a Legendre-Fenchel transform of a function 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 F. du Pin Calmon & M. Medard (MIT).
Links
Practical information
- General public
- Free
Organizer
- SuRI 2013
Contact
- Simone Muller