Guessing Revisited: A Large Deviations Approach

Manjesh Kumar Hanawal, Rajesh Sundaresan

TL;DR

This paper provides a unifying framework for the "guessing problem"—determining how many attempts it takes to identify a random string—by linking it to source compression and Large Deviations Theory (LDP). The authors show that if a random process's "information spectrum" behaves predictably in a large-scale limit, we can precisely calculate the effort required by an attacker to guess a secret key or password.

What Problem Does This Paper Address?

In information theory, the "guessing problem" asks: if you have a random variable (like a password or a cryptographic key), what is the minimum expected number of guesses required to find its true value? This is a fundamental question for security, as it quantifies the effort needed for a brute-force attack.

While researchers like Arikan and Massey had previously solved this for simple cases—like strings where every character is independent and identically distributed (iid)—real-world data is rarely that simple. Data often has memory (like a Markov chain) or complex structures. Before this paper, results for different types of data sources were scattered and derived using different techniques. The authors set out to find a "universal" mathematical property that explains why these guessing exponents exist across various types of data.

Methods

The authors bridge the gap between guessing and source compression. They demonstrate that an optimal guessing strategy is essentially the inverse of an optimal compression strategy.

The core of their approach involves the Information Spectrum, which is the sequence of random variables representing the "surprise" or self-information of a string ($-\frac{1}{n} \ln P_n(X^n)$). They apply Large Deviations Theory (LDP), a branch of probability that deals with the asymptotic behavior of remote "tails" of probability distributions.

Specifically, they prove that if the distribution of the information spectrum satisfies the Large Deviation Property with a specific "rate function" $I$, then the limiting guessing exponent exists. This exponent is shown to be the Legendre-Fenchel dual of that rate function. This allows them to use standard tools from LDP (like the Contraction Principle) to solve the guessing problem for complex sources.

Datasets

As a theoretical paper in mathematical information theory, this work does not use empirical datasets. Instead, it evaluates its framework against several mathematical models of data sources:

  • Independent and Identically Distributed (iid) sources: The simplest model where each character is independent.
  • Markov sources: Where the next character depends on the current one.
  • Unifilar sources: A more general class of processes with hidden states.
  • Mixed sources: Combinations of different iid sources.
  • Stationary sources: A broad class of processes satisfying certain continuity properties.

Key Insights and Ideas

  • Guessing is Compression: The paper reinforces the "intimate relationship" between guessing and compression. If you can compress a source well, you can guess it efficiently.
  • The Information Spectrum is Key: Rather than looking at the source directly, looking at the distribution of its information content provides a much more powerful lens for analysis.
  • A Unified Theory: By using LDP, the authors show that previously disparate results (Arikan’s iid results and Malone & Sullivan’s Markov results) are actually just specific applications of the same underlying principle.
  • Variational Characterization: The guessing exponent can be expressed as a maximization problem over probability measures, balancing the entropy of the source against its "distance" (divergence) from the true distribution.

Key Results

  • Theorem 5: Establishes that the limit for the guessing moment exists if and only if the limit for the compression moment (Campbell’s coding problem) exists.
  • Proposition 7: Provides the master formula: the limiting guessing exponent is a scalar multiple of the Legendre-Fenchel dual of the information spectrum's rate function.
  • Recovery of Prior Work: The authors successfully re-derive the guessing exponents for iid and Markov sources using their new framework, proving its validity.
  • New Solutions: They provide a clear path to calculating guessing exponents for "Mixed Sources" and a broad class of stationary processes that satisfy specific "large deviation" hypotheses.

Limitations and Future Work

  • The LDP Requirement: The main limitation is that the source must satisfy the Large Deviation Property. While many common sources do, the authors note that finding a general, easily verifiable condition for any source to satisfy LDP remains an open question.
  • Finitary Processes: The authors specifically point to "finitary processes" (complex encodings of memoryless processes) as an interesting area where it is not yet known if the LDP—and thus their guessing framework—applies.
  • Key-Rate Constraints: The paper focuses on unconstrained guessing. The authors mention that extending this "information spectrum approach" to scenarios with side information or key-rate constraints is a primary direction for future research (some of which they address in subsequent work).

Summary updated

Abstract

The problem of guessing a random string is revisited. A close relation between guessing and compression is first established. Then it is shown that if the sequence of distributions of the information spectrum satisfies the large deviation property with a certain rate function, then the limiting guessing exponent exists and is a scalar multiple of the Legendre-Fenchel dual of the rate function. Other sufficient conditions related to certain continuity properties of the information spectrum are briefly discussed. This approach highlights the importance of the information spectrum in determining the limiting guessing exponent. All known prior results are then re-derived as example applications of our unifying approach.
BibTeX
@article{hanawal2011guessing,
  author = {Manjesh Kumar Hanawal and Rajesh Sundaresan},
  title = {{Guessing Revisited: A Large Deviations Approach}},
  journal = {IEEE Trans. Information Theory},
  year = {2011},
  url = {https://openreview.net/forum?id=eGog_ZaxxY},
}

Loading related content...

Figure