An Improved Transformation between HILL and Metric Conditional Pseudoentropy

Abstract. HILL Entropy and Metric Entropy are generalizations of the information-theoretic notion of min-entropy to the realistic setting where an adversary is computationally bounded. The notion of HILL Entropy appeared in the breakthrough construction of a PRG from any one-way function, and has become the most important and most widely used definition 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. 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 en-tropy. Interestingly, our bound is independent of size of the probability space. As an interesting example of application we derive the computa-tional dense model theorem with best known parameters, which does not follow from the result of Barak et al.. This application suggests that our transformation is tight. Our approach is based on the theory of convex approximation in Lp-spaces