Skip to main content

Quantifying computational security subject to source constraints, guesswork and inscrutability

Publication ,  Conference
Beirami, A; Calderbank, R; Duffy, K; Medard, M
Published in: IEEE International Symposium on Information Theory - Proceedings
September 28, 2015

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.

Duke Scholars

Published In

IEEE International Symposium on Information Theory - Proceedings

DOI

ISSN

2157-8095

Publication Date

September 28, 2015

Volume

2015-June

Start / End Page

2757 / 2761
 

Citation

APA
Chicago
ICMJE
MLA
NLM
Beirami, A., Calderbank, R., Duffy, K., & Medard, M. (2015). Quantifying computational security subject to source constraints, guesswork and inscrutability. In IEEE International Symposium on Information Theory - Proceedings (Vol. 2015-June, pp. 2757–2761). https://doi.org/10.1109/ISIT.2015.7282958
Beirami, A., R. Calderbank, K. Duffy, and M. Medard. “Quantifying computational security subject to source constraints, guesswork and inscrutability.” In IEEE International Symposium on Information Theory - Proceedings, 2015-June:2757–61, 2015. https://doi.org/10.1109/ISIT.2015.7282958.
Beirami A, Calderbank R, Duffy K, Medard M. Quantifying computational security subject to source constraints, guesswork and inscrutability. In: IEEE International Symposium on Information Theory - Proceedings. 2015. p. 2757–61.
Beirami, A., et al. “Quantifying computational security subject to source constraints, guesswork and inscrutability.” IEEE International Symposium on Information Theory - Proceedings, vol. 2015-June, 2015, pp. 2757–61. Scopus, doi:10.1109/ISIT.2015.7282958.
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. 2015. p. 2757–2761.

Published In

IEEE International Symposium on Information Theory - Proceedings

DOI

ISSN

2157-8095

Publication Date

September 28, 2015

Volume

2015-June

Start / End Page

2757 / 2761