MURAL - Maynooth University Research Archive Library



    Guesswork Subject to a Total Entropy Budget


    Rezaee, Arman, Beirami, Ahmad, Makhdoumi, Ali, Medard, Muriel and Duffy, Ken R. (2018) Guesswork Subject to a Total Entropy Budget. Working Paper. arXiv.

    [thumbnail of KD-Guesswork-2018.pdf]
    Preview
    Text
    KD-Guesswork-2018.pdf

    Download (415kB) | Preview

    Abstract

    We consider an abstraction of computational security in password protected systems where a user draws a secret string of given length with i.i.d. characters from a finite alphabet, and an adversary would like to identify the secret string by querying, or guessing, the identity of the string. The concept of a "total entropy budget" on the chosen word by the user is natural, otherwise the chosen password would have arbitrary length and complexity. One intuitively expects that a password chosen from the uniform distribution is more secure. This is not the case, however, if we are considering only the average guesswork of the adversary when the user is subject to a total entropy budget. The optimality of the uniform distribution for the user's secret string holds when we have also a budget on the guessing adversary. We suppose that the user is subject to a "total entropy budget" for choosing the secret string, whereas the computational capability of the adversary is determined by his "total guesswork budget." We study the regime where the adversary's chances are exponentially small in guessing the secret string chosen subject to a total entropy budget. We introduce a certain notion of uniformity and show that a more uniform source will provide better protection against the adversary in terms of his chances of success in guessing the secret string. In contrast, the average number of queries that it takes the adversary to identify the secret string is smaller for the more uniform secret string subject to the same total entropy budget.
    Item Type: Monograph (Working Paper)
    Keywords: Guesswork; Total Entropy Budget; computational security; password protected systems;
    Academic Unit: Faculty of Science and Engineering > Research Institutes > Hamilton Institute
    Item ID: 10171
    Identification Number: arXiv:1712.09082
    Depositing User: Dr Ken Duffy
    Date Deposited: 02 Nov 2018 17:21
    Publisher: arXiv
    URI: https://mural.maynoothuniversity.ie/id/eprint/10171
    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