Centralized vs decentralized multi-agent guesswork

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...

Full description

Saved in:
Bibliographic Details
Main Authors: Salamatian, Salman, Beirami, Ahmad, Cohen, Asaf, Medard, Muriel
Format: Conference Proceeding
Language:English
Subjects:
brute-force attack
Computational efficiency
coordinated attack
Decoding
Distance measurement
Entropy
Guesswork
Manganese
Memoryless systems
Online Access:Request full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary: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.
ISSN:2157-8117
DOI:10.1109/ISIT.2017.8006931