# Inaccessible entropy

### Citation:

Haitner, Iftach, Omer Reingold, Salil Vadhan, and Hoeteck Wee. “Inaccessible entropy.” In Proceedings of the 41st Annual ACM Symposium on Theory of Computing (STOC ‘09), 611-620. ACM, 2009.
 STOC2009.pdf 449 KB

### 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$$’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$$’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}$$’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).

Publisher's Version

Last updated on 07/14/2020