pdf icon
Volume 8 (2012) Article 10 pp. 231-238 [Note]
Monotone Circuits: One-Way Functions versus Pseudorandom Generators
Received: January 24, 2012
Published: June 3, 2012
Download article from ToC site:
[PDF (200K)] [PS (605K)] [Source ZIP]
Misc.:
[About the Authors] [HTML Bibliography] [BibTeX]
Keywords: monotone circuits, one-way functions, pseudorandom generators, cryptography
Categories: note, complexity theory, cryptography, circuit complexity, monotone circuits, one-way functions, pseudorandom generators
ACM Classification: F.1.1, F.1.3
AMS Classification: 68Q17, 03D15

Abstract: [Plain Text Version]

We study the computability of one-way functions and pseudorandom generators by monotone circuits, showing a substantial gap between the two: On one hand, there exist one-way functions that are computable by (uniform) polynomial-size monotone functions, provided (of course) that one-way functions exist at all. On the other hand, no monotone function can be a pseudorandom generator.