Inaccessible Entropy I: Inaccessible Entropy Generators and Statistically Hiding Commitments from One-Way Functions

We put forth a new computational notion of entropy, measuring the\n(in)feasibility of sampling high-entropy strings that are consistent with a\ngiven generator. Specifically, the i'th output block of a generator G has\naccessible entropy at most k if the following holds: when conditioning on its\nprior coin tosses, no polynomial-time strategy $\\widetilde{G}$ can generate\nvalid output for G's i'th output block with entropy greater than k. A generator\nhas inaccessible entropy if the total accessible entropy (summed over the\nblocks) is noticeably smaller than the real entropy of G's output.\n As an application of the above notion, we improve upon the result of Haitner,\nNguyen, Ong, Reingold, and Vadhan [Sicomp '09], presenting a much simpler and\nmore efficient construction of statistically hiding commitment schemes from\narbitrary one-way functions.\n