TR09-045 Authors: Iftach Haitner, Omer Reingold, Salil Vadhan, Hoeteck Wee

Publication: 26th May 2009 05:18

Downloads: 2660

Keywords:

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).