International Association
for Cryptologic Research

We present a new information theoretic result which we call the Chaining Lemma. It considers a so-called \"chain\" of random variables, defined by a source distribution X0 with high min-entropy and a number (say, t in total) of arbitrary functions (T1,....Tt) which are applied in succession to that source to generate the chain X0-->X1-->.....-->Xt such that Xi=Ti(X[i-1]). Intuitively, the Chaining Lemma guarantees that, if the chain is not too long, then either (i) the entire chain is \"highly random\", in that every variable has high min-entropy; or (ii) it is possible to find a point j ( 1