Strong Chain Rules for Min-Entropy under Few Bits Spoiled
Maciej Skorski














Supported by


































Strong Chain Rules for Min-Entropy under Few Bits Spoiled
    
supported by
Maciej Skórski
IST Austria

Email: mskorski@ist.ac.at


    Accepted .  Received ; in original form 
=========================================================================






It is well established that the notion of min-entropy fails to satisfy the chain rule of the form 
H(X,Y) = H(X|Y)+H(Y), known for Shannon Entropy. 
The lack of a chain rule causes a lot of technical difficulties, particularly in cryptography 
where the chain rule would be a natural way to analyze how min-entropy is split among smaller blocks. Such problems arise
for example when constructing extractors and dispersers.

We show that any sequence of variables exhibits
a very strong strong block-source structure (conditional distributions of blocks are nearly flat) when we spoil few correlated bits.
This implies, conditioned on the spoiled bits, that splitting-recombination properties hold.
In particular, we have many nice properties that min-entropy doesn't obey in general, for example
strong chain rules, “information can't hurt” inequalities, equivalences of average and worst-case conditional entropy definitions 
and others. 

Quantitatively, for any sequence X_1,…,X_t of random variables over an alphabet 𝒳
we prove that, when conditioned on m = t· O( loglog|𝒳| + loglog(1/ϵ) + log t) bits of auxiliary information,
all conditional distributions of the form X_i|X_<i are ϵ-close to be nearly flat (only a constant factor away).
The argument is combinatorial (based on simplex coverings).

This result may be used as a generic tool for exhibiting block-source structures.
We demonstrate this by reproving the fundamental converter due to Nisan and Zuckermann (J. Computer and System Sciences, 1996), 
which shows that sampling blocks from a min-entropy source roughly preserves the entropy rate.
Our bound implies, only by straightforward chain rules, an additive loss of o(1) (for sufficiently many samples), which qualitatively meets 
the first tighter analysis of this problem due to Vadhan (CRYPTO'03), obtained by large deviation techniques.




chain rule, min-entropy, spoiling knowledge, block sources, local extractors





















§ INTRODUCTION





 §.§ Strong vs Weak Entropy Chain Rules

One of the most useful properties of Shannon entropy is the chain rule, 
showing how entropy splits between distributions

    H_1(X|Y) = H(X,Y) - H(Y).

The notion of min-entropy, very important for cryptography <cit.>, fails to satisfy this property <cit.>. 
In the lack of a chain rule, a much weaker one-sided bound (e.g. of the form
H_∞(X|Y) ⩾ H_∞(X)-H_0(Y), where H̃_∞ is an appropriate extension of min-entropy to conditional distributions)
is sometimes used <cit.>, which we address as a weak chain rule[In leakage-resilient cryptography such bounds are simply called chain rules.
In this paper we discuss chain rules in a strong sense.].



 §.§ Need for Strong Chain Rules


While the weak chain rule suffices for many applications related to bounded leakage
 <cit.> (where Y is leakage much shorter than the amount of min-entropy in X),
it is insufficient where one needs to estimate how entropy is distributed among blocks. In these settings,
one would like to argue that (roughly) either X or Y|X has high min-entropy if the joint min-entropy (of (X,Y)) is high. 
Examples of such problems are randomness extraction in the bounded storage model <cit.>, constructions of dispersers <cit.>, 
or oblivious transfer protocols <cit.>.


















 §.§ Our Contribution and Related Works


Although the chain rule fails in general, we show that it is true conditioned on few spoiled bits.
We actually show more, that (locally, conditioned on auxiliary bits) a very strong block-source structure exists. Namely, each block
is nearly flat given previous blocks. Informally, the theorem reads as follows
[Informal: exhibiting flat block-source structures]
For any sequence X=X_1,…,X_t of correlated random variables each over 𝒳 and any ϵ
there exists auxiliary information S of length m bits such that

 
  * S is short: m=t· O(loglog|𝒳|+loglog(1/ϵ) + log t)
 
  * Conditioned on S, conditional block distributions 
[X_i|X_i=x_i,X_i-1=x_i-1,…,X_1=x_1] are nearly flat (ϵ-close to
a probability distribution whose values differ by a constant factor).


The formal statement is given in <Ref>.
For cryptographic applications, loglog(ϵ^-1) is pretty much a small constant (typically ϵ = 2^-100). 
Also, for sources with super-logarithmic entropy per block, that is when H_∞(X) ≫ t loglog|𝒳|),
and the number of blocks t growing not too fast, e.g. t = log^O(1)(|𝒳|), 
the error term is of a smaller order than the entropy. Under these mild assumptions, conditioned on the partition generated
by auxiliary bits, we conclude
many nice properties that fail in general. Examples are chain rules, “conditioning only decreases entropy” properties,
equivalences of conditional entropy defined in different ways and others.


 



  §.§.§ Our Tools




  
Spoiling Knowledge
The spoiling knowledge technique is essentially about finding auxiliary information that increases entropy, and
was introduced in <cit.>. We use the same idea to force block distributions to be nearly flat.




  
Covering techniques (combinatorial geometry)
In order to construct a good “spoiling”, we consider the logarithm of the chaining identity 
p_X_1… X_t(·) = ∏_j=1^tp_X_i|X_i-1… X_1(·) which 
represents the “surprise” of the total distribution as a sum of “next-block surprises”
of the form r_i(·) = -log p_X_i|X_i-1… X_1(·). It follows
that the vector of all r_i (for i=1,…,t) lie in a (t-1)-dimensional simplex
of edge roughly O(tlog|𝒳|). Our partition is obtained from coverings, as 
for all x in the same part r_i(·) is roughly constant (when the radius is small enough).
This approach can be likely optimized (we use a crude bound on the covering number). Also the lower bounds on the necessary number of spoiled buts are possible, by considering packings instead of coverings.
We defer this discussion to the full version.










 §.§ Related works

As far as we know, the presented result on spoiling min-entropy is knew.
The Nisan-Zuckerman lemma, discussed in this paper as an application,
was analyzed by Vadhan <cit.> and recently by Bellare <cit.>. 
These results study min-entropy present in random chunks of a larger source,
and don't offer tools for splitting entropy in any source deterministically (particularly for a small number of blocks),
as we do.







 §.§ Applications


The important result due to Nisan and Zuckerman <cit.>, improved later by Vadhan <cit.> 
states that sampling from a given source of high min-entropy rate α yields
a source of a comparable entropy rate β. This fact is a crucial step in constructions
of so called local extractors, that extract randomness parsing only a part of input. 
For a while, only a lossy bound β≈α/log(1/α) was known.
The reason was precisely the lack of a chain rule for min-entropy.
As observed by Cachin <cit.> the proof for Shannon entropy (a less interesting case) is straightforward and follows basically by a splitting-recombining argument, which uses a chain rule in both directions.
We demonstrate by our technique that (surprisingly) a very effective splitting-recombining approach actually works,
and achieves β = α- o(1) in a very straightforward way. This matches the bound due to Vadhan.
Concretely, if the original source is a sequence of t blocks over an alphabet 𝒳 and we take ℓ samples, then
β = α - err_𝖲𝗉𝗈𝗂𝗅  -err_𝖲𝖺𝗆𝗉
where the losses due to chain rules and sampling equal, respectively 

    err_𝖲𝗉𝗈𝗂𝗅   = O(loglog|𝒳|+loglog(1/ϵ)+log t)/log|𝒳| 
     
    err_𝖲𝖺𝗆𝗉   = O(√(ℓ^-1log(1/ϵ))).

In particular β converges to α when the block length is log|𝒳| = log^ω(1)(1/ϵ) and 
log |𝒳| = ω(1)· t.
For more details see <Ref> in <Ref>.
For the discussed result our bounds converge slightly slower than Vadhan's bounds derived by large deviation techniques.
However, our spoiling technique can be used also for small number of samples.




 §.§ Organization


In <Ref> we explain necessary notions and notations. Auxiliary facts that will be needed are discussed
in <Ref>. In <Ref> we prove the main result.
Applications to the bounded storage model are discussed in <Ref>. 
We conclude the work in <Ref>.



§ PRELIMINARIES




 §.§ Basic Notation

For any random variables X_1,X_2 by p_X_1|X_2 we denote the distribution of X_1 conditioned on X_2, that is
 p_X_1|X_2(x_1,x_2) = [X_1=x_1|X_2=x_2]. 
 Throughout this paper, all logarithms are taken to base 2.
 For any sequence of random variables X = X_1,…,X_n
we denote X_<i=X_1,…,X_i-1,  X_⩽ i=X_1,…,X_i
and more generally for any subset I⊂{1,…,n} we put X_I = X_i_1X_i_2… X_i_m-1X_i_m where i_1<i_2<… <i_m are all elements of I.



 §.§ Distances, Entropies

In the definitions below 𝒳 is an arbitrary finite set.

For two random variables X,Y on 𝒳 by
the statistical distance (total variation) we mean

    d_TV(X;Y) = 1/2∑_x∈𝒳| [X=x] - [Y=x]|












The Shannon entropy of a random variable X on 𝒳 equals

    H_1(X) = -∑_x[X=x]log[X=x].


 


The min-entropy of a random variable X on 𝒳 equals

    H_∞(X) = -logmax_x∈𝒳[X=x].




Let X,Y be random variables over 𝒳 and 𝒴 respectively.
The worst-case min-entropy of X conditioned on Y equals

    H_∞(X|Y) = min_y∈𝒴 H_∞(X|Y=y).

The average min-entropy of X conditioned on Y equals

    H_∞(X|Y) = -log(𝔼_y Y 2^-H_∞(X|Y=y)).



The averaged notion is slightly weaker, but has better properties and actually better suits applications <cit.>.

The notion of smooth entropy is more accurate than min-entropy because quantifies entropy up to small perturbations in the probability mass.

The ϵ-smooth min-entropy of a random variable X on 𝒳 is defined as

    H_∞^ϵ(X)  = max_X': d_TV(X,X')⩽ϵ H_∞(X')

where the maximum is over all random variables X' on 𝒳. In other words, X has at least k bits of smooth min-entropy
if there is X' of min-entropy at least k and ϵ-close to X.
















 §.§ Randomness Extractors


Below we recall the definition of seeded extractors

We say that a function 𝖤𝗑𝗍:{0,1}^n×{0,1}^d →{0,1}^m
is a (k,ϵ)-extractor if and only if

    d_TV(𝖤𝗑𝗍(X,U_d),U_d ; U_m,U_d) ⩽ϵ

for any X on {0,1}^n with min-entropy at least k.






 §.§ Samplers


Averaging samplers are procedures which sample points, within a given domain, that are distributed enough random to 
approximate every function. It turns out that there exist good averaging samples, using
much less auxiliary randomness than necessary to generate independent points.
For our applications we consider samplers that approximate averages from below.

A function 𝖲𝖺𝗆𝗉:{0,1}^d → [t]^ℓ is a (μ,θ,γ)-averaging sampler if for every function f:[t]→ [0,1]
with average value 1/ℓ∑_i=1^ℓf(i) ⩾μ it holds that

    _i_1,…,i_ℓ𝖲𝖺𝗆𝗉(U_r)[ 1/ℓ∑_i=1^ℓf(i) ⩾μ - θ] ⩽ 1-γ.




For the setting in <Ref>
there is an averaging sampler which for any ℓ' such that
Ω(μθ^-2log(1/γ) ) ⩽ℓ' ⩽ℓ
produces ℓ' distinct samples and uses
d = log(t/ℓ') + log(1/γ) + 2log(μ/θ) + loglog(1/μ)+O(1) random bits.






§ AUXILIARY LEMMAS


The following lemma is essentially the information can't hurt principle, well known for Shannon entropy, stated for the notion of min-entropy. 
It says that extra information can only reduce the uncertainty, and comes up often in cryptography.

For any X,Y,Z we have H_∞(X|Y,Z) ⩽H_∞(X|Y).



It is well known (see, e.g., <cit.>) that when each block has certain min-entropy entropy conditioned on previous blocks, the total entropy
grows linearly with the number of blocks (as expected). The lemma is stated without a proof (it follows directly from definitions).
We stress, however, that using the worst-case notion of conditional entropy is crucial. 

For any X,Y,Z 
we have 
H_∞(X,Y|Z) ⩾H_∞(X|Y,Z)+H_∞(Y|Z).


Another lemma, well known in folklore, quantifies the intuition that conditioning on “large” events (not too surprising information) doesn't decrease entropy too much.

For any random variable X and any events A,B we have H_∞(X|B,A) ⩾ H_∞(X|B)-log(1/(A|B)). 


The first part of the lemma follows because we have [X=x|A,B] = [X=x,A∩ B]/[A∩ B] ⩽[X=x,B]/([B]·[A|B]) for every x.





































§ MAIN RESULT




 §.§ Chain Rule








Let 𝒳 be a fixed alphabet and X=(X_1,…,X_t) be a sequence of (possibly correlated) random variables each over 𝒳.
Then for any 1>ϵ>0 and δ>0 there exists a collection ℬ of disjoint sets on 𝒳^t
such that 


  * ℬ can be indexed by a small number of bits, namely

    log |ℬ| = t· O(loglog|𝒳| +loglog(ϵ^-1)+log (t/δ))


  * ℬ almost covers the domain

    ∑_B∈ℬp_X(B) ⩾ 1-ϵ


  * Conditioned on members of ℬ, block distributions X_i|X_<i are nearly flat.

    ∀ x,x'∈ B:   2^-O(δ)⩽p_X(x_i|x_<i)/p_X(x'_i|x'_<i)⩽ 2^O(δ).

for every B∈ℬ and i=1,…,t.


In some applications (see for example <Ref>) it is convenient to work with parts that are not too small. 
By substituting ϵ:=ϵ/2, and deleting from ℬ
all members of smaller than ϵ/2|ℬ| (their mass is at most ϵ/2), we obtain

In <Ref>, we may assume p_X(B) = Ω(ϵ· |ℬ|^-1) for every B∈ℬ.



Under the assumptions of <Ref>, for every B∈ℬ for every index i and for every 
set I⊂{1,…,i-1} we have

 
  * The chain rule for min-entropy
 
    H_∞(X_i|X_I,B) = H_∞(X_i,X_I|B) - H_∞(X_I|B)  ± O(δ).


  * The average and worst-case min-entropy almost match

    H_∞(X_i|X_I,B) = H_∞(X_i|X_I,B)  ± O(δ).






Fix any subset I⊂{1,…,i-1} of size m. By <Ref> for every x and B we have

    [X_⩽ i = x_⩽ i  |B ] =  2^± O(δ)[X_< i = x_< i |B ].

Let J = {1,…,i-1}∖ I. Taking the sum of <Ref> over
x such that x_I = x'_I and x_i = x” are fixed but x_J varies we obtain

    [X_i=x”,X_I = x'_I  |B ] =  2^± O(δ)[X_I = x'_I |B ].

This implies

    H_∞(X_i|X_I,B) = H_∞(X_i,X_I,B) - H_∞(X_I,B)  ± O(δ) 
    H_∞(X_i|X_I,B) = H_∞(X_i|X_I,B)   ± O(δ)

which finishes the proof.































Let p be the joint distribution of X_1,…,X_n.
For any i denote 

    p_i(x_i|x_i-1,…,x_1) = p_X_i|X_<i(x_i,…,x_1).

and let the “surprise” of the bit x_i be

    r^i(x) = -log p_i(x_i,…,x_1).

Note that
p(x_1,…,x_n) = ∏_i=1^n p_i(x_i,x_i-1,…,x_1) and therefore, denoting x=(x_1,…,x_n), we obtain
[Decomposing surprises]
We have

    ∑_i=1^tr^i(x) = -log p(x).


The next claim follows by a simple Markov-type argument.
[Significant probabilities]
There exists a set A⊂𝒳^t of
probability 1-ϵ such that p(x) ⩾ϵ/|𝒳|^t 
for all x∈ A.


Denoting x=x_1,…,x_n, we have

    ∀ x∈ A:   -log p(x_1,…,x_n) ⩽ tlog|𝒳| + log(1/ϵ).

The claim below follows from <Ref> and <Ref>
[Surprises live in a simplex]
We have r^i(x) ⩾ 0 for i=1,…, t and ∑_i=1^t r^i(x) ⩽ tlog|𝒳| + log(1/ϵ),
for all points x∈ A.



[Simplex coverings imply a chain rule]
If the simplex with side length tlog|𝒳| + log(1/ϵ) can be covered 
by N balls of radius R in the ℓ_∞ norm, then the theorem holds with |ℬ| =  N and δ =  R.


Let C⊂ℝ^t, |C|=N, be the set of the centers of the covering balls.
Let S be the function which assigns to every point x∈ A (where A is defined in <Ref>) the point z∈ C 
closest to the vector (r_1(x),…,r_t(x)) in the ℓ_∞-norm.
Fix any z and let B_z = {x: S(x)=z}. By the properties of the covering, for i=1,…,t we obtain

    ∀ x∈ B:   |r^i(x)-z_i| ⩽ R

In particular, the surprises for any two points in B are close

    ∀ x,x'∈ B:   |r^i(x) -r^i(x')| ⩽ 2R,    i=1,…,t.

Let p_B be the conditional probability of p given B. Denote by 
r^i_B  the surprise of the i-th bit given previous bits and conditioned on B, that is

    r^i_B(x)    = -log[X_i=x_i|X_i-1=x_i-1,…,X_1=x_1,B] 
        = -log p_B(x_i | x_i-1,…,x_1)

Note that p_B(x) = p(x)/p(B) for x∈ B, and hence
r^i_B(x) = r^i(x) + log (p(B)^-1).
Now <Ref> implies

    ∀ x,x'∈ B:   |r^i_B(x) -r^i_B(x')| ⩽ 2R,    i=1,…,t.

which finishes the proof.

It remains to observe that the covering number for our case is
log N = log N_0 + loglog(|𝒳|)+loglog(1/ϵ))+log (t/δ) (see for example <cit.>)
which finishes the proof.









































































































§ APPLICATIONS



Let 𝒳 be a fixed finite alphabet, and
let X_1,…,X_t be a sequence of correlated random variables each over 𝒳. 
Let i_1,…,i_ℓ∈ [1,t], where ℓ < t, be chosen from the set {1,…,t} by an averaging (μ,θ,γ)-sampler. Then there is a random variable ℬ 
taking m = t· O(loglog|𝒳|+loglog(1/ϵ)+log t) bits, 
such that

    1/ℓlog|𝒳|H^ϵ_∞(X_i_ℓX_i_ℓ-1X_i_ℓ-2…,X_i_1|ℬ) ⩾
    1/tlog|𝒳|H_∞(X_i_ℓX_i_ℓ-1X_i_ℓ-2…,X_i_1)-err_𝖲𝗉𝗈𝗂𝗅-err_𝖲𝖺𝗆𝗉𝗅𝖾𝗋

where the errors due to spoiling and sampling equal

    err_𝖲𝗉𝗈𝗂𝗅   = O(loglog|𝒳|+loglog(1/ϵ)+log t)/log|𝒳| 
    
    err_𝖲𝖺𝗆𝗉   = O(√(ℓ^-1log(1/ϵ))).



Composing this with an extractor over 𝒳^ℓ one obtains a local extractor, which 
reads only a small fraction (specifically ℓ/t) of input bits. We refer to <cit.>
for a general discussion.






We will argue that the sequence X_i_1,…,X_i_ℓ, for ℓ sufficiently big, likely
has the same entropy rate (entropy per block) as the original sequence X_1,…,X_ℓ.

Let ℬ be the family guaranteed by <Ref>. By part (a) of <Ref> applied t times
(starting from i=t downto i=1) we have
for every B∈ℬ

    ∑_i=1^tH_∞(X_i|X_<i,B) ⩾ H_∞(X|B) - O(tδ)

and now by part (b) applied to each summand

    ∑_i=1^tH_∞(X_i|X_<i,B) ⩾ H_∞(X|B) - O(tδ).

Note that

    𝔼_i_1,…,i_ℓ∑_j=1^ℓH_∞(X_i_j|X_<i_j,B) = 
     1/t∑_i=1^tH_∞(X_i|X_<i,B)

In particular, with high probability over (i_j)_j=1,…,ℓ 

    1/ℓ∑_j=1^ℓH_∞(X_i_j|X_<i_j,B) ≳1/t∑_i=1^tH_∞(X_i|X_<i,B).

For the sake of clarity, we comment later on the exact error in accuracy and probability in <Ref>.
Observe that by part (b) of <Ref> we obtain

    1/ℓ∑_j=1^ℓH_∞(X_i_j|X_i_jX_i_j-1…,X_i_1|B)  ⩾
    1/ℓ∑_j=1^ℓH_∞(X_i_j|X_<i_j|B) 
     -  O(δ)

(which is the conditioning reduces entropy property). Again, by applying part (b) of <Ref> to the sum on the right-hand side of <Ref> we get

    1/ℓ∑_j=1^ℓH_∞(X_i_j|X_i_jX_i_j-1…,X_i_1|B)  ⩾
    1/ℓ∑_j=1^ℓH_∞(X_i_j|X_i_jX_i_j-1…,X_i_1|B)  - O(δ)

By <Ref> from <Ref> we get for every B'∈ℬ'

    1/ℓH_∞(X_i_ℓX_i_ℓ-1X_i_ℓ-2…,X_i_1|B) ⩾
    1/ℓ∑_j=1^ℓH_∞(X_i_j|X_i_jX_i_j-1…,X_i_1|B)  - O(δ).

Combining this with <Ref>,<Ref> and <Ref> we finally obtain (with high probability)

    1/ℓH_∞(X_i_ℓX_i_ℓ-1X_i_ℓ-2…,X_i_1|B) ≳
    1/tH_∞(X|B) - O(δ).

Note that this holds for every B.
Recall that by <Ref> we can assume [B] = Ω(|ℬ|^-1ϵ). Now by <Ref>
we have H_∞(X|B) > H_∞(X)-O(log|ℬ| + log(1/ϵ))
and thus

    1/ℓH_∞(X_i_ℓX_i_ℓ-1X_i_ℓ-2…,X_i_1|B) ≳
    1/tH_∞(X|B) -O(log|ℬ| + log(1/ϵ))/t.

We can do slightly better. Namely, from <Ref> 

    1/ℓH_∞(X_i_ℓX_i_ℓ-1X_i_ℓ-2…,X_i_1|ℬ) ≳
    1/tH_∞(X|ℬ)  - O(δ).

where ℬ is a random variable that assigns to every point x the corresponding set B covering x, conditioned
in addition on the map being defined (it fails when x is not covered by any B which happens w.p. at most ϵ)
Indeed, we have

    2^-H_∞(X_i_ℓX_i_ℓ-1X_i_ℓ-2…,X_i_1|B)⩽
    ( 2^-H_∞(X_i_tX_i_t-1X_i_ℓ-2…,X_i_1))^ℓ/t.

and <Ref> follows by averaging over B and the Jensen Inequality (note that ℓ < t implies that the corresponding mapping is concave).
By <Ref> applied to X|ℬ=B for all possible B to outcomes of ℬ we obtain

    1/ℓH_∞(X_i_ℓX_i_ℓ-1X_i_ℓ-2…,X_i_1|ℬ) ≳
    1/tH_∞(X) -log |ℬ|/t - O(δ)

It remains to use an explicit bound on |ℬ| from <Ref>, set the sampler to γ = ϵ and compute θ from ϵ and ℓ.




§ CONCLUSION
 
By a simple combinatorial argument combined with the spoiling knowledge technique we showed how to exhibits strong block-source structures
in any min-entropy source. This approach may be applied to locally enforce chain rules (or other desired properties) for min-entropy.















































