Inaccessible Entropy I: Inaccessible Entropy Generators and Statistically Hiding Commitments from One-Way Functions
This addresses the problem of building secure cryptographic primitives from minimal assumptions for cryptographers, though it is incremental as it improves upon existing constructions.
The paper introduces a new computational notion of entropy called inaccessible entropy, which measures the difficulty of generating high-entropy strings consistent with a given generator, and applies it to construct statistically hiding commitment schemes from arbitrary one-way functions, resulting in a simpler and more efficient method compared to prior work.
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 i'th 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 G's i'th 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 G's 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.