A hard-core predicate for all one-way functions
O Goldreich, LA Levin - Proceedings of the twenty-first annual ACM …, 1989 - dl.acm.org
Proceedings of the twenty-first annual ACM symposium on Theory of computing, 1989•dl.acm.org
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 …
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 …
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.