Earlier Version

# A counterexample to the chain rule for conditional HILL entropy, and what deniable encryption has to do with it

Krenn S, Pietrzak KZ, Wadia A. 2013. A counterexample to the chain rule for conditional HILL entropy, and what deniable encryption has to do with it. TCC: Theory of Cryptography Conference, LNCS, vol. 7785, 23–39.

Download

2013_LNCS_Krenn.pdf
414.82 KB

*Conference Paper*|

*Published*|

*English*

**Scopus indexed**

Author

Editor

Sahai, Amit

Department

Series Title

LNCS

Abstract

A chain rule for an entropy notion H(.) states that the entropy H(X) of a variable X decreases by at most l if conditioned on an l-bit string A, i.e., H(X|A)>= H(X)-l. More generally, it satisfies a chain rule for conditional entropy if H(X|Y,A)>= H(X|Y)-l.
All natural information theoretic entropy notions we are aware of (like Shannon or min-entropy) satisfy some kind of chain rule for conditional entropy. Moreover, many computational entropy notions (like Yao entropy, unpredictability entropy and several variants of HILL entropy) satisfy the chain rule for conditional entropy, though here not only the quantity decreases by l, but also the quality of the entropy decreases exponentially in l. However, for
the standard notion of conditional HILL entropy (the computational equivalent of min-entropy) the existence of such a rule was unknown so far.
In this paper, we prove that for conditional HILL entropy no meaningful chain rule exists, assuming the existence of one-way permutations: there exist distributions X,Y,A, where A is a distribution over a single bit, but $H(X|Y)>>H(X|Y,A)$, even if we simultaneously allow for a massive degradation in the quality of the entropy.
The idea underlying our construction is based on a surprising connection between the chain rule for HILL entropy and deniable encryption.

Publishing Year

Date Published

2013-01-29

Volume

7785

Page

23 - 39

Conference

TCC: Theory of Cryptography Conference

Conference Location

Tokyo, Japan

Conference Date

2013-03-03 – 2013-03-06

IST-REx-ID

### Cite this

Krenn S, Pietrzak KZ, Wadia A. A counterexample to the chain rule for conditional HILL entropy, and what deniable encryption has to do with it. In: Sahai A, ed. Vol 7785. Springer; 2013:23-39. doi:10.1007/978-3-642-36594-2_2

Krenn, S., Pietrzak, K. Z., & Wadia, A. (2013). A counterexample to the chain rule for conditional HILL entropy, and what deniable encryption has to do with it. In A. Sahai (Ed.) (Vol. 7785, pp. 23–39). Presented at the TCC: Theory of Cryptography Conference, Tokyo, Japan: Springer. https://doi.org/10.1007/978-3-642-36594-2_2

Krenn, Stephan, Krzysztof Z Pietrzak, and Akshay Wadia. “A Counterexample to the Chain Rule for Conditional HILL Entropy, and What Deniable Encryption Has to Do with It.” edited by Amit Sahai, 7785:23–39. Springer, 2013. https://doi.org/10.1007/978-3-642-36594-2_2.

S. Krenn, K. Z. Pietrzak, and A. Wadia, “A counterexample to the chain rule for conditional HILL entropy, and what deniable encryption has to do with it,” presented at the TCC: Theory of Cryptography Conference, Tokyo, Japan, 2013, vol. 7785, pp. 23–39.

Krenn, Stephan, et al.

*A Counterexample to the Chain Rule for Conditional HILL Entropy, and What Deniable Encryption Has to Do with It*. Edited by Amit Sahai, vol. 7785, Springer, 2013, pp. 23–39, doi:10.1007/978-3-642-36594-2_2.**All files available under the following license(s):**

**Copyright Statement:**

**This Item is protected by copyright and/or related rights.**[...]

**Main File(s)**

File Name

2013_LNCS_Krenn.pdf
414.82 KB

Access Level

Open Access

Date Uploaded

2019-01-22

MD5 Checksum

beb0cc1c0579da2d2e84394230a5da78