Paper 2014/836

A Tight Transformation between HILL and Metric Conditional Pseudoentropy

Maciej Skorski

Abstract

HILL Entropy and Metric Entropy are generalizations of the information-theoretic notion of min-entropy to the realistic setting where adversaries are computationally bounded. The notion of HILL Entropy appeared in the breakthrough construction of a PRG from any one-way function (Håstad et al.), and has become the most important and most widely used variant of computational entropy. In turn, Metric Entropy defined as a relaxation of HILL Entropy, has been proven to be much easier to handle, in particular in the context of computational generalizations of the Green-Tao-Ziegler Dense Model Theorem which find applications in leakage-resilient cryptography, memory delegation or deterministic encryption. Fortunately, Metric Entropy can be converted, with some loss in quality, to HILL Entropy as shown by Barak, Shaltiel and Wigderson. In this paper we improve their result, reducing the loss in quality of entropy. Our bound is tight and, interestingly, independent of size of the probability space. As an interesting example of application we derive the computational dense model theorem with best possible parameters. Our approach is based on the theory of convex approximation in $L^p$-spaces.

Note: This work appears as a part of the paper ``Metric Pseudoentropy: Characterizations, Transformations and Applications '', to appear at ICITS 2015. Preliminary versions of this work appeared in the Proceedings of Student Research Forum Papers and Posters at SOFSEM 2015.

Metadata
Available format(s)
PDF
Publication info
Published elsewhere. Minor revision. ICITS 2015
Keywords
PseudoentropyDense Model TheoremConvex Approximation
Contact author(s)
maciej skorski @ gmail com
History
2015-03-19: last of 2 revisions
2014-10-20: received
See all versions
Short URL
https://ia.cr/2014/836
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2014/836,
      author = {Maciej Skorski},
      title = {A Tight Transformation between HILL and Metric Conditional Pseudoentropy},
      howpublished = {Cryptology ePrint Archive, Paper 2014/836},
      year = {2014},
      note = {\url{https://eprint.iacr.org/2014/836}},
      url = {https://eprint.iacr.org/2014/836}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.