A hard-core predicate for all one-way functions
A hard-core predicate for all one-way functions
复制标题
DOI：
10.1145/73007.73010
复制
发表时间：
1989-02
期刊：
影响因子：
--
通讯作者：
Oded Goldreich;L. Levin
中科院分区：
文献类型：
--
作者：
Oded Goldreich;L. Levin
构造伪随机生成器的中心工具是安全加密函数，在其他领域是函数(排列)ƒ的“核心”谓词b，在[Blum Micali 82]中发现。仅给出ƒ(X)，这样的b(X)不能被有效地猜测(基本上比50-50好)。B，ƒ都可以在多项式时间内计算。[姚82]将任何单向函数ƒ转换为一个更复杂的函数ƒ*，它有一个硬核谓词。该构造将原始ƒ应用于ƒ*的许多小输入片段，只是为了获得一个“核心”位。该比特的安全性可以小于ƒ安全性的任何恒定正幂。事实上，对于实际大小的输入(到ƒ*)，ƒ影响的片段非常小，以至于可以通过穷举搜索来反转ƒ(并计算“核心”位)。本文证明了填充到ƒ(p，x)=(p，g(X))，‖‖p‖‖=‖x‖形式的每个单向函数本身都有一个相同的(在一个多项式内)安全性的硬核谓词。也就是说，我们证明了[Levin 87，SEC.5.6.2]布尔向量p，x的标积是每个单向函数ƒ(p，x)=(p，g(X))的硬核。结果扩展到多个这样的比特(直到安全的对数)，以及x上ƒ难以求逆的任何分布。
A central tool in constructing pseudorandom generators, secure encryption functions, and in other areas are “hard-core” predicates b of functions (permutations) ƒ, discovered in [Blum Micali 82]. Such b(x) cannot be efficiently guessed (substantially better than 50-50) given only ƒ(x). Both b, ƒ are computable in polynomial time. [Yao 82] transforms any one-way function ƒ into a more complicated one, ƒ*, which has a hard-core predicate. The construction applies the original ƒ to many small pieces of the input to ƒ* just to get one “hard-core” bit. The security of this bit may be smaller than any constant positive power of the security of ƒ. In fact, for inputs (to ƒ*) of practical size, the pieces effected by ƒ are so small that ƒ can be inverted (and the “hard-core” bit computed) by exhaustive search. In this paper we show that every one-way function, padded to the form ƒ(p, x) = (p, g(x)), ‖‖p‖‖ = ‖x‖, has by itself a hard-core predicate of the same (within a polynomial) security. Namely, we prove a conjecture of [Levin 87, sec. 5.6.2] that the scalar product of Boolean vectors p, x is a hard-core of every one-way function ƒ(p, x) = (p, g(x)). The result extends to multiple (up to the logarithm of security) such bits and to any distribution on the x's for which ƒ is hard to invert.