Complexity bounds on general hard-core predicates.

DOI10.1007/S00145-001-0007-6MaRDI QIDQ5944107zbMATH OpenOpenAlexFDO

Authors Mikael Goldmann, Mats Näslund, Alexander Russell

Publication date 7 November 2001

Published in Journal of Cryptology (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/s00145-001-0007-6

zbMATH Keywords

circuit complexitycryptographyhard-core predicateone-way functionpseudorandom number generator

Mathematics Subject Classification ID

Cryptography (94A60)

Review text

A Boolean function is said to be a hard-core predicate for a one-way function if it is efficiently computable, but given the value of the one-way function, the value of the hard-core predicate is difficult to predict. The question studied in the present paper is how hard a function must be in order to be a hard-core predicate. A general condition in terms of Fourier coefficients is given that implies some previous lower bounds (e.g., hard-core predicates cannot be in \(\text{ AC}^0\)) as well as some interesting new lower bounds (in terms of monotone circuits and threshold circuits).

Recommendations

• scientific article; zbMATH DE number 1088223
• scientific article; zbMATH DE number 1500548
• scientific article; zbMATH DE number 3990863
• Advances in Cryptology – CRYPTO 2004
• On the Complexity of Hard-Core Set Constructions

Cited in

(5)

• Hard-core theorems for complexity classes
• scientific article; zbMATH DE number 1088223 (Why is no real title available?)
• scientific article; zbMATH DE number 1962816 (Why is no real title available?)
• scientific article; zbMATH DE number 1500548 (Why is no real title available?)
• On the complexity of computation of rudimentary predicates

This page was built for publication: Complexity bounds on general hard-core predicates.

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5944107)