Accessible Entropy (tentative title)

by Iftach Haitner, Omer Reingold Salil Vadhan and Hoeteck Wee.

Oded's comments

The standard notion of "computational entropy" refers to a situation in which a distribution appears to have a higher entropy than it actually has; that is, a distribution $X$ is computationally indistinguishable from a distribution $Y$ whereas $H(Y) > H(X)$, where $H(Z)$ denotes the standard (information theoretic) measure of entropy. The new notion refers to a "kind of opposite" situation in which sampling the support of a distribution fails to obtain its entropy; that is, any feasible procedure $S$ that sample the support of a distribution $X$ has entropy that is lower than the entropy of $X$ (i.e., $H(S) < H(X)$).
One nice application of the new notion is a construction of a statistically hiding commitment (from any one-way function) which mirrors the construction of statistically binding commitment (from any one-way function, via the construction of a pseudorandom generator). Thus, these two dual primitives are derived via analogous manipulations of dual notions of computational entropy.

The original 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 ith round of a protocol (A; B) has accessible entropy at most k, if no polynomial-time strategy A* can generate messages for A such that the entropy of its message in the ith round has entropy greater than k when conditioned both on prior messages of the protocol and on prior coin tosses of A*. As applications of this notion, we
1. Give a much simpler and more efficient construction of statistically hiding commitment schemes from arbitrary one-way functions.
2. 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).

Back to list of Oded's choices.