Change search
ReferencesLink to record
Permanent link

Direct link
Complexity bounds on general hard-core predicates
KTH, Superseded Departments, Numerical Analysis and Computer Science, NADA.
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
Abstract [en]

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.
Keyword [en]
cryptography, one-way function, hard-core predicate, pseudorandom generator, bits, rsa
URN: urn:nbn:se:kth:diva-20727ISI: 000169412300002OAI: diva2:339423
QC 20100525Available from: 2010-08-10 Created: 2010-08-10Bibliographically approved

Open Access in DiVA

No full text

Search in DiVA

By author/editor
Goldmann, Mikael
By organisation
Numerical Analysis and Computer Science, NADA
In the same journal
Journal of Cryptology

Search outside of DiVA

GoogleGoogle Scholar
The number of downloads is the sum of all downloads of full texts. It may include eg previous versions that are now no longer available

Total: 14 hits
ReferencesLink to record
Permanent link

Direct link