Department of Mathematics
 Search | Help | Login | pdf version | printable version

Math @ Duke



Publications [#326896] of Robert Calderbank

Papers Published

  1. Beirami, A; Calderbank, R; Duffy, K; Medard, M, Quantifying computational security subject to source constraints, guesswork and inscrutability, Ieee International Symposium on Information Theory Proceedings, vol. 2015-June (September, 2015), pp. 2757-2761, ISBN 9781467377041 [doi]
    (last updated on 2018/11/15)

    © 2015 IEEE. 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.
ph: 919.660.2800
fax: 919.660.2821

Mathematics Department
Duke University, Box 90320
Durham, NC 27708-0320