# Inaccessible entropy I: Inaccessible entropy generators and statistically hiding commitments from one-way functions

### Citation:

Haitner, Iftach, Omer Reingold, Salil Vadhan, and Hoeteck Wee. “Inaccessible entropy I: Inaccessible entropy generators and statistically hiding commitments from one-way functions.” arXiv: 2010.05586 [cs.CR] (2020).
 ArXiv 2020.pdf 626 KB

### Abstract:

Version History: Full version of part of an STOC 2009 paper.

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 $$\mathsf{G}$$ has accessible entropy at most $$k$$ if the following holds: when conditioning on its prior coin tosses, no polynomial-time strategy $$\mathsf{\widetilde{G}}$$ can generate valid output for $$\mathsf{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 $$\mathsf{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.

ArXiv Version

Last updated on 03/02/2021