Inaccessible Entropy
Iftach Haitner, Omer Reingold, Salil Vadhan, and Hoeteck Wee
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 (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 i’th round has entropy greater than k when conditioned both on prior messages of the protocol and on prior coin tosses of 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 A's messages, conditioned only on prior messages (but not the coin tosses of 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).
Versions
- In Proceedings of the 41st Annual ACM Symposium on Theory of Computing (STOC `09), pages 611-620, 31 May-2 June 2009. [pdf][ACM page]
- Electronic Colloquium on Computational Complexity TR09-045, May 2009. [pdf][ECCC page]
- Talk at Israel Theory Day, Open University, Raanana, Israel, March 2009. [ppsx]
- Talk at Oberwolfach Meeting on Complexity Theory, Germany, November 2009 [ppsx][3-page abstract]
(This talk uses a simpler notion and construction of "inaccessible entropy generators," which we have not yet incorporated into the full paper, but a description can be found in the abstract for the Oberwolfach talk.)
- See also survey talk on Computatational Entropy at Michael Rabin 80th Birthday Celebration, Cambridge, MA, August 2011.
[ back to
Salil Vadhan's research]