A Characterization of Guesswork on Swiftly Tilting Curves

Ahmad Beirami, A. Robert Calderbank, Mark M. Christiansen, Ken R. Duffy, Muriel Médard

This paper, "A Characterization of Guesswork on Swiftly Tilting Curves," provides a deep geometric and information-theoretic dive into "guesswork"—a concept that measures the effort required to identify a secret message or crack a password. By leveraging the "tilt" operation on probability distributions, the authors move beyond asymptotic limits to provide a precise characterization of guesswork for strings of any length.

TL;DR

The authors introduce a geometric framework using "tilted" probability distributions to characterize guesswork—the number of attempts needed to identify a secret string. They prove that guesswork orderings are fundamentally tied to exponential families of distributions and provide a highly accurate new approximation for the probability of guesswork that works even for very short strings.

What Problem Does This Paper Address?

In information theory, guesswork is the number of trials an adversary (or a decoder) must make to correctly identify a realization of a random variable, assuming they guess in order from most likely to least likely. It is a critical metric for password security, sequential decoding, and list decoding.

While previous researchers (like Massey and Arıkan) linked the moments of guesswork to Shannon and Rényi entropy, their results were primarily asymptotic—meaning they only described what happens as the strings become infinitely long. There was a significant gap in understanding:

  1. Reverse Guesswork: What happens if we guess from least likely to most likely? (Important for characterizing the "tail" of the distribution).
  2. Non-Asymptotic Behavior: How can we accurately estimate the probability of needing exactly $k$ guesses for a short string (e.g., a 10-character password)?
  3. Geometric Structure: Is there a fundamental relationship between different sources that produce the same guessing order?

Methods

The core of the paper is the tilt operation ($T(\mu, \alpha)$). Given a source distribution $\mu$, the tilt operation creates a new distribution where each probability is raised to the power of $\alpha$ and re-normalized. This creates a "tilted family" of distributions—a curve in the probability simplex.

Key methodological contributions include:

  • Tilted Weakly Typical Sets: The authors generalize the standard Asymptotic Equipartition Property (AEP). While standard typicality only describes "average" behavior, tilted typicality allows the authors to treat atypical strings as "typical" under a different tilted distribution.
  • Large Deviation Principle (LDP): They prove that the logarithm of reverse guesswork satisfies an LDP. This was previously difficult because the rate function for reverse guesswork is concave, making standard tools like the Gärtner-Ellis Theorem inapplicable.
  • Laplace’s Method: To move from theory to practice, they use Laplace’s method for integral approximation to derive a closed-form formula for the Probability Mass Function (PMF) of guesswork.

Datasets

The paper evaluates its theoretical findings using several synthetic "string-sources":

  • $S_2$: A binary Bernoulli source (p=0.2, 0.8).
  • $S_3$: A ternary memoryless source (0.2, 0.3, 0.5).
  • $S_{77}$: A 77-ary source inspired by the empirical distribution of characters found in real-world password databases.
  • Markov/HMM Sources: They also test their approximation on first-order Markov and Hidden Markov Models to demonstrate the robustness of their formulas beyond simple i.i.d. sources.

Key Insights and Ideas

  • The "Aha" Moment on Ordering: The authors prove that two different sources will result in the exact same guesswork ordering for all string lengths if and only if they belong to the same "tilted family." This gives the tilt operation a concrete operational meaning.
  • Atypical is Typical (Somewhere): Every "rare" event in a distribution $\mu$ is actually a "typical" event in some tilted version $T(\mu, \alpha)$. By "sweeping" $\alpha$ across the real line, the authors can characterize the entire probability space, not just the high-probability center.
  • The Value of Reverse Guesswork: While forward guesswork tells us how quickly we find a string, reverse guesswork is mathematically better suited for estimating the likelihood of "large" numbers of guesses (the unlikely events that represent the greatest security risks).

Key Results

  • LDP for Reverse Guesswork: The paper successfully characterizes the rate function for reverse guesswork, showing it is a concave function of the entropy of the tilted source.
  • High-Accuracy Approximation: The proposed approximation for the PMF of guesswork (Equation 184) shows "excellent concordance" with actual distributions. In numerical tests with strings as short as $n=8$, the approximation curve almost perfectly overlaps with the true probability staircase.
  • Generalization: Even though the formal proofs focus on memoryless sources, numerical results show the approximation remains highly accurate for Markov and Hidden Markov sources, suggesting the "tilted curve" framework is a universal feature of guesswork.

Limitations and Future Work

  • Formal Proofs for Memory: The rigorous LDP and characterization proofs are limited to memoryless (i.i.d.) sources. While the numerical results for Markov sources are promising, the formal theory for sources with memory remains an open area.
  • Alphabet Constraints: The current work assumes a finite alphabet. Extending this to infinite alphabets or continuous distributions would require further mathematical refinement.
  • Computational Complexity: While the approximation formula is efficient, finding the specific $\alpha$ that corresponds to a given guesswork value requires solving an implicit equation, which may be a hurdle for real-time applications.

The authors suggest that future work should focus on generalizing these results to a wider class of stationary ergodic sources, potentially unifying the study of guesswork across all types of information processes.

Summary updated

Abstract

Given a collection of strings, each with an associated probability of occurrence, the guesswork of each of them is their position in a list ordered from most likely to least likely, breaking ties arbitrarily. The guesswork is central to several applications in information theory: average guesswork provides a lower bound on the expected computational cost of a sequential decoder to decode successfully the transmitted message; the complementary cumulative distribution function of guesswork gives the error probability in list decoding; the logarithm of guesswork is the number of bits needed in optimal lossless one-to-one source coding; and the guesswork is the number of trials required of an adversary to breach a password protected system in a brute-force attack. In this paper, we consider memoryless string sources that generate strings consisting of independent and identically distributed characters drawn from a finite alphabet, and characterize their corresponding guesswork. Our main tool is the tilt operation on a memoryless string source. We show that the tilt operation on a memoryless string source parametrizes an exponential family of memoryless string sources, which we refer to as the tilted family of the string source. We provide an operational meaning to the tilted families by proving that two memoryless string sources result in the same guesswork on all strings of all lengths if and only if their respective categorical distributions belong to the same tilted family. Establishing some general properties of the tilt operation, we generalize the notions of weakly typical set and asymptotic equipartition property to tilted weakly typical sets of different orders. We use this new definition to characterize the large deviations for all atypical strings and characterize the volume of tilted weakly typical sets of different orders. We subsequently build on this characterization to prove large deviation bounds on guesswork and provide an accurate approximation of its probability mass function.
BibTeX
@article{beirami2019characterization,
  author = {Ahmad Beirami and A. Robert Calderbank and Mark M. Christiansen and Ken R. Duffy and Muriel Médard},
  title = {{A Characterization of Guesswork on Swiftly Tilting Curves}},
  journal = {IEEE Trans. Information Theory},
  year = {2019},
  url = {https://openreview.net/forum?id=xZN8c-XF1fM},
}

Loading related content...

Figure