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.
Introduction
In the field of information theory, the "guessing problem" serves as a fundamental metric for security. It asks a deceptively simple question: given a random variable—such as a cryptographic key or a password—what is the minimum expected number of attempts required for an attacker to correctly identify its value? While early work by researchers like Arikan and Massey provided solutions for independent and identically distributed (iid) sources, real-world data often exhibits complex dependencies and memory, such as those found in Markov chains or unifilar processes.
This paper provides a unifying framework for the guessing problem by establishing a rigorous link between guessing effort, source compression, and Large Deviations Theory (LDP). By focusing on the "information spectrum" of a source rather than the raw data itself, the authors demonstrate that the effort required to guess a secret can be calculated through the lens of asymptotic probability distributions.
The Relationship Between Guessing and Compression
A central pillar of this research is the "intimate relationship" between guessing and source compression. The authors demonstrate that an optimal guessing strategy is essentially the inverse of an optimal compression strategy. Specifically, if a source can be compressed efficiently, it can also be guessed efficiently.
This connection is formalized in Theorem 5, which establishes that the limit for the guessing moment exists if and only if the limit for the compression moment (specifically Campbell’s coding problem) exists. This equivalence allows researchers to leverage decades of progress in source coding to solve complex guessing problems.
The Information Spectrum and Large Deviations
The core methodology of the paper involves the Information Spectrum, defined as the sequence of random variables representing the self-information (or "surprise") of a string:
$$-\frac{1}{n} \ln P_n(X^n)$$
Rather than analyzing the source symbols directly, the authors apply Large Deviations Theory (LDP) to the distribution of this information spectrum. LDP is a branch of probability that describes the asymptotic behavior of rare events—the "tails" of a distribution.
The authors prove that if the information spectrum satisfies the Large Deviation Property with a specific rate function $I$, the limiting guessing exponent exists. In Proposition 7, they provide a master formula: the limiting guessing exponent is shown to be a scalar multiple of the Legendre-Fenchel dual of the rate function $I$. This variational characterization expresses the guessing exponent as a maximization problem over probability measures, balancing the entropy of the source against its divergence from the true distribution.
A Unified Framework for Diverse Sources
One of the paper's most significant contributions is its ability to unify previously disparate results. By using the LDP-based approach, the authors successfully re-derive known guessing exponents for various mathematical models, including:
- IID Sources: The simplest case where characters are independent.
- Markov Sources: Where the next character depends on the current state.
- Mixed Sources: Combinations of different iid sources.
- Stationary Sources: A broad class of processes satisfying specific continuity properties.
By showing that Arikan’s iid results and Malone & Sullivan’s Markov results are specific applications of the same underlying principle, the paper provides a powerful, generalized tool for information theorists.
Limitations and Future Directions
While the framework is robust, it relies on the source satisfying the Large Deviation Property. The authors note that identifying a general, easily verifiable condition that guarantees LDP for any arbitrary source remains an open challenge. Particular interest is directed toward "finitary processes"—complex encodings of memoryless processes—where it is not yet confirmed if this LDP-based framework applies.
Additionally, the current work focuses on unconstrained guessing. Future research directions include extending this information spectrum approach to scenarios involving side information or key-rate constraints, further bridging the gap between theoretical guessing limits and practical cryptographic security.
Summary updated