Math @ Duke

Publications [#326896] of Robert Calderbank
Papers Published
 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. 2015June
(September, 2015),
pp. 27572761, ISBN 9781467377041 [doi]
(last updated on 2018/11/15)
Abstract: © 2015 IEEE. Guesswork forms the mathematical framework for quantifying computational security subject to bruteforce determination by query. In this paper, we consider guesswork subject to a persymbol 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 stringsource supported on a finite alphabet χ, if it exists, lies between the persymbol Shannon entropy constraint and log χ. We further prove that the inscrutability rate of any finiteorder Markov stringsource 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 stringsource that achieves the upper limit on the inscrutability rate, i.e., log χ, under the same Shannon entropy budget.


dept@math.duke.edu
ph: 919.660.2800
fax: 919.660.2821
 
Mathematics Department
Duke University, Box 90320
Durham, NC 277080320

