MURAL - Maynooth University Research Archive Library

    Computational Security Subject to Source Constraints, Guesswork and Inscrutability

    Beirami, Ahmad and Calderbank, Robert and Duffy, Ken R. and Medard, Muriel (2015) Computational Security Subject to Source Constraints, Guesswork and Inscrutability. In: IEEE Symposium on Information Theory, 14-19 June 2015, Hong Kong.

    Download (414kB) | Preview

    Share your research

    Twitter Facebook LinkedIn GooglePlus Email more...

    Add this article to your Mendeley library


    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 to quantify the asymptotic difficulty of guessing U out of V secret strings drawn from the string-source and prove that the inscrutability rate of any string-source supported on a finite alphabet X, if it exists, lies between the per-symbol Shannon entropy constraint and log |X|. We show that for a stationary string-source, the inscrutability rate of guessing any fraction (1 - ϵ) of the V strings for any fixed ϵ > 0, as V grows, approaches the per-symbol Shannon entropy constraint (which is equal to the Shannon entropy rate for the stationary string-source). This corresponds to the minimum inscrutability rate among all string-sources with the same per-symbol Shannon entropy. 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 |X|, under the same Shannon entropy budget.

    Item Type: Conference or Workshop Item (Paper)
    Keywords: Brute-force attack; Guesswork; Inscrutability; Rényi entropy; Universal methods; Large deviations;
    Academic Unit: Faculty of Science and Engineering > Research Institutes > Hamilton Institute
    Item ID: 6215
    Depositing User: Dr Ken Duffy
    Date Deposited: 23 Jun 2015 15:11
    Refereed: No
      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)

      View Item Item control page


      Downloads per month over past year

      Origin of downloads