×

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].

MSC:

68P25 Data encryption (aspects in computer science)
65C10 Random number generation in numerical analysis
PDFBibTeX XMLCite