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.