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

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:	https://doi.org/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
URI:	http://ieeexplore.ieee.org/xpl/RecentIss...
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)

Item control page

Downloads

Origin of downloads