Name
Abstract | ||
|---|---|---|
. 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-ε
) average sensitivity, for any ε > 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 - ε
) and ε > 0 . |
Year | DOI | Venue |
|---|---|---|
2001 | 10.1007/s00145-001-0007-6 | J. Cryptology |
Keywords | Field | DocType |
Key words. Cryptography,One-way function,Hard-core predicate,Pseudorandom generator. | Boolean function,Discrete mathematics,Fourier analysis,Hard-core predicate,Predicate (grammar),Parity (mathematics),Pseudorandom generator,One-way function,Mathematics,Monotone polygon | Journal |
Volume | Issue | ISSN |
14 | 3 | 0933-2790 |
Citations | PageRank | References |
4 | 0.42 | 16 |
Authors | ||
3 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Mikael Goldmann | 1 | 210 | 27.05 |
| Mats Näslund | 2 | 141 | 21.58 |
| Alexander Russell | 3 | 196 | 23.41 |