Inaccessible Entropy

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


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



 [ back to Salil Vadhan's research]