Cryptology ePrint Archive: Report 2015/599

The Chain Rule for HILL Pseudoentropy, Revisited

Krzysztof Pietrzak and Maciej Skorski

Abstract: Computationalnotionsofentropy(a.k.a.pseudoentropy)have found many applications, including leakage-resilient cryptography, deter- ministic encryption or memory delegation. The most important tools to argue about pseudoentropy are chain rules, which quantify by how much (in terms of quantity and quality) the pseudoentropy of a given random variable X decreases when conditioned on some other variable Z (think for example of X as a secret key and Z as information leaked by a side-channel). In this paper we give a very simple and modular proof of the chain rule for HILL pseudoentropy, improving best known parameters. Our version allows for increasing the acceptable length of leakage in ap- plications up to a constant factor compared to the best previous bounds. As a contribution of independent interest, we provide a comprehensive study of all known versions of the chain rule, comparing their worst-case strength and limitations.

Category / Keywords: foundations / pseudoentropy

Original Publication (with minor differences): Latincrypt 2015

Date: received 16 Jun 2015

Contact author: maciej skorski at gmail com

Available format(s): PDF | BibTeX Citation

Version: 20150621:165310 (All versions of this report)

Short URL: ia.cr/2015/599

Discussion forum: Show discussion | Start new discussion