We put forth a new computational notion of entropy, measuring the (in)feasibility of sampling high-entropy strings that are consistent with a given generator. Specifically, the ith output block of a generator G has accessible entropy at most k if the following holds: when conditioning on its prior coin tosses, no polynomial-time strategy $widetilde{G}$ can generate valid output for Gs ith output block with entropy greater than k. A generator has inaccessible entropy if the total accessible entropy (summed over the blocks) is noticeably smaller than the real entropy of Gs output. As an application of the above notion, we improve upon the result of Haitner, Nguyen, Ong, Reingold, and Vadhan [Sicomp 09], presenting a much simpler and more efficient construction of statistically hiding commitment schemes from arbitrary one-way functions.
Download