@conference {634708,
title = {Inaccessible entropy},
booktitle = {Proceedings of the 41st Annual ACM Symposium on Theory of Computing (STOC {\textquoteleft}09)},
year = {2009},
pages = {611-620},
publisher = {ACM},
organization = {ACM},
abstract = {
We put forth a new computational notion of entropy, which measures the (in)feasibility of sampling high entropy strings that are consistent with a given protocol. Specifically, we say that the \(i\){\textquoteright}th round of a protocol\ \((\mathsf{A,B})\)\ has\ accessible entropy\ at most\ \(k\), if no polynomial-time strategy\ \(\mathsf{A}^*\)\ can generate messages for\ \(\mathsf{A}\) such that the entropy of its message in the\ \(i\){\textquoteright}th round has entropy greater than\ \(k\)\ when conditioned both on prior messages of the protocol and on prior coin tosses of\ \(\mathsf{A}^*\). We say that the protocol has\ inaccessible entropy\ if the total accessible entropy (summed over the rounds) is noticeably smaller than the real entropy of\ \(\mathsf{A}\){\textquoteright}s messages, conditioned only on prior messages (but not the coin tosses of \(\mathsf{A}\)). As applications of this notion, we
Give a much simpler and more efficient construction of statistically hiding commitment schemes from arbitrary one- way functions.
Prove that constant-round statistically hiding commitments are necessary for constructing constant-round zero-knowledge proof systems for NP that remain secure under parallel composition (assuming the existence of one-way functions).
},
url = {https://dl.acm.org/citation.cfm?id=1536497},
author = {Iftach Haitner and Omer Reingold and Salil Vadhan and Hoeteck Wee}
}