A Hard-Core Predicate for all One-Way Functions

Authors: Oded Goldreich, Leonid A. Levin - ACM Symposium on Theory of Computing, STOC 1989 cited by 1,210

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.