PROJECT TITLE :

Multi-User Guesswork and Brute Force Security

ABSTRACT:

The guesswork drawback was originally motivated by a need to quantify computational security for single user systems. Leveraging recent results from its analysis, we tend to 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 choose strings stochastically from a finite, however doubtless giant, list. An inquisitor who will not grasp that strings have been selected needs to spot $U$ of them. The inquisitor knows the choice probabilities of each user and is supplied with a technique that allows the testing of every (user, string) try, one at a time, for whether that string had been selected by that user. Here, we have a tendency to establish that, unless $U=V$ , there's no general strategy that minimizes the distribution of the amount of guesses, but in the asymptote because the strings become long we have a tendency to prove the following: by construction, there's an asymptotically optimal class of strategies; the amount of guesses needed in an asymptotically optimal strategy satisfies a massive deviation principle with a rate function, that isn't essentially convex, that may be determined from the speed functions of optimally guessing individual users’ strings; if all users’ choice statistics are identical, the exponential growth rate of the common guesswork as the string-length will increase is decided by the precise Rényi entropy of the string-supply with parameter $(V-U+1)/(V-U+two)$ , generalizing the known $V=U=one$ case; and that the Shannon entropy of the supply may be a lower certain on the average guesswork gr- wth 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.