@article {669854,
title = {Inaccessible entropy I: Inaccessible entropy generators and statistically hiding commitments from one-way functions},
journal = {arXiv: 2010.05586 [cs.CR]},
year = {2020},
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\){\textquoteright}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}\){\textquoteright}s \(i \){\textquoteright}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}\){\textquoteright}s output.
As an application of the above notion, we improve upon the result of Haitner, Nguyen, Ong, Reingold, and Vadhan [Sicomp {\textquoteright}09], presenting a much simpler and more efficient construction of statistically hiding commitment schemes from arbitrary one-way functions.
},
url = {https://arxiv.org/abs/2010.05586},
author = {Iftach Haitner and Omer Reingold and Salil Vadhan and Hoeteck Wee}
}