Complexity bounds on general hard-core predicates
2001 (English)In: Journal of Cryptology, ISSN 0933-2790, E-ISSN 1432-1378, Vol. 14, no 3, 177-195 p.Article in journal (Refereed) Published
A Boolean function b is a hard-core predicate for a one-way function S if b is polynomial-time computable but b(x) is difficult to predict from lf(x). A general 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-epsilon)) average sensitivity for any epsilon > 0. As a result, such families cannot consist of functions in AC(0), monotone functions, functions computed by generalized threshold gates, or symmetric d-threshold functions, for d = O(n(1/2-epsilon)) and epsilon > 0.
Place, publisher, year, edition, pages
2001. Vol. 14, no 3, 177-195 p.
cryptography, one-way function, hard-core predicate, pseudorandom generator, bits, rsa
IdentifiersURN: urn:nbn:se:kth:diva-20727ISI: 000169412300002OAI: oai:DiVA.org:kth-20727DiVA: diva2:339423
QC 201005252010-08-102010-08-10Bibliographically approved