2018/11/11 by Neri Merhav, Asaf Cohen, Merhav, Neri +1 · 2 citations
Computer Science · #Cryptography and Data Security #FOS: Computer and information sciences #Information Theory (cs.IT) #Internet Traffic Analysis and Secure E-voting #Security in Wireless Sensor Networks
paper · pdf · doi:10.48550/arxiv.1811.04363
openalex publication_date 2018/11/11 · openalex created_date 2022/08/02 · openalex updated_date 2026/07/28
Consider the problem of guessing the realization of a random vector\n\X by repeatedly submitting queries (guesses) of the form "Is\n\X equal to \x?" until an affirmative answer is obtained.\nIn this setup, a key figure of merit is the number of queries required until\nthe right vector is identified, a number that is termed the \guesswork.\nTypically, one wishes to devise a guessing strategy which minimizes a certain\nguesswork moment.\n In this work, we study a universal, decentralized scenario where the guesser\ndoes not know the distribution of \X, and is not allowed to use a\nstrategy which prepares a list of words to be guessed in advance, or even\nremember which words were already used. Such a scenario is useful, for example,\nif bots within a Botnet carry out a brute-force attack in order to guess a\npassword or decrypt a message, yet cannot coordinate the guesses between them\nor even know how many bots actually participate in the attack.\n We devise universal decentralized guessing strategies, first, for memoryless\nsources, and then generalize them for finite-state sources. In each case, we\nderive the guessing exponent, and then prove its asymptotic optimality by\nderiving a compatible converse bound. The strategies are based on randomized\nguessing using a universal distribution. We also extend the results to guessing\nwith side information. Finally, for all above scenarios, we design efficient\nalgorithms in order to sample from the universal distributions, resulting in\nstrategies which do not depend on the source distribution, are efficient to\nimplement, and can be used asynchronously by multiple agents.\n