Modulus computational entropy

DOI10.1007/978-3-319-04268-8_11MaRDI QIDQ2948262zbMATH OpenOpenAlexFDO

Authors Maciej Skórski

Publication date 30 September 2015

Published in Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1302.2128

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Measures of information, entropy (94A17) Cryptography (94A60)

Abstract: The so-called {em leakage-chain rule} is a very important tool used in many security proofs. It gives an upper bound on the entropy loss of a random variable $X$ in case the adversary who having already learned some random variables $Z_1,ldots,Z_{ell}$ correlated with $X$, obtains some further information $Z_{ell+1}$ about $X$. Analogously to the information-theoretic case, one might expect that also for the emph{computational} variants of entropy the loss depends only on the actual leakage, i.e. on $Z_{ell+1}$. Surprisingly, Krenn et al. have shown recently that for the most commonly used definitions of computational entropy this holds only if the computational quality of the entropy deteriorates exponentially in $|(Z_1,ldots,Z_{ell})|$. This means that the current standard definitions of computational entropy do not allow to fully capture leakage that occurred "in the past", which severely limits the applicability of this notion. As a remedy for this problem we propose a slightly stronger definition of the computational entropy, which we call the emph{modulus computational entropy}, and use it as a technical tool that allows us to prove a desired chain rule that depends only on the actual leakage and not on its history. Moreover, we show that the modulus computational entropy unifies other,sometimes seemingly unrelated, notions already studied in the literature in the context of information leakage and chain rules. Our results indicate that the modulus entropy is, up to now, the weakest restriction that guarantees that the chain rule for the computational entropy works. As an example of application we demonstrate a few interesting cases where our restricted definition is fulfilled and the chain rule holds.

Recommendations

• The chain rule for HILL pseudoentropy, revisited
• A better chain rule for HILL pseudoentropy -- beyond bounded leakage
• A counterexample to the chain rule for conditional HILL entropy
• Pseudoentropy: lower-bounds for chain rules and transformations
• A counterexample to the chain rule for conditional HILL entropy. And what deniable encryption has to do with it

Cites work

• A counterexample to the chain rule for conditional HILL entropy. And what deniable encryption has to do with it
• A Mathematical Theory of Communication
• A Pseudorandom Generator from any One-way Function
• Characterizing pseudoentropy and simplifying pseudorandom generator constructions
• Computational analogues of entropy
• Conditional Computational Entropy, or Toward Separating Pseudoentropy from Compressibility
• Fuzzy Extractors: How to Generate Strong Keys from Biometrics and Other Noisy Data
• Overcoming weak expectations
• Some notions of entropy for cryptography. (Invited talk)

Cited in

(7)

• The chain rule for HILL pseudoentropy, revisited
• Unifying leakage classes: simulatable leakage and pseudoentropy
• Metric pseudoentropy: characterizations, transformations and applications
• The Chaining Lemma and its application
• A better chain rule for HILL pseudoentropy -- beyond bounded leakage
• A counterexample to the chain rule for conditional HILL entropy
• Min-entropy as a resource

This page was built for publication: Modulus computational entropy

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2948262)