Paper 2014/979

The Chaining Lemma and its application

Ivan Damgaard, Sebastian Faust, Pratyay Mukherjee, and Daniele Venturi


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 X[0] 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 X[0]-->X[1]-->.....-->X[t] such that X[i] = 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 <= j <= t) in the chain such that, conditioned on the end of the chain the preceding part remains highly random. We believe this is an interesting information-theoretic result which is intuitive but nevertheless requires rigorous case-analysis to prove. We believe that the above lemma will find applications in cryptography. We give an example of this, namely we show an application of the lemma to protect essentially any cryptographic scheme against memory-tampering attacks. We allow several tampering requests, the tampering functions can be arbitrary, however, they must be chosen from a bounded size set of functions that is fixed a priori.

Available format(s)
Publication info
Published elsewhere. Major revision. ICITS 2015
information theorytamper resistance
Contact author(s)
pratyay85 @ gmail com
2015-02-18: revised
2014-12-07: received
See all versions
Short URL
Creative Commons Attribution


      author = {Ivan Damgaard and Sebastian Faust and Pratyay Mukherjee and Daniele Venturi},
      title = {The Chaining Lemma and its application},
      howpublished = {Cryptology ePrint Archive, Paper 2014/979},
      year = {2014},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.