function l(n) = O(log n) s.t. l(n) ≤ n. Let Then h(x, r) := b1(x, r) b2(x, r) ... bl(|x|)(x, r) is a hard-core function with output length l(|x|). It is sometimes the case that an actual bit of the input x is hard-core. For example, every single bit of inputs to the RSA function is a hard-core predicate of RSA and blocks of O(log |x|) bits of x are indistinguishable from random bit strings in polynomial time (under the assumption that the RSA function is hard to invert). Hard-core predicates give a way to construct a pseudorandom generator from any one-way permutation. If b is a hard-core predicate of a one-way permutation f, and s is a random seed, then is a pseudorandom bit sequence, where fn means the n-th iteration of applying f on s, and b is the generated hard-core bit by each round n. Hard-core predicates of trapdoor one-way permutations (known as trapdoor predicates) can be used to construct semantically secure public-key encryption schemes. See also List-decoding (describes list decoding; the core of the Goldreich-Levin construction of hard-core predicates from one-way functions can be viewed as an algorithm for list-decoding the Hadamard code). References Oded Goldreich, Foundations of Cryptography vol 1: Basic Tools, Cambridge University Press, 2001. Pseudorandomness Theory of cryptography