MURAL - Maynooth University Research Archive Library



    Guesswork, large deviations and Shannon entropy


    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

    [thumbnail of KD-guesswork.pdf]
    Preview
    Text
    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)

    Item control page
    Item control page

    Downloads

    Downloads per month over past year

    Origin of downloads