Christiansen, Mark M. and Duffy, Ken R. (2013) Guesswork, large deviations and Shannon entropy. IEEE Transactions on Information Theory, 59 (2). pp. 796-802. ISSN 0018-9448
Preview
KD-guesswork.pdf
Download (248kB) | Preview
Abstract
How hard is it to guess a password? Massey showed
that a simple function of the Shannon entropy of the distribution
from which the password is selected is a lower bound on the
expected number of guesses, but one which is not tight in general.
In a series of subsequent papers under ever less restrictive
stochastic assumptions, an asymptotic relationship as password
length grows between scaled moments of the guesswork and
specific R´enyi entropy was identified.
Here we show that, when appropriately scaled, as the password
length grows the logarithm of the guesswork satisfies a Large
Deviation Principle (LDP), providing direct estimates of the
guesswork distribution when passwords are long. The rate function
governing the LDP possesses a specific, restrictive form that
encapsulates underlying structure in the nature of guesswork.
Returning to Massey’s original observation, a corollary to the
LDP shows that expectation of the logarithm of the guesswork is
the specific Shannon entropy of the password selection process.
Item Type: | Article |
---|---|
Additional Information: | This is the preprint version of the published article, which is available at DOI: 10.1109/TIT.2012.2219036 |
Keywords: | Guesswork; Renyi Entropy; Shannon Entropy; Large Deviations; |
Academic Unit: | Faculty of Science and Engineering > Research Institutes > Hamilton Institute |
Item ID: | 6219 |
Identification Number: | 10.1109/TIT.2012.2219036 |
Depositing User: | Dr Ken Duffy |
Date Deposited: | 29 Jun 2015 14:41 |
Journal or Publication Title: | IEEE Transactions on Information Theory |
Publisher: | IEEE |
Refereed: | Yes |
Related URLs: | |
URI: | https://mu.eprints-hosting.org/id/eprint/6219 |
Use Licence: | This item is available under a Creative Commons Attribution Non Commercial Share Alike Licence (CC BY-NC-SA). Details of this licence are available here |
Repository Staff Only (login required)
Downloads
Downloads per month over past year