Unifying Computational Entropies via Kullback–Leibler Divergence
Unifying Computational Entropies via Kullback–Leibler Divergence
复制标题
通过 Kullback-Leibler 散度统一计算熵
DOI：
10.1007/978-3-030-26951-7_28
复制
发表时间：
2019
期刊：
影响因子：
--
通讯作者：
Vadhan, Salil
中科院分区：
文献类型：
--
作者：
Agrawal, Rohit;Chen, Yi-Hsiu;Horel, Thibaut;Vadhan, Salil
我们引入相对熵的硬度，一个新的概念的硬度搜索问题，一方面是满足所有的单向函数，另一方面意味着bothnext-block pseudoentropyandinaccessible熵，两种形式的计算熵用于最近的伪随机生成器的建设和统计隐藏承诺计划，分别。因此，相对熵的硬度统一了后两个计算熵的概念，并揭示了它们之间明显的“二元性”。此外，它产生了一个更加模块化和启发性的证明，即单向函数意味着下一个块不可访问的熵，在结构上类似于单向函数意味着下一个块伪熵的证明（Vadhan和Zheng，STOC '12）。
We introducehardness in relative entropy, a new notion of hardness for search problems which on the one hand is satisfied by all one-way functions and on the other hand implies bothnext-block pseudoentropyandinaccessible entropy, two forms of computational entropy used in recent constructions of pseudorandom generators and statistically hiding commitment schemes, respectively. Thus, hardness in relative entropy unifies the latter two notions of computational entropy and sheds light on the apparent “duality” between them. Additionally, it yields a more modular and illuminating proof that one-way functions imply next-block inaccessible entropy, similar in structure to the proof that one-way functions imply next-block pseudoentropy (Vadhan and Zheng, STOC ‘12).