Christiansen, Mark M. and Duffy, Ken R. and Calmon, Flavio du Pin and Medard, Muriel
(2013)
Brute force searching, the typical set and Guesswork.
Working Paper.
arXiv.org.
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 |
| URI: |
|
| 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)
 |
Item control page |
Downloads per month over past year
Origin of downloads
Altmetric
Altmetric