论文标题
无法访问的熵I：无法访问的熵发生器和单向功能的统计隐藏承诺
Inaccessible Entropy I: Inaccessible Entropy Generators and Statistically Hiding Commitments from One-Way Functions
论文作者
论文摘要
我们提出了一个新的熵计算概念，测量了与给定发电机一致的高渗透字符串的（在）可行性。具体而言，如果以下情况下，则发电机G的“输出块”最多可访问熵：当对其先前的硬币进行调理时，没有多项式策略$ \ widetilde {g} $可以为G的I'th输出块生成有效的输出，其熵大于K。如果总可访问熵（在块上求和）明显小于G输出的真实熵，则发电机具有无法访问的熵。 作为上述概念的应用，我们根据海特纳，nguyen，ong，reingold和vadhan [Sicomp '09]的结果进行了改进，从而提出了从任意单向功能中的统计上隐藏承诺方案的更简单，更有效地构建。
We put forth a new computational notion of entropy, measuring the (in)feasibility of sampling high-entropy strings that are consistent with a given generator. Specifically, the i'th output block of a generator G has accessible entropy at most k if the following holds: when conditioning on its prior coin tosses, no polynomial-time strategy $\widetilde{G}$ can generate valid output for G's i'th output block with entropy greater than k. A generator has inaccessible entropy if the total accessible entropy (summed over the blocks) is noticeably smaller than the real entropy of G's output. As an application of the above notion, we improve upon the result of Haitner, Nguyen, Ong, Reingold, and Vadhan [Sicomp '09], presenting a much simpler and more efficient construction of statistically hiding commitment schemes from arbitrary one-way functions.
