Centralized vs decentralized multi-agent guesswork
© 2017 IEEE. We study a notion of guesswork, where multiple agents intend to launch a coordinated brute-force attack to find a single binary secret string, and each agent has access to side information generated through either a BEC or a BSC. The average number of trials required to find the secret...
| Main Authors: | , , , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
IEEE
2021
|
| Online Access: | https://hdl.handle.net/1721.1/137926 |
| _version_ | 1826198195731955712 |
|---|---|
| author | Salamatian, Salman Beirami, Ahmad Cohen, Asaf Medard, Muriel |
| author_facet | Salamatian, Salman Beirami, Ahmad Cohen, Asaf Medard, Muriel |
| author_sort | Salamatian, Salman |
| collection | MIT |
| description | © 2017 IEEE. We study a notion of guesswork, where multiple agents intend to launch a coordinated brute-force attack to find a single binary secret string, and each agent has access to side information generated through either a BEC or a BSC. The average number of trials required to find the secret string grows exponentially with the length of the string, and the rate of the growth is called the guesswork exponent. We compute the guesswork exponent for several multi-agent attacks. We show that a multi-agent attack reduces the guesswork exponent compared to a single agent, even when the agents do not exchange information to coordinate their attack, and try to individually guess the secret string using a predetermined scheme in a decentralized fashion. Further, we show that the guesswork exponent of two agents who do coordinate their attack is strictly smaller than that of any finite number of agents individually performing decentralized guesswork. |
| first_indexed | 2024-09-23T11:00:47Z |
| format | Article |
| id | mit-1721.1/137926 |
| institution | Massachusetts Institute of Technology |
| language | English |
| last_indexed | 2024-09-23T11:00:47Z |
| publishDate | 2021 |
| publisher | IEEE |
| record_format | dspace |
| spelling | mit-1721.1/1379262021-11-10T03:33:05Z Centralized vs decentralized multi-agent guesswork Salamatian, Salman Beirami, Ahmad Cohen, Asaf Medard, Muriel © 2017 IEEE. We study a notion of guesswork, where multiple agents intend to launch a coordinated brute-force attack to find a single binary secret string, and each agent has access to side information generated through either a BEC or a BSC. The average number of trials required to find the secret string grows exponentially with the length of the string, and the rate of the growth is called the guesswork exponent. We compute the guesswork exponent for several multi-agent attacks. We show that a multi-agent attack reduces the guesswork exponent compared to a single agent, even when the agents do not exchange information to coordinate their attack, and try to individually guess the secret string using a predetermined scheme in a decentralized fashion. Further, we show that the guesswork exponent of two agents who do coordinate their attack is strictly smaller than that of any finite number of agents individually performing decentralized guesswork. 2021-11-09T15:39:44Z 2021-11-09T15:39:44Z 2017-06 2019-06-20T17:48:27Z Article http://purl.org/eprint/type/ConferencePaper https://hdl.handle.net/1721.1/137926 Salamatian, Salman, Beirami, Ahmad, Cohen, Asaf and Medard, Muriel. 2017. "Centralized vs decentralized multi-agent guesswork." en 10.1109/isit.2017.8006931 Creative Commons Attribution-Noncommercial-Share Alike http://creativecommons.org/licenses/by-nc-sa/4.0/ application/pdf IEEE arXiv |
| spellingShingle | Salamatian, Salman Beirami, Ahmad Cohen, Asaf Medard, Muriel Centralized vs decentralized multi-agent guesswork |
| title | Centralized vs decentralized multi-agent guesswork |
| title_full | Centralized vs decentralized multi-agent guesswork |
| title_fullStr | Centralized vs decentralized multi-agent guesswork |
| title_full_unstemmed | Centralized vs decentralized multi-agent guesswork |
| title_short | Centralized vs decentralized multi-agent guesswork |
| title_sort | centralized vs decentralized multi agent guesswork |
| url | https://hdl.handle.net/1721.1/137926 |
| work_keys_str_mv | AT salamatiansalman centralizedvsdecentralizedmultiagentguesswork AT beiramiahmad centralizedvsdecentralizedmultiagentguesswork AT cohenasaf centralizedvsdecentralizedmultiagentguesswork AT medardmuriel centralizedvsdecentralizedmultiagentguesswork |