---
_id: '1479'
abstract:
- lang: eng
  text: "Most entropy notions H(.) like Shannon or min-entropy satisfy a chain rule
    stating that for random variables X,Z, and A we have H(X|Z,A)≥H(X|Z)−|A|. That
    is, by conditioning on A the entropy of X can decrease by at most the bitlength
    |A| of A. Such chain rules are known to hold for some computational entropy notions
    like Yao’s and unpredictability-entropy. For HILL entropy, the computational analogue
    of min-entropy, the chain rule is of special interest and has found many applications,
    including leakage-resilient cryptography, deterministic encryption, and memory
    delegation. These applications rely on restricted special cases of the chain rule.
    Whether the chain rule for conditional HILL entropy holds in general was an open
    problem for which we give a strong negative answer: we construct joint distributions
    (X,Z,A), where A is a distribution over a single bit, such that the HILL entropy
    H HILL (X|Z) is large but H HILL (X|Z,A) is basically zero.\r\n\r\nOur counterexample
    just makes the minimal assumption that NP⊈P/poly. Under the stronger assumption
    that injective one-way function exist, we can make all the distributions efficiently
    samplable.\r\n\r\nFinally, we show that some more sophisticated cryptographic
    objects like lossy functions can be used to sample a distribution constituting
    a counterexample to the chain rule making only a single invocation to the underlying
    object."
acknowledgement: "This work was partly funded by the European Research Council under
  ERC Starting Grant 259668-PSPC and ERC Advanced Grant 321310-PERCY.\r\n"
article_processing_charge: No
author:
- first_name: Stephan
  full_name: Krenn, Stephan
  id: 329FCCF0-F248-11E8-B48F-1D18A9856A87
  last_name: Krenn
  orcid: 0000-0003-2835-9093
- first_name: Krzysztof Z
  full_name: Pietrzak, Krzysztof Z
  id: 3E04A7AA-F248-11E8-B48F-1D18A9856A87
  last_name: Pietrzak
  orcid: 0000-0002-9139-1654
- first_name: Akshay
  full_name: Wadia, Akshay
  last_name: Wadia
- first_name: Daniel
  full_name: Wichs, Daniel
  last_name: Wichs
citation:
  ama: Krenn S, Pietrzak KZ, Wadia A, Wichs D. A counterexample to the chain rule
    for conditional HILL entropy. <i>Computational Complexity</i>. 2016;25(3):567-605.
    doi:<a href="https://doi.org/10.1007/s00037-015-0120-9">10.1007/s00037-015-0120-9</a>
  apa: Krenn, S., Pietrzak, K. Z., Wadia, A., &#38; Wichs, D. (2016). A counterexample
    to the chain rule for conditional HILL entropy. <i>Computational Complexity</i>.
    Springer. <a href="https://doi.org/10.1007/s00037-015-0120-9">https://doi.org/10.1007/s00037-015-0120-9</a>
  chicago: Krenn, Stephan, Krzysztof Z Pietrzak, Akshay Wadia, and Daniel Wichs. “A
    Counterexample to the Chain Rule for Conditional HILL Entropy.” <i>Computational
    Complexity</i>. Springer, 2016. <a href="https://doi.org/10.1007/s00037-015-0120-9">https://doi.org/10.1007/s00037-015-0120-9</a>.
  ieee: S. Krenn, K. Z. Pietrzak, A. Wadia, and D. Wichs, “A counterexample to the
    chain rule for conditional HILL entropy,” <i>Computational Complexity</i>, vol.
    25, no. 3. Springer, pp. 567–605, 2016.
  ista: Krenn S, Pietrzak KZ, Wadia A, Wichs D. 2016. A counterexample to the chain
    rule for conditional HILL entropy. Computational Complexity. 25(3), 567–605.
  mla: Krenn, Stephan, et al. “A Counterexample to the Chain Rule for Conditional
    HILL Entropy.” <i>Computational Complexity</i>, vol. 25, no. 3, Springer, 2016,
    pp. 567–605, doi:<a href="https://doi.org/10.1007/s00037-015-0120-9">10.1007/s00037-015-0120-9</a>.
  short: S. Krenn, K.Z. Pietrzak, A. Wadia, D. Wichs, Computational Complexity 25
    (2016) 567–605.
date_created: 2018-12-11T11:52:16Z
date_published: 2016-09-01T00:00:00Z
date_updated: 2025-09-18T11:37:23Z
day: '01'
ddc:
- '004'
department:
- _id: KrPi
doi: 10.1007/s00037-015-0120-9
ec_funded: 1
external_id:
  isi:
  - '000382686200002'
file:
- access_level: open_access
  checksum: 7659296174fa75f5f0364f31f46f4bcf
  content_type: application/pdf
  creator: system
  date_created: 2018-12-12T10:13:29Z
  date_updated: 2020-07-14T12:44:56Z
  file_id: '5012'
  file_name: IST-2017-766-v1+1_678.pdf
  file_size: 483258
  relation: main_file
file_date_updated: 2020-07-14T12:44:56Z
fulldoi: https://doi.org/10.1007/s00037-015-0120-9
has_accepted_license: '1'
intvolume: '        25'
isi: 1
issue: '3'
language:
- iso: eng
license: https://creativecommons.org/licenses/by/4.0/
month: '09'
oa: 1
oa_version: Submitted Version
page: 567 - 605
project:
- _id: 258C570E-B435-11E9-9278-68D0E5697425
  call_identifier: FP7
  grant_number: '259668'
  name: Provable Security for Physical Cryptography
publication: Computational Complexity
publication_status: published
publisher: Springer
publist_id: '5715'
pubrep_id: '766'
quality_controlled: '1'
related_material:
  record:
  - id: '2940'
    relation: earlier_version
    status: public
scopus_import: '1'
status: public
title: A counterexample to the chain rule for conditional HILL entropy
tmp:
  image: /images/cc_by.png
  legal_code_url: https://creativecommons.org/licenses/by/4.0/legalcode
  name: Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)
  short: CC BY (4.0)
type: journal_article
user_id: 317138e5-6ab7-11ef-aa6d-ffef3953e345
volume: 25
year: '2016'
...