Christiansen, Mark M., Duffy, Ken R., Calmon, Flavio du Pin and Medard, Muriel (2013) Brute force searching, the typical set and Guesswork. Working Paper. arXiv.org.
Preview
KD-Brute-force-searching.pdf
Download (309kB) | Preview
Abstract
Consider the situation where a word is chosen
probabilistically from a finite list. If an attacker knows the
list and can inquire about each word in turn, then selecting
the word via the uniform distribution maximizes the attacker’s
difficulty, its Guesswork, in identifying the chosen word. It is
tempting to use this property in cryptanalysis of computationally
secure ciphers by assuming coded words are drawn from a
source’s typical set and so, for all intents and purposes, uniformly
distributed within it. By applying recent results on Guesswork,
for i.i.d. sources, it is this equipartition ansatz that we investigate
here. In particular, we demonstrate that the expected Guesswork
for a source conditioned to create words in the typical set grows,
with word length, at a lower exponential rate than that of the
uniform approximation, suggesting use of the approximation is
ill-advised.
Item Type: | Monograph (Working Paper) |
---|---|
Additional Information: | Paper given at the IEEE International Symposium on Information Theory (2013). M.C. and K.D. supported by the Science Foundation Ireland Grant No. 11/PI/1177 and the Irish Higher Educational Authority (HEA) PRTLI Network Mathematics Grant. F.d.P.C. and M.M. sponsored by the Department of Defense under Air Force Contract FA8721-05-C-0002. Opinions, interpretations, recommendations, and conclusions are those of the authors and are not necessarily endorsed by the United States Government. Specifically, this work was supported by Information Systems of ASD(R&E). |
Keywords: | Brute force searching; typical set; Guesswork; information theory; security; |
Academic Unit: | Faculty of Science and Engineering > Research Institutes > Hamilton Institute |
Item ID: | 5983 |
Identification Number: | arXiv:1301.6356 |
Depositing User: | Dr Ken Duffy |
Date Deposited: | 24 Mar 2015 17:01 |
Publisher: | arXiv.org |
Refereed: | Yes |
Funders: | Science Foundation Ireland (SFI), Higher Education Authority (HEA), US Department of Defense |
Related URLs: | |
URI: | https://mu.eprints-hosting.org/id/eprint/5983 |
Use Licence: | This item is available under a Creative Commons Attribution Non Commercial Share Alike Licence (CC BY-NC-SA). Details of this licence are available here |
Repository Staff Only (login required)
Downloads
Downloads per month over past year