Track papers across labs, topics, and trends.
Search papers, labs, and topics across Lattice.
This paper investigates the guessing problem of an i.i.d. random sequence when provided with element-wise correlated side-information, extending previous work that used large-deviation techniques. By employing type-counting methods, the authors derive new explicit expressions for tail probabilities and guesswork exponents in a conditional setting, which were previously unexplored. The findings include a practical application to brute-force password guessing, demonstrating how side-information can significantly influence guessing efficiency.
Guessing efficiency can be dramatically improved with side-information, revealing new insights into the limits of brute-force password attacks.
We study the problem of guessing a realization of an i.i.d. random sequence given element-wise correlated side-information. We use type-counting to provide estimates of the tail probabilities of the number of guesses for the case without side-information, which was shown earlier through large-deviation techniques. We then extend the same counting argument to the conditional setting, obtaining new explicit expressions for the corresponding guesswork exponents as divergences involving conditional tilted distributions. Finally, we provide an application of these exponents to brute-force password guessing with side-information.