A Boolean function b is a hard-core predicate for a one-way function f if b Is polynomial-time computable but b(x) is difficult to predict from f(x). A general family of hard-core predicates is a family of functions containing a hard-core predicate for any one-way function. A seminal result of Goldreich and Levin asserts that the family of parity functions is a general family of hard-core predicates.
展开▼
