%0 Journal Article %J arXiv: 2010.05586 [cs.CR] %D 2020 %T Inaccessible entropy I: Inaccessible entropy generators and statistically hiding commitments from one-way functions %A Iftach Haitner %A Omer Reingold %A Salil Vadhan %A Hoeteck Wee %X

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.

%B arXiv: 2010.05586 [cs.CR] %G eng %U https://arxiv.org/abs/2010.05586