Accessible Entropy
Speaker: Iftach Haitner , Microsoft Research New England
Date: January 30 2009
Time: 10:30AM to 12:00PM
Location: 32-449
Contact: Be , 3-6098, imbe@mit.edu
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*.
As applications of this notion, we:
- Give a much simpler and more efficient construction of statistically hiding
commitment schemes from arbitrary one-way functions, and
- 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).
Joint work with Omer Reingold, Salil Vadhan and Hoeteck Wee.
See other events that are part of CIS/Microsoft Seminars 2008/2009
See other events happening in January 2009
