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. We show that no general family of hard core predicates can consist of functions with O(n 1-e ) average sensitivity, for any e > 0. As a result, such families cannot consist of monotone functions, functions computed by generalized threshold gates, or symmetric d-threshold functions, for d = O(n 1/2-e ) and e > 0. This also subsumes a 1997 result of Goldmann and Naslund which asserts that such families cannot consist of functions computable in AC 0 . The above bound on sensitivity is obtained by (lower) bounding the high order terms of the Fourier transform.
['Mikael Goldmann', 'Alan M. Russell']
Spectral bounds on general hard core predicates