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, 1419 June 2015, Hong Kong.
Abstract
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 to quantify the asymptotic difficulty of guessing
U out of V secret strings drawn from the stringsource and
prove that the inscrutability rate of any stringsource supported
on a finite alphabet X, if it exists, lies between the persymbol
Shannon entropy constraint and log X. We show that for a
stationary stringsource, the inscrutability rate of guessing any
fraction (1  ϵ) of the V strings for any fixed ϵ > 0, as V
grows, approaches the persymbol Shannon entropy constraint
(which is equal to the Shannon entropy rate for the stationary
stringsource). This corresponds to the minimum inscrutability
rate among all stringsources with the same persymbol Shannon
entropy. 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 X, under the same Shannon
entropy budget.
Repository Staff Only(login required)

Item control page 
Downloads per month over past year