IACR News item: 20 October 2014
Maciej Skorski
ePrint ReportThe 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 which is 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 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, slightly reducing the loss in quality of entropy. Interestingly, our bound is independent of size of the probability space in comparison to the result of Barak et al. Our approach is based on the theory of convex approximation in $L^p$-spaces.
Additional news items may be found on the IACR news page.