Goldmann, Mikael; Näslund, Mats The complexity of computing hard core predicates. (English) Zbl 0884.68046 Kaliski, Burton S. jun. (ed.), Advances in Cryptology - CRYPTO ’97. 17th annual international cryptology conference. Santa Barbara, CA, USA. August 17–21, 1997. Proceedings. Berlin: Springer. Lect. Notes Comput. Sci. 1294, 1-15 (1997). Summary: We prove that a general family of hard core predicates requires circuits of depth \((1-o(1)){\log n\over\log\log n}\) or super-polynomial size to be realized. This lower bound is essentially tight. For constant depth circuits, an exponential lower bound on the size is obtained. Assuming the existence of one-way functions, we explicitly construct a one-way function \(f(x)\) such that for any circuit \(c\) from a family of circuits as above, \(c(x)\) is almost always predictable from \(f(x)\).For the entire collection see [Zbl 0870.00047]. Cited in 1 Review MSC: 68P25 Data encryption (aspects in computer science) 65C10 Random number generation in numerical analysis Keywords:pseudo-randomness; small-depth circuit; one-way functions PDFBibTeX XMLCite \textit{M. Goldmann} and \textit{M. Näslund}, Lect. Notes Comput. Sci. 1294, 1--15 (1997; Zbl 0884.68046)