Change search
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • harvard1
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf
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
Identifiers
URN: urn:nbn:se:kth:diva-20727ISI: 000169412300002OAI: oai:DiVA.org:kth-20727DiVA: diva2:339423
Note
QC 20100525Available from: 2010-08-10 Created: 2010-08-10 Last updated: 2017-12-12Bibliographically 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

urn-nbn

Altmetric score

urn-nbn
Total: 22 hits
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • harvard1
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf