Quantifying computational security subject to source constraints, guesswork and inscrutability

Conference Paper

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.

Full Text

Duke Authors

Cited Authors

  • Beirami, A; Calderbank, R; Duffy, K; Medard, M

Published Date

  • September 28, 2015

Published In

Volume / Issue

  • 2015-June /

Start / End Page

  • 2757 - 2761

International Standard Serial Number (ISSN)

  • 2157-8095

International Standard Book Number 13 (ISBN-13)

  • 9781467377041

Digital Object Identifier (DOI)

  • 10.1109/ISIT.2015.7282958

Citation Source

  • Scopus