Brute force searching, the typical set and Guesswork
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...
| Main Authors: | , , , |
|---|---|
| Other Authors: | |
| Format: | Article |
| Language: | en_US |
| Published: |
Institute of Electrical and Electronics Engineers (IEEE)
2014
|
| Online Access: | http://hdl.handle.net/1721.1/90432 https://orcid.org/0000-0003-2912-7972 https://orcid.org/0000-0003-4059-407X |
| _version_ | 1826197548040192000 |
|---|---|
| author | Christiansen, Mark M. Duffy, Ken R. Medard, Muriel Calmon, Flavio du Pin |
| author2 | Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science |
| author_facet | Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science Christiansen, Mark M. Duffy, Ken R. Medard, Muriel Calmon, Flavio du Pin |
| author_sort | Christiansen, Mark M. |
| collection | MIT |
| description | 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. |
| first_indexed | 2024-09-23T10:49:22Z |
| format | Article |
| id | mit-1721.1/90432 |
| institution | Massachusetts Institute of Technology |
| language | en_US |
| last_indexed | 2024-09-23T10:49:22Z |
| publishDate | 2014 |
| publisher | Institute of Electrical and Electronics Engineers (IEEE) |
| record_format | dspace |
| spelling | mit-1721.1/904322022-09-30T23:15:27Z Brute force searching, the typical set and Guesswork Christiansen, Mark M. Duffy, Ken R. Medard, Muriel Calmon, Flavio du Pin Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science Massachusetts Institute of Technology. Research Laboratory of Electronics Calmon, Flavio du Pin Medard, Muriel 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. United States. Dept. of Defense (Air Force Contract FA8721-05-C-0002) 2014-09-29T15:32:41Z 2014-09-29T15:32:41Z 2013-07 Article http://purl.org/eprint/type/ConferencePaper 978-1-4799-0446-4 2157-8095 http://hdl.handle.net/1721.1/90432 Christiansen, Mark M., Ken R. Duffy, Flavio du Pin Calmon, and Muriel Medard. “Brute Force Searching, the Typical Set and Guesswork.” 2013 IEEE International Symposium on Information Theory (July 2013). https://orcid.org/0000-0003-2912-7972 https://orcid.org/0000-0003-4059-407X en_US http://dx.doi.org/10.1109/ISIT.2013.6620428 Proceedings of the 2013 IEEE International Symposium on Information Theory Creative Commons Attribution-Noncommercial-Share Alike http://creativecommons.org/licenses/by-nc-sa/4.0/ application/pdf Institute of Electrical and Electronics Engineers (IEEE) arXiv |
| spellingShingle | Christiansen, Mark M. Duffy, Ken R. Medard, Muriel Calmon, Flavio du Pin Brute force searching, the typical set and Guesswork |
| title | Brute force searching, the typical set and Guesswork |
| title_full | Brute force searching, the typical set and Guesswork |
| title_fullStr | Brute force searching, the typical set and Guesswork |
| title_full_unstemmed | Brute force searching, the typical set and Guesswork |
| title_short | Brute force searching, the typical set and Guesswork |
| title_sort | brute force searching the typical set and guesswork |
| url | http://hdl.handle.net/1721.1/90432 https://orcid.org/0000-0003-2912-7972 https://orcid.org/0000-0003-4059-407X |
| work_keys_str_mv | AT christiansenmarkm bruteforcesearchingthetypicalsetandguesswork AT duffykenr bruteforcesearchingthetypicalsetandguesswork AT medardmuriel bruteforcesearchingthetypicalsetandguesswork AT calmonflaviodupin bruteforcesearchingthetypicalsetandguesswork |