Tail exponents of conditional guesswork via the method of types

Tail Exponents of Conditional Guesswork via the Method of Types Adway Girish∗ , Andreina Patrizia Motter† , Emre Telatar∗ ∗

arXiv:2608.17949v1 [cs.IT] 18 Aug 2026

School of Computer and Communication Sciences, EPFL, Switzerland † Federal Department of Foreign Affairs, Switzerland adway.girish@epfl.ch, andreina.motter@alumni.epfl.ch, emre.telatar@epfl.ch

August 19, 2026

Abstract We study the problem of guessing a realization of an i.i.d. random sequence given elementwise 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.

1

Introduction

Consider the problem of guessing a realization of a finite-alphabet random variable, first studied by Massey [Mas94]: X is generated according to a probability distribution PX , and the guesser is allowed to ask questions of the form “Is X = x?” for different choices of x, until they correctly guess the realization X. The goal is to do so with “as few guesses as possible”. If PX is known, the optimal strategy is to guess symbols in decreasing order of their probability. Let G(x) denote the “guesswork”, i.e., the number of attempts needed to correctly guess x. If the guesser also has access to side-information Y that is correlated with X, then the optimal strategy is to guess symbols in decreasing order of their conditional probability, and let G(x|y) denote the (conditional) guesswork for x on observing y. When referring to guesswork in the remainder of the paper, we always consider the optimal strategy of guessing symbols from most likely to least likely. Guesswork is a natural operational quantity in settings where one gets an immediate binary “yes”/“no” feedback, such as brute-force password guessing [SHBCM19; SHBCM20; BHL19], guessing-noise decoding [DLM18], computing lower bounds to the computational effort of sequential decoding (via an oracle that provides immediate feedback) [Ari96], and so on. Now suppose that the object to be guessed is an n-length sequence X that is correlated with side-information Y available to the guesser, where the entries (Xi , Yi ) are generated i.i.d. from a distribution PXY . Then the guesswork grows exponentially in n, and Arikan [Ari96] characterized the exponent of the moment E[G(X|Y )ρ ] in terms of the conditional Rényi entropy of order 1/(1+ρ). A natural quantity to study is therefore the tail probabilities of the guesswork, in particular, for what values of h the quantities Pr{G(X|Y ) < 2nh } and Pr{G(X|Y ) > 2nh } decay exponentially in n → ∞ and with what exponent.

1

Such large-deviation results have been explored previously in the literature. Christiansen and Duffy [CD13] showed for X not necessarily i.i.d., that n−1 log G(X), without side-information, satisfies a large-deviations principle (LDP). However, it requires an assumption on the scaled cumulant generating function (sCGF) that clearly holds for i.i.d. sources, but is hard to verify in general. For i.i.d. X, Beirami et al. [BCC+15; BCCDM19] explicitly characterized the exponents of Pr{G(X) ≷ 2nh } as a function of h, in terms of information-theoretic quantities involving “tilted” distributions. To do so, they developed a theory of “weakly typical tilted sets” that requires several technical results. A similar LDP for the conditional case with general sources was established by Li [Li19], but again with an assumption on the sCGF similar to Christiansen and Duffy [CD13], that is hard to verify for non-i.i.d. sources. Moreover, even for i.i.d. sources, the resulting rate function is not explicitly evaluated as Beirami et al. [BCC+15; BCCDM19] do for the unconditional case. In this paper, we consider i.i.d. sources and explicitly derive the exponents of Pr{G(X|Y ) ≷ 2nh } as a function of h using the method of types. In addition to giving a short and direct proof, this gives the exponent immediately as the solution to an entropy-constrained divergence minimization problem and makes clear which empirical distributions of (X, Y ) contribute the most to the tail event. Finally, since the argument uses explicit type-class bounds, it can also be used to obtain finite-n upper and lower bounds to the probability that match up to polynomial factors in n without requiring approximation arguments, unlike the large-deviations machinery which only yields asymptotic limits [CD13; BCCDM19; Li19] (we do not provide these bounds here to keep our presentation concise). We illustrate the use of these explicit characterizations through an application to brute-force password guessing with side-information.

2

Preliminaries

For completeness, we first provide a review of our main technical tool, the method of types [CK11; Csi98]. We then introduce the technical aspects of the guessing problem and define an “order” on these types, which will prove useful for the analysis in Section 3.

2.1

Notation

All logarithms and exponents are taken to base 2, i.e., we write a = 2b as a = exp(b) and b = log(a). We use calligraphic letters X , Y to denote finite sets. Given X of cardinality |X |, let P(X ) denote the set of all probability distributions on X . When X is a random variable taking values on X with distribution P ∈ P(X ), we use X and P interchangeably in expressions Pinvolving information measures. The entropy of X ∼ P is denoted by H(P ) = H(X) = − x P (x) log P
(x). For P distributions P, Q ∈ P(X ), the KL divergence is D(Q∥P ) = x Q(x) log Q(x)/P (x) and the cross entropy is H(Q∥P ) = H(Q) + D(Q∥P ). Given a joint distribution PXY ∈ P(X × Y), we also P define the conditional entropy H(X | Y ) = − x,y PXY (x, y) log PX|Y (x|y), which we also denote as HPXY (X | Y ) to make the joint distribution clear.
the P Also given a distribution QXY , we define conditional KL divergence D(QX|Y ∥PX|Y |QY ) = x,y QXY (x, y) log QX|Y (x|y)/PX|Y (x|y) , and the conditional cross entropy H(QX|Y ∥PX|Y |QY ) = HQXY (X|Y ) + D(QX|Y ∥PX|Y |QY ). We may drop subscripts to simplify notation when the distribution is clear from context. We use boldface letters to denote n-length vectors, such as x ∈ X n , which has components x1 , . . . , xn . We use supp(P ) to denote the support of a distribution. Given a distribution P on X and λ > 0, we define the tilted distribution P (λ) as P (x)λ P (λ) (x) = P . ′ λ x′ P (x )

2

(λ)

Similarly, given a conditional distribution PX|Y and λ > 0, the conditional tilted distribution PX|Y is given by PX|Y (x | y)λ (λ) PX|Y (x | y) = P . ′ λ x′ PX|Y (x | y)

2.2

Method of types

Given a sequence x ∈ X n , denote the type of x by the probability distribution Qx ∈ P(X ) with Qx (a) equal to the relative frequency of a ∈ X among x1 , . . . , xn . Let Pn (X ) denote the set of all n-types, i.e., types of n-length sequences. The number of n-types is at most (n + 1)|X | . Given a probability distribution P ∈ P(X ), let TPn := {x ∈ X n : Qx = P } denote the type class, the set of all . n-length sequences of type P . The cardinality of the type class is bounded as |TPn | = exp(n H(P )), . where = means that the left and right-hand sides are equal up to polynomial factors in n. For X generated i.i.d. according to P , we have Pr{X = x} = exp[−n H(Qx ∥P )]. Similarly define the joint type Qxy ∈ P(X × Y) and for a distribution PXY ∈ P(X × Y), define the joint type class TPnXY . Given y ∈ Y n and a conditional distribution V , define the conditional type class to be TVn (y) := {x ∈ X n : (x, y) ∈ TQny V }. The cardinality of the conditional type class . is bounded as |TPnX|Y (y)| = exp(n H(X|Y )), where the conditional entropy H(X|Y ) is computed according to the joint distribution induced by the type Qy and PX|Y . For X generated from y conditionally independently according to the conditional distribution PX|Y , we have Pr{X = x | Y = y} = exp[−n H(Qx|y ∥PX|Y |Qy )] where Qx|y is the conditional type induced by (x, y), given by Qx|y (x|y) = Qxy (x, y)/Qy (y).

2.3

Guessing and orders on types

Suppose that the object to be guessed is X = X1 , . . . , Xn generated i.i.d. from a distribution P ∈ P(X ). Then, we guess x ∈ X n before x′ if PX (x) ≥ PX (x′ ), with ties broken arbitrarily. Note that PX (x) = exp[−n H(Qx ∥P )], and hence, define the total order ⪰ between types as Q ⪰ Q′ to mean H(Q∥P ) ≤ H(Q′ ∥P ), i.e., X

[Q(x) − Q′ (x)] log

x

1 ≤ 0. P (x)

Similarly, define the strict order ≻ if the above inequality is strict. Note that ≻ and ⪰ depend on P . The optimal guessing strategy is to go through types in decreasing order (picking arbitrarily among Q and Q′ if H(Q∥P ) = H(Q′ ∥P )) and guessing sequences within each type arbitrarily. Recall that G(x) denotes the number of guesses needed (guesswork) to correctly guess x with this strategy. Now consider a conditional version of the problem, where we have access to Y that is correlated element-wise with X, i.e., (Xi , Yi ) is generated i.i.d. from a distribution PXY ∈ P(X × Y). Having observed y, we guess x before x′ if PX|Y (x|y) ≥ PX|Y (x′ |y). Note that PX|Y (x|y) = exp[−n H(QX|Y ∥PX|Y | Qy )], and hence, we define the total order between conditional types as QX|Y ⪰ Q′X|Y to mean H(QX|Y ∥PX|Y | Qy ) ≤ H(Q′X|Y ∥PX|Y | Qy ), i.e., X

[QXY (x, y) − Q′XY (x, y)] log

x,y

1 ≤ 0, PX|Y (x|y)

where QXY (x, y) = QX|Y (x|y)Qy (y) is the joint distribution induced by the conditional type QX|Y and the type Qy . Also define the strict order similarly, and note that ≻ and ⪰ depend on PX|Y and Qy . This order on conditional types also induces a partial order on joint types in the following 3

way: we write QXY ⪰ Q′XY to mean that they have the same Y -marginals, i.e., QY = Q′Y , and their conditional types satisfy QX|Y ⪰ Q′X|Y . Recall that G(x|y) denotes the guesswork to correctly guess x having observed y with the optimal strategy, i.e., guessing sequences from type Q before Q′ if Q ⪰ Q′ .

3

Tail exponents of guesswork

For a pair (X, Y ) with entries (Xi , Yi ) generated i.i.d. from a distribution PXY ∈ P(X × Y), we are interested in the tail exponents of conditionally guessing X from Y , i.e., := lim − n1 log Pr{G(X|Y ) ≷ 2nh }, e≷ X|Y (h) n→∞

(1)

where ≷ can be either > or <. Also suppose without loss of generality that PX and PY have full support. In addition, we assume that PX and each PX|Y (·|y) have unique maximizers. Analogous results can be obtained even without this assumption, but this simplifies the presentation of our results. The unconditional version of this problem, i.e., the exponents of Pr{G(X) ≷ 2nh }, was explicitly characterized by Beirami et al. [BCCDM19]. We first recover their result directly using a simple type-counting argument, which is well-suited when the sets are finite and the distribution is i.i.d., as in our setting (and indeed, also the setting that Beirami et al. [BCCDM19] consider) and then apply the same approach to conditional guesswork. Li [Li19] similarly to [BCCDM19] established a general LDP for conditional guesswork, but did not explicitly derive the exponent in the i.i.d. case as we do below. Our type-counting proof strategy is to explicitly evaluate the probability that X ∼ P i.i.d. occurs in the 2nh sequences with the highest probability. Since the probability of such an X only depends on its type Q, this is the same as checking that Q is such that the total number of sequences among all types Q′ ≻ Q is smaller or greater than 2nh . Finally, since the number of types is polynomial in n, the exponent of the probability is determined by the type Q satisfying the above . constraint that has the smallest D(Q∥P ) (recall that Pr{X ∈ TQn } = exp(−n D(Q∥P ))). To solve the resulting optimization problem, we show that the solution is unchanged if we instead consider a relaxed version of the same problem, whose solution is easily computed to be the tilted distribution P (λh ) with tilting parameter λh such that H(P (λh ) ) = h. Thus, the tilted distribution is exactly the type whose corresponding type class has the largest probability among all types that appear in the first 2nh guesses. Proposition 1 (Unconditional guesswork exponent). Let h ∈ (0, log |X |). Then, the exponents 1 nh e≷ X (h) := limn→∞ − n log Pr{G(X) ≷ 2 } are respectively given by (λh ) e≷ ∥ P ) · 1{h ≷ H(P )}, X (h) = D(P

where ≷ is either > or < and λh is such that H(P (λh ) ) = h in both cases. Proof. Note that the number of guesses G(x) can be upper and lower bounded as X X |TQn′ | =: u(Qx ). ℓ(Qx ) := |TQn′ | ≤ G(x) ≤ Q′ ⪰Qx

Q′ ≻Qx

. Then, up to polynomial factors in n, we have, for Q ∈ Pn (X ), ℓ(Q) = exp[n maxQ′ ≻Q H(Q′ )] and . . u(Q) = exp[n maxQ′ ⪰Q H(Q′ )]. Further, the probability that X has type Q is Pr{X ∈ TQn } = 4

exp[−n D(Q∥P )]. Since we are interested in the regime when n → ∞, note that for ℓ(Q), the maximum over the Q′ ’s satisfying the strict inequality becomes a supremum in the limit, with the maximum attained in the closure, i.e., allowing Q′ ⪰ Q, and hence the exponents of both ℓ(Q) and u(Q) are maxQ′ ⪰Q H(Q′ ). Putting these together, we have that the exponent e> X (h) is determined by the type Q that has the smallest D(Q∥P ) while satisfying maxQ′ ⪰Q H(Q′ ) ≥ h (and similarly for e< X (h) and ′ ′ maxQ ⪰Q H(Q ) ≤ h), i.e., e≷ min D(Q ∥ P ), X (h) = Q:maxQ′ ⪰Q H(Q′ )⋛h

where Q, Q′ ∈ P(X ) and ⋛ is ≥ or ≤ accordingly when ≷ is > or <. In both cases, we show that the above optimization problem is respectively equivalent to the simpler problem E ≷ (h) :=

min

D(Q ∥ P ).

Q:H(Q)⋛h ≷ ≷ (λh ) ∥P ) · 1{h ≷ We will show that e≷ X (h) = E (h), but we first show that E (h) is equal to D(P H(P )}, as desired. Clearly, if H(P ) ≤ h, then E < (h) = 0, and if H(P ) ≥ h, then E > (h) = 0, as Q = P is feasible. We first consider E > (h) = minQ:H(Q)≥h D(Q∥P ) and suppose h > H(P ). Then, we claim that the solution lies on the boundary {Q : H(Q) = h}. To see why this is true, suppose the minimizer Q∗ has H(Q∗ ) > h, and consider Qt = (1 − t)Q∗ + tP for t ∈ (0, 1). Then, by the convexity of divergence, D(Qt ∥P ) ≤ (1 − t)D(Q∗ ∥P ) < D(Q∗ ∥P ). Meanwhile, for sufficiently small t > 0, we still have H(Qt ) > h as the entropy is continuous on finite sets, which contradicts the optimality of Q∗ . Hence, Q∗ must satisfy H(Q∗ ) = h. A completely identical argument also shows that the minimizer in E < (h) for h < H(P ) also lies on the boundary {Q : H(Q) = h}. Hence, it is enough to solve minQ:H(Q)=h D(Q∥P ). We claim that the minimizer is Q = P (λh ) , where λh is such that H(P (λh ) ) = h. Clearly, P (λh ) satisfies the constraint. It is enough to show that D(Q∥P ) ≥ D(P (λh ) ∥P ) for all Q with H(Q) = h. Consider the difference D(Q∥P ) − D(P (λh ) ∥P ) = H(Q∥P ) − H(P (λh ) ∥P )  X 1 . = Q(x) − P (λh ) (x) log P (x) x

Also consider the divergence D(Q∥P (λh ) ) = H(Q∥P (λh ) ) − H(Q), and since H(P (λh ) ) = H(Q), we have that D(Q∥P (λh ) ) = H(Q∥P (λh ) ) − H(P (λh ) )  X = Q(x) − P (λh ) (x) log x

1 P (λh ) (x)

= λh [D(Q∥P ) − D(P (λh ) ∥P )], from the above. Hence, D(Q∥P )−D(P (λh ) ∥P ) ≥ 0, and we have that P (λh ) is the desired minimizer. (We could have also used Lagrange multipliers to arrive at the same minimizer.) To complete the ≷ proof, it remains to show that e≷ X (h) = E (h). > First consider eX (h) = minQ:maxQ′ ⪰Q H(Q′ )≥h D(Q∥P ). Suppose, for a fixed Q with maxQ′ ⪰Q H(Q′ ) ≥ h, that Q̃ (which depends on Q) is a maximizer of maxQ′ ⪰Q H(Q′ ). Then we have H(Q̃) ≥ H(Q) and H(Q̃) ≥ h, as Q̃ is the maximizer, and H(Q̃)+D(Q̃∥P ) ≤ H(Q)+D(Q∥P ), as Q̃ ⪰ Q. Together, this implies that D(Q̃∥P ) ≤ D(Q∥P ).

5

Hence, for every Q that is feasible in the original problem (satisfying maxQ′ ⪰Q H(Q′ ) ≥ h), we have a Q̃ that satisfies D(Q̃∥P ) ≤ D(Q∥P ) and H(Q̃) ≥ h, i.e., e> X (h) ≥

min

D(Q∥P ) = E > (h).

Q:H(Q)≥h

On the other hand, note that Q with H(Q) ≥ h also necessarily satisfies maxQ′ ⪰Q H(Q′ ) ≥ h, and hence, the reverse inequality, and consequently equality, holds. < < Now consider e< X (h) = minQ:maxQ′ ⪰Q H(Q′ )≤h D(Q∥P ). Note that we have E (h) ≤ eX (h) in general, as Q with maxQ′ ⪰Q H(Q′ ) ≤ h also satisfies H(Q) ≤ h. Hence, if we can show that the minimizer Q∗ of the relaxed problem minQ:H(Q)≤h D(Q∥P ) satisfies the original constraint maxQ′ ⪰Q∗ H(Q′ ) ≤ h, then we are done. If h ≥ H(P ), then Q∗ = P , and for any Q′ ⪰ Q∗ , H(Q′ ) ≤ H(Q′ ) + D(Q′ ∥P ) ≤ H(Q∗ ) + D(Q∗ ∥P ), which is equal to H(P ) ≤ h, and hence, maxQ′ ⪰Q∗ H(Q′ ) ≤ h. On the other hand, for h < H(P ), then Q∗ = P (λh ) with H(Q∗ ) = h. Note that maxQ′ ⪰P (λ) H(Q′ ) for λ > 0 involves maximizing a concave function subject to a linear constraint. Solving this via Lagrange multipliers yields the maximizer to be exactly P (λ) , and hence, maxQ′ ⪰Q∗ H(Q′ ) = H(P (λh ) ) = h, and we are done. Remark 1. One way to get an easy upper bound to Pr{G(X) > 2nh } is to use Arikan’s bound [Ari96] n(1+ρ) P 1 1+ρ for ρ > 0, together with Markov’s on the moments of G(X), i.e., E[G(X)ρ ] ≤ P (x) x inequality Pr{G(X) > 2nh } ≤ 2−nhρ E[G(X)ρ ]. Optimizing over the choice of ρ gives the best bound at ρ = 1/λh − 1, with λh ∈ (0, 1) as above (which is possible if h > H(P )), and the exponent is exactly D(P (λh ) ∥P ). One might naively expect a conditional version of the above statement to follow immediately by simply replacing P by PX|Y , but it is easy to see that this is not the case, as the Xi are not identically distributed given Y = y. Indeed, Xi has distribution PX|Y (·|yi ) given Y = y. Nonetheless, by repeating the type-counting argument above with correct order on conditional types, we can compute the tail exponents of conditional guesswork. We compute two such conditional exponents, namely that of Pr{G(X|Y ) ≷ 2nh | Y = y} for y’s whose type converges to a limit in Theorem 1, and Pr{G(X|Y ) ≷ 2nh } averaged over Y in Theorem 2. Theorem 1 (Conditional guesswork exponent for given y-type). Let h ∈  P (n) (n) 0, y Q(y) log | supp(PX|Y (·|y))| and Q ∈ P(Y). Then, for y such that the type Qy → Q, := limn→∞ − n1 log Pr{G(X|Y ) ≷ 2nh | Y = y (n) } are respectively given the exponents e≷ X|Y (h, Q) by (λh,Q ) e≷ X|Y (h, Q) = D(PX|Y ∥PX|Y |Q) · 1{h ≷ HQPX|Y (X|Y )}, where ≷ is either > or < and λh,Q is such that H

(λ

h,Q QPX|Y

)

(X|Y ) = h in both cases.

Proof sketch. The proof follows identically to that of Proposition 1, except that we replace the initial bounds on G(x|y) by terms involving conditional distributions and conditional type classes, i.e., for x ∈ TQnX|Y (y), we have ℓ(QX|Y , y) ≤ G(x|y) ≤ u(QX|Y , y), 6

P where ℓ(V, y) := V ′ ≻V |TVn′ (y)| and u(V, y) is identical with ≻ replaced by ⪰, with both V, V ′ . being conditional types. As before, we have ℓ(V, y) = exp[n maxV ′ ≻V HQy V ′ (X|Y )], and u(V, y) is identical with ⪰ instead of ≻. Together with the probability of X having conditional type V given Y = y being Pr{X ∈ . n TV (y) | Y = y} = exp[−n D(V ∥PX|Y |Qy )], we have that the exponent is e≷ X|Y (h, Q) =

min V :maxV ′ ⪰V HQV ′ (X|Y )⋛h

D(V ∥ PX|Y | Q)

with V, V ′ going over all conditional types on X from Y. By a completely analogous reasoning to the unconditional case, we claim that the minimization problem is unchanged if we relax the constraint on the conditional type V to simply HQV (X|Y ) ⋛ h. The solution to this simpler problem occurs < at V = PX|Y for e> X|Y (h, Q) if HQPX|Y (X|Y ) ≥ h and for eX|Y (h, Q) if HQPX|Y (X|Y ) ≤ h. On the (λ

)

< other hand, the solution is at V = PX|Yh,Q for e> X|Y (h, Q) if HQPX|Y (X|Y ) < h and for eX|Y (h, Q) if HQPX|Y (X|Y ) > h. Note that the tilted distribution here is the conditional tilted distribution, which is obtained by tilting PX|Y (·|y) with parameter λh,Q for each y.
Theorem 2 (Conditional guesswork exponent). Let h ∈ 0, maxy log | supp(PX|Y (·|y))| . For λ > 0, define
P λ 1/λ PY (y) x PX|Y (x|y) (2) QY,λ (y) := P
. P ′ |y ′ )λ 1/λ ′) P (x P (y ′ ′ Y X|Y x y

Then, the exponents of Pr{G(X|Y ) ≷ 2nh } as defined in (1) are respectively given by (λ )

h e≷ X|Y (h) = D(QY,λh PX|Y ∥ PXY ) · 1{h ≷ H(X | Y )},

where ≷ is either > or < and λh is such that H

(λ )

h QY,λh PX|Y

(X | Y ) = h in both cases.

Remark 2. Before proceeding to the proof, it is worth noting that if PX|Y is symmetric in the P λh is a constant for all y, then Q sense that Y,λh = PY , and the exponents are x PX|Y (x|y) (λ )

(λ )

D(PY PX|Yh ∥PXY ) = D(PX|Yh ∥PX|Y |PY ) which is equal to the conditional exponent e≷ X|Y (h, PY ). Proof sketch. We follow the same procedure as in the proof of Proposition 1, except that we go over joint types Qxy to compute the probability instead of types on X only. Recall that the (partial) order on joint types is defined so that QXY ⪰ Q′XY means that QY = Q′Y and QX|Y ⪰ Q′X|Y . By following the same steps as earlier, we have that the exponent is e≷ X|Y (h) =

D(Q ∥ PXY ),

min Q:maxQ′ ⪰Q HQ′ (X|Y )⋛h

where Q, Q′ ∈ P(X × Y) are joint distributions, and ⋛ is ≥ when ≷ is > and ≤ when ≷ is <. By the same reasoning as in the unconditional case, this minimization problem is unchanged if we simplify the constraint to HQ (X|Y ) ⋛ h, i.e., e≷ X|Y (h) =

min

D(Q ∥ PXY ).

Q:HQ (X|Y )⋛h

Clearly, if H(X|Y ) ⋛ h, then Q = PXY is feasible and the exponent is 0. Hence, it remains to solve min D(Q ∥ PXY ) Q:HQ (X|Y )=h

7

in the non-trivial case h ≷ H(X|Y ). We can solve this using Lagrange multipliers to obtain that the (λ ) optimizer is of the form Q(x, y) = Q(y)V (x|y) where V is the conditional tilted distribution PX|Yh
P λh 1/λh , where λ is such that the conditional entropy H(X|Y ) and Q(y) ∝ PY (y) h x PX|Y (x|y) with this Q is h. Remark 3. A more illustrative proof of Theorem 2 can perhaps be obtained using Theorem 1 by simply averaging over Y = y, as Pr{G(X|Y ) ≷ 2nh } X = PY (y) Pr{G(X|Y ) ≷ 2nh |Y = y}. y

Since the terms in the sum only depend on the type of y, we can sum over all possible types Q ∈ Pn (Y) instead, with each type having exponent D(Q∥PY ) + e≷ X|Y (h, Q) = (λ

)

(λ

)

D(Q∥PY ) + D(PX|Yh,Q ∥PX|Y | Q) = D(QPX|Yh,Q ∥PXY ), where λh,Q satisfies H

(λ

h,Q QPX|Y

)

(X|Y ) = h as before. Hence, the averaged conditional exponent is

e≷ X|Y (h) = min

Q∈P(Y)

h

i D(Q∥PY ) + e≷ (h, Q) , X|Y

However, there does not seem to be an easier way to see that this exponent is minimized at Q = QY,λh as in (2), other than resorting to Lagrange multipliers. Further, note that for the averaged conditional exponent in Theorem 2, it is not a tilted joint (λ) distribution PXY for some appropriate λ that determines the exponent, but rather, the joint distri(λ ) bution induced by the conditional tilted distribution PX|Yh together with some marginal distribution QY,λh . Thus, the important geodesic here is the family of conditional tilted distributions, similar to the tilted distributions in the unconditional case (Proposition 1). Remark 4. Note that the moment characterization tells us that E[G(X|Y )] grows exponentially in n with the exponent related to the Rényi entropy of order 1/2. Nonetheless, in the results above, we see that it is the Shannon entropy (which is the Rényi entropy of order 1) that marks the transition point: Pr{G(X|Y ) < 2nh } goes to 0 if h < H(X|Y ) and goes to 1 otherwise. This is not surprising, as it can be shown that limn→∞ n1 E[log G(X|Y )] = H(X|Y ) (for example, by taking ρ → 0 in the moment characterization).

4

Application to password guessing

We now use Theorem 2 to obtain a quantitative estimate for a natural problem in security. Suppose we have a password X that is an n-length string generated i.i.d. from distribution PX , and suppose an attacker observes side-information Y through a memoryless channel P Y |X . For example, PX is P −s a Zipf law [WCWHJ17] on an alphabet {1, . . . , m}, i.e., PX (x) = x / x′ x′−s with s > 0, and PY |X is an m-ary erasure channel, i.e, PY |X (y|x) = 1 − ϵ for y = x and ϵ for y equal to a special “erasure” symbol not in X . If our system is such that it allows a small, finite number of attempts at entering the password before locking out the user, then we wish to ensure that the attacker is, with high probability, unable to guess the password in a constant number of attempts. For δ → 0, if we choose n ≳ log 1δ /e< X|Y (η), then, we have that Pr{G(X|Y ) < tn } < δ for tn that grows slower

8

(λ )

η than 2nη for η > 0. Note that e< X|Y (η) = D(QY,λη PX|Y ∥PXY ), where λη → ∞ as η → 0. Assuming that maxx PX|Y (x|y) is unique, we can check that

η→0

e< X|Y (η) −→ − log

! X

PY (y) max PX|Y (x|y) , x

y

which is exactly the conditional min-entropy [KRS09]. For the Zipf source erasure channel setP and −s ). To give a concrete ting considered above, this expression evaluates to − log ((1 − ϵ) + ϵ/ m i i=1 example, let δ = 10−6 , s = 0.8, m = 100 and ϵ = 0.5, then this exponent is approximately 0.83. We need n ≳ log(1/δ) ≈ 24 to ensure that even if around half of the (i.i.d.) characters in the password 0.83 are leaked, the attacker can succeed in guessing the right password in a small number of attempts only with probability 10−6 .

5

Conclusion

We give a simple method-of-types derivation of the tail exponents of conditional guesswork for i.i.d. sources. The exponent is characterized as the solution to an entropy-constrained divergence minimization problem, which yields a divergence involving conditional tilted distributions. This lets us easily compute the exponent for use in applications, as we illustrate in a password guessing example. Though our results only show asymptotic exponents, the method-of-types derivation can also give upper and lower bounds to the probability that match up to polynomial factors in n. Another possible application is the analysis of guessing-based decoding [DLM18; DMA22; DAM22; MY25; LZ26], where we are interested in quantifying the probability that the true noise sequence is not reached within a prescribed number of guesses.

References [Ari96]

Erdal Arikan. “An inequality on guessing and its application to sequential decoding”. In: IEEE Transactions on Information Theory 42.1 (1996), pp. 99–105 (cit. on pp. 1, 6).

[BCC+15]

Ahmad Beirami, Robert Calderbank, Mark Christiansen, Ken Duffy, Ali Makhdoumi, and Muriel Médard. “A geometric perspective on guesswork”. In: 53rd Annual Allerton Conference on Communication, Control, and Computing (Allerton). 2015, pp. 941–948 (cit. on p. 2).

[BCCDM19]

Ahmad Beirami, Robert Calderbank, Mark M. Christiansen, Ken R. Duffy, and Muriel Médard. “A characterization of guesswork on swiftly tilting curves”. In: IEEE Transactions on Information Theory 65.5 (2019), pp. 2850–2871 (cit. on pp. 2, 4).

[BHL19]

Annina Bracher, Eran Hof, and Amos Lapidoth. “Guessing attacks on distributedstorage systems”. In: IEEE Transactions on Information Theory 65.11 (2019), pp. 6975–6998 (cit. on p. 1).

[CD13]

Mark M. Christiansen and Ken R. Duffy. “Guesswork, large deviations, and Shannon entropy”. In: IEEE Transactions on Information Theory 59.2 (2013), pp. 796–802 (cit. on p. 2).

[CK11]

Imre Csiszár and János Körner. Information theory: coding theorems for discrete memoryless systems. Cambridge University Press, 2011 (cit. on p. 2). 9

[Csi98]

Imre Csiszár. “The method of types”. In: IEEE Transactions on Information Theory 44.6 (1998), pp. 2505–2523 (cit. on p. 2).

[DAM22]

Ken R. Duffy, Wei An, and Muriel Médard. “Ordered reliability bits guessing random additive noise decoding”. In: IEEE Transactions on Signal Processing 70 (2022), pp. 4528–4542 (cit. on p. 9).

[DLM18]

Ken R. Duffy, Jiange Li, and Muriel Médard. “Guessing noise, not code-words”. In: Proc. IEEE International Symposium on Information Theory (ISIT). 2018, pp. 671– 675 (cit. on pp. 1, 9).

[DMA22]

Ken R. Duffy, Muriel Médard, and Wei An. “Guessing random additive noise decoding with symbol reliability information (SRGRAND)”. In: IEEE Transactions on Communications 70.1 (2022), pp. 3–18 (cit. on p. 9).

[KRS09]

Robert Konig, Renato Renner, and Christian Schaffner. “The operational meaning of min- and max-entropy”. In: IEEE Transactions on Information Theory 55.9 (2009), pp. 4337–4347 (cit. on p. 9).

[Li19]

Jiange Li. “Large deviations for conditional guesswork”. In: Statistics and Probability Letters 153 (2019), pp. 7–14 (cit. on pp. 2, 4).

[LZ26]

Zhuang Li and Wenyi Zhang. “A finite-blocklength analysis for ORBGRAND”. In: arXiv preprint arXiv:2603.07526 (2026) (cit. on p. 9).

[Mas94]

James L. Massey. “Guessing and entropy”. In: Proc. IEEE International Symposium on Information Theory (ISIT). 1994, p. 204 (cit. on p. 1).

[MY25]

Henrique K. Miyamoto and Sheng Yang. “On universal decoding over discrete additive channels by noise guessing”. In: Proc. IEEE Information Theory Workshop (ITW). 2025, pp. 1–6 (cit. on p. 9).

[SHBCM19]

Salman Salamatian, Wasim Huleihel, Ahmad Beirami, Asaf Cohen, and Muriel Médard. “Why botnets work: Distributed brute-force attacks need no synchronization”. In: IEEE Transactions on Information Forensics and Security 14.9 (2019), pp. 2288– 2299 (cit. on p. 1).

[SHBCM20]

Salman Salamatian, Wasim Huleihel, Ahmad Beirami, Asaf Cohen, and Muriel Médard. “Centralized vs decentralized targeted brute-force attacks: Guessing with side-information”. In: IEEE Transactions on Information Forensics and Security 15 (2020), pp. 3749–3759 (cit. on p. 1).

[WCWHJ17]

Ding Wang, Haibo Cheng, Ping Wang, Xinyi Huang, and Gaopeng Jian. “Zipf’s law in passwords”. In: IEEE Transactions on Information Forensics and Security 12.11 (2017), pp. 2776–2791 (cit. on p. 8).

10

Related documents

• Good guesses as accuracy-specificity tradeoffs#79921
• Characterizing generics are material inference tickets: a proof-theoretic analysis#771104
• On the imprecision of full conditional probabilities#90058
• Probability, Evidential Support, and the Logic of Conditionals#93550
• Consequences of Assigning Non-Measurable Sets Imprecise Probabilities#90181