MURAL - Maynooth University Research Archive Library



    Quantifying Computational Security Subject to Source Constraints, Guesswork and Inscrutability


    Beirami, Ahmad and Calderbank, Robert and Duffy, Ken R. and Medard, Muriel (2015) Quantifying Computational Security Subject to Source Constraints, Guesswork and Inscrutability. In: IEEE International Symposium on Information Theory (ISIT), 2015. IEEE, pp. 2757-2761. ISBN 9781467377041

    [img]
    Preview
    Download (265kB) | Preview


    Share your research

    Twitter Facebook LinkedIn GooglePlus Email more...



    Add this article to your Mendeley library


    Abstract

    Guesswork forms the mathematical framework for quantifying computational security subject to brute-force determination by query. In this paper, we consider guesswork subject to a per-symbol Shannon entropy budget. We introduce inscrutability rate as the asymptotic rate of increase in the exponential number of guesses required of an adversary to determine one or more secret strings. We prove that the inscrutability rate of any string-source supported on a finite alphabet χ, if it exists, lies between the per-symbol Shannon entropy constraint and log |χ|. We further prove that the inscrutability rate of any finite-order Markov string-source with hidden statistics remains the same as the unhidden case, i.e., the asymptotic value of hiding the statistics per each symbol is vanishing. On the other hand, we show that there exists a string-source that achieves the upper limit on the inscrutability rate, i.e., log |χ|, under the same Shannon entropy budget.

    Item Type: Book Section
    Keywords: Large deviations; Brute-force attack; Guesswork; Inscrutability; Rényi entropy; Universal methods;
    Academic Unit: Faculty of Science and Engineering > Research Institutes > Hamilton Institute
    Item ID: 9111
    Identification Number: https://doi.org/10.1109/ISIT.2015.7282958
    Depositing User: Dr Ken Duffy
    Date Deposited: 03 Jan 2018 16:49
    Publisher: IEEE
    Refereed: Yes
    URI:

    Repository Staff Only(login required)

    View Item Item control page

    Downloads

    Downloads per month over past year