Multi-User Guesswork and Brute Force Security
The guesswork problem was originally motivated by a desire to quantify computational security for single user systems. Leveraging recent results from its analysis, we extend the remit and utility of the framework to the quantification of the computational security of multi-user systems. In particula...
| Main Authors: | , , , |
|---|---|
| Other Authors: | |
| Format: | Article |
| Language: | en_US |
| Published: |
Institute of Electrical and Electronics Engineers (IEEE)
2018
|
| Online Access: | http://hdl.handle.net/1721.1/113425 https://orcid.org/0000-0003-4059-407X https://orcid.org/0000-0003-2912-7972 |
| _version_ | 1826196284500869120 |
|---|---|
| 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 | The guesswork problem was originally motivated by a desire to quantify computational security for single user systems. Leveraging recent results from its analysis, we extend the remit and utility of the framework to the quantification of the computational security of multi-user systems. In particular, assume that V users independently select strings stochastically from a finite, but potentially large, list. An inquisitor who does not know which strings have been selected wishes to identify U of them. The inquisitor knows the selection probabilities of each user and is equipped with a method that enables the testing of each (user, string) pair, one at a time, for whether that string had been selected by that user. Here, we establish that, unless U=V, there is no general strategy that minimizes the distribution of the number of guesses, but in the asymptote as the strings become long we prove the following: by construction, there is an asymptotically optimal class of strategies; the number of guesses required in an asymptotically optimal strategy satisfies a large deviation principle with a rate function, which is not necessarily convex, that can be determined from the rate functions of optimally guessing individual users' strings; if all users' selection statistics are identical, the exponential growth rate of the average guesswork as the string-length increases is determined by the specific Rényi entropy of the string-source with parameter (V-U+1)/(V-U+2), generalizing the known V=U=1 case; and that the Shannon entropy of the source is a lower bound on the average guesswork growth rate for all U and V, thus providing a bound on computational security for multi-user systems. Examples are presented to illustrate these results and their ramifications for systems design. |
| first_indexed | 2024-09-23T10:24:28Z |
| format | Article |
| id | mit-1721.1/113425 |
| institution | Massachusetts Institute of Technology |
| language | en_US |
| last_indexed | 2024-09-23T10:24:28Z |
| publishDate | 2018 |
| publisher | Institute of Electrical and Electronics Engineers (IEEE) |
| record_format | dspace |
| spelling | mit-1721.1/1134252022-09-26T17:40:33Z Multi-User Guesswork and Brute Force Security Christiansen, Mark M. Duffy, Ken R. Medard, Muriel Calmon, Flavio du Pin Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science Medard, Muriel Calmon, Flavio du Pin The guesswork problem was originally motivated by a desire to quantify computational security for single user systems. Leveraging recent results from its analysis, we extend the remit and utility of the framework to the quantification of the computational security of multi-user systems. In particular, assume that V users independently select strings stochastically from a finite, but potentially large, list. An inquisitor who does not know which strings have been selected wishes to identify U of them. The inquisitor knows the selection probabilities of each user and is equipped with a method that enables the testing of each (user, string) pair, one at a time, for whether that string had been selected by that user. Here, we establish that, unless U=V, there is no general strategy that minimizes the distribution of the number of guesses, but in the asymptote as the strings become long we prove the following: by construction, there is an asymptotically optimal class of strategies; the number of guesses required in an asymptotically optimal strategy satisfies a large deviation principle with a rate function, which is not necessarily convex, that can be determined from the rate functions of optimally guessing individual users' strings; if all users' selection statistics are identical, the exponential growth rate of the average guesswork as the string-length increases is determined by the specific Rényi entropy of the string-source with parameter (V-U+1)/(V-U+2), generalizing the known V=U=1 case; and that the Shannon entropy of the source is a lower bound on the average guesswork growth rate for all U and V, thus providing a bound on computational security for multi-user systems. Examples are presented to illustrate these results and their ramifications for systems design. 2018-02-05T19:18:40Z 2018-02-05T19:18:40Z 2015-10 Article http://purl.org/eprint/type/JournalArticle 0018-9448 1557-9654 http://hdl.handle.net/1721.1/113425 Christiansen, Mark M., et al. “Multi-User Guesswork and Brute Force Security.” IEEE Transactions on Information Theory, vol. 61, no. 12, Dec. 2015, pp. 6876–86. https://orcid.org/0000-0003-4059-407X https://orcid.org/0000-0003-2912-7972 en_US http://dx.doi.org/10.1109/tit.2015.2482972 IEEE Transactions 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 Multi-User Guesswork and Brute Force Security |
| title | Multi-User Guesswork and Brute Force Security |
| title_full | Multi-User Guesswork and Brute Force Security |
| title_fullStr | Multi-User Guesswork and Brute Force Security |
| title_full_unstemmed | Multi-User Guesswork and Brute Force Security |
| title_short | Multi-User Guesswork and Brute Force Security |
| title_sort | multi user guesswork and brute force security |
| url | http://hdl.handle.net/1721.1/113425 https://orcid.org/0000-0003-4059-407X https://orcid.org/0000-0003-2912-7972 |
| work_keys_str_mv | AT christiansenmarkm multiuserguessworkandbruteforcesecurity AT duffykenr multiuserguessworkandbruteforcesecurity AT medardmuriel multiuserguessworkandbruteforcesecurity AT calmonflaviodupin multiuserguessworkandbruteforcesecurity |