Inaccessible entropy
Inaccessible entropy
复制标题
DOI：
10.1145/1536414.1536497
复制
发表时间：
2009-05
期刊：
影响因子：
--
通讯作者：
Iftach Haitner;Omer Reingold;S. Vadhan;H. Wee
中科院分区：
文献类型：
--
作者：
Iftach Haitner;Omer Reingold;S. Vadhan;H. Wee
我们提出了一个新的熵计算概念，该概念测量了与给定协议一致的高熵字符串的（在）可行性。具体而言，我们说，如果没有多项式时间策略a*可以生成a的消息，则协议的第三轮（a，b）最多可访问熵*当在协议的先前消息和a*的先前硬币折腾时，均具有大于k的熵。我们说，该协议具有 *不可访问的熵 *，如果总计可访问的熵（在整个回合中进行了总结）明显小于A消息的真实熵，仅以先验消息为条件（而不是A的硬币折腾）。作为这个概念的应用，我们 - 为任意单向功能提供了更简单，更有效地构建统计上隐藏的承诺方案。 - 证明，对于在并行组成下（假设存在单向函数的存在），为NP构建恒定的零知识证明系统是必需的。
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).