Endre søk
RefereraExporteraLink to record
Permanent link

Direct link
Referera
Referensformat
  • apa
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Annet format
Fler format
Språk
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Annet språk
Fler språk
Utmatningsformat
  • html
  • text
  • asciidoc
  • rtf
Complexity bounds on general hard-core predicates
KTH, Tidigare Institutioner (före 2005), Numerisk analys och datalogi, NADA.
2001 (engelsk)Inngår i: Journal of Cryptology, ISSN 0933-2790, E-ISSN 1432-1378, Vol. 14, nr 3, s. 177-195Artikkel i tidsskrift (Fagfellevurdert) 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.

sted, utgiver, år, opplag, sider
2001. Vol. 14, nr 3, s. 177-195
Emneord [en]
cryptography, one-way function, hard-core predicate, pseudorandom generator, bits, rsa
Identifikatorer
URN: urn:nbn:se:kth:diva-20727DOI: 10.1007/s00145-001-0007-6ISI: 000169412300002Scopus ID: 2-s2.0-27644489812OAI: oai:DiVA.org:kth-20727DiVA, id: diva2:339423
Merknad
QC 20100525Tilgjengelig fra: 2010-08-10 Laget: 2010-08-10 Sist oppdatert: 2022-06-25bibliografisk kontrollert

Open Access i DiVA

Fulltekst mangler i DiVA

Andre lenker

Forlagets fulltekstScopus

Søk i DiVA

Av forfatter/redaktør
Goldmann, Mikael
Av organisasjonen
I samme tidsskrift
Journal of Cryptology

Søk utenfor DiVA

GoogleGoogle Scholar

doi
urn-nbn

Altmetric

doi
urn-nbn
Totalt: 36 treff
RefereraExporteraLink to record
Permanent link

Direct link
Referera
Referensformat
  • apa
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Annet format
Fler format
Språk
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Annet språk
Fler språk
Utmatningsformat
  • html
  • text
  • asciidoc
  • rtf