MURAL - Maynooth University Research Archive Library



    Brute force searching, the typical set and Guesswork


    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.

    [thumbnail of KD-Brute-force-searching.pdf]
    Preview
    Text
    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://mural.maynoothuniversity.ie/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)

    Item control page
    Item control page

    Downloads

    Downloads per month over past year

    Origin of downloads