Authors Oded Goldreich, Rani Izsak,
License CC-BY-3.0
T HEORY OF C OMPUTING, Volume 8 (2012), pp. 231–238
www.theoryofcomputing.org
NOTE
Monotone Circuits: One-Way Functions
versus Pseudorandom Generators
Oded Goldreich∗ Rani Izsak†
Received: January 24, 2012; published: June 3, 2012.
Abstract: 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.
ACM Classification: F.1.1, F.1.3
AMS Classification: 68Q17, 03D15
Key words and phrases: monotone circuits, one-way functions, pseudorandom generators, cryptography
1 Introduction
One-way functions and pseudorandom generators play a central role in computational complexity
theory and cryptography. Loosely speaking, one-way functions (OWFs) are functions that are easy to
compute but hard to invert (in the average-case sense). Pseudorandom generators (PRGs) are efficient
algorithms that stretch short random seeds into longer (pseudorandom) sequences that are computationally
indistinguishable from truly random sequences. (Indeed, we refer to the standard definitions, which are
recalled in Section 2; for further discussion, the interested reader is referred to [5, 6].)
∗ Partially supported by the Israel Science Foundation (grant No. 1041/08).
† Partially supported by the Israel Science Foundation (grant No. 1041/08).
2012 Oded Goldreich and Rani Izsak
Licensed under a Creative Commons Attribution License DOI: 10.4086/toc.2012.v008a010
O DED G OLDREICH AND R ANI I ZSAK
A fundamental result in this area asserts that one-way functions exist if any only if pseudorandom
generators exist [7] (see also [5, Sec. 3.5]). A relatively recent result of Applebaum, Ishai, and Kushile-
vitz [2] indicates that (under some widely believed conjectures) both OWFs and (sublinear-stretch) PRGs
can be computed by very simple circuits; specifically, by circuits in which each output bit depends only
on a constant number of input bits (i. e., NC0 ).
The latter result raises the natural question of whether OWFs and PRGs can be computed by other
restricted families of circuits. Recalling that PRGs constitute OWFs (see [5, Sec. 3.5]), it is natural to
first ask whether OWFs can be computed by polynomial-size monotone circuits, and then to ask the same
regarding PRGs. We show that the answer to the first question is positive (assuming, of course, that
OWFs exist at all), while the answer to the second question is negative. That is:
Theorem 1.1. If there exist one-way functions, then there exist one-way functions that are computable by
uniform families of polynomial-size monotone circuits.
We stress that not only are these one-way functions monotone, but also their monotone circuit
complexity is polynomial.
Theorem 1.2. No monotone function is a pseudorandom generator. Furthermore, for any monotone
function f : {0, 1}n → {0, 1}n+1 , there exists a (monotone) circuit D in NC0 such that
|Pr [D(Un+1 ) = 1] − Pr[D( f (Un )) = 1]| = Ω 1/n2 ,
where Um denotes a random variable uniformly distributed over {0, 1}m .
We stress that Theorem 1.2 makes no reference to the monotone (or even the general) complexity of
f . We also note that the distinguishers witnessing this failure are very simple (and monotone).
Indeed, these two results indicate that in the “monotone world” there is a fundamental gap between
one-way functions and pseudorandom generators; thus, the “hardness-vs-randomness” paradigm [4, 11, 9]
fails in the monotone setting.
Organization Theorems 1.1 and 1.2 are proved in Sections 3 and 4, respectively. But before turning to
these proofs, we recall (in Section 2) the standard definitions.
2 Preliminaries
We recall the standard definitions (adapted from [5], where the interested reader may find further
discussions). A function f : N → R is called negligible if it decreases faster than the reciprocal of
any positive polynomial (i. e., for every positive polynomial p and all sufficiently large n it holds that
f (n) < 1/p(n)). A function f : N → R is called noticeable if it decreases slower than the reciprocal of
some positive polynomial (i. e., there exists a positive polynomial p such that for all sufficiently large n
it holds that f (n) > 1/p(n)). We say that a family of circuits {Cn } is polynomial-size if there exists a
polynomial p such that for all n it holds that size(Cn ) ≤ p(n), while the number of input bits to the circuit
Cn is not necessarily n.
T HEORY OF C OMPUTING, Volume 8 (2012), pp. 231–238 232
M ONOTONE C IRCUITS : O NE -WAY F UNCTIONS VERSUS P SEUDORANDOM G ENERATORS
Definition 2.1 (One-Way Functions – OWF). Let h : N → [0, 1]. A function F : {0, 1}∗ → {0, 1}∗ is
called h-hard one-way if it satisfies the following two conditions.
• Easy to compute: There exists a polynomial-time algorithm that on input x outputs F(x).
• h-hard to invert: For every family of (uniform)1 polynomial-size circuits {In }n∈N it holds that
Pr In (F(Un )) 6∈ F −1 (F(Un )) ≥ h(n) .
If h is noticeable, then F is called a weak one-way function, whereas if 1 − h is negligible then F is
called a strong one-way function (or just a one-way function).
Note that the above definitional framework has two versions, one referring to uniform polynomial-size
circuits and one referring to all (including non-uniform) polynomial-size circuits. Our results refer to
both versions. The same applies also to the following definition.
Definition 2.2 (Pseudorandom Generator – PRGs). A function G : {0, 1}∗ → {0, 1}∗ is called a pseudo-
random generator if it satisfies the following three conditions:
• Stretch: For every s it holds that |G(s)| > |s|.
• Easy to compute: There exists a polynomial-time algorithm that on input s outputs G(s).
• Pseudorandomness: For every family of (uniform) polynomial-size circuits {Dn }n∈N it holds that
the function ∆ defined by ∆(n) = | Pr[Dn (G(Un )) = 1] − Pr[Dn (U|G(1n )| ) = 1]| is negligible.
Monotone functions and circuits A Boolean function f : {0, 1}n → {0, 1} is called monotone if for
every x ≺ y it holds that f (x) ≤ f (y), where ≺ denotes the standard partial order on (fixed length)
bit strings (i. e., x1 x2 · · · xn ≺ y1 y2 · · · yn if for every i it holds that xi ≤ yi and for some i it holds that
0 = xi < yi = 1). A function f : {0, 1}n → {0, 1}m is called monotone if, for every i ∈ [m], the projection
def
of f on its ith output bit (i. e., fi (x) = f (x)i ) yields a monotone Boolean function. This notion extends
naturally to length regular functions defined over {0, 1}∗ (i. e., functions f : {0, 1}∗ → {0, 1}∗ such that for
every |x| = |y| it holds that | f (x)| = | f (y)|). Throughout this paper, we shall consider only length-regular
functions.
3 OWFs computable by monotone circuits
In this section, we prove Theorem 1.1. We focus on proving that the existence of OWFs implies the
existence of weak-OWFs that are computable by small (uniform) monotone circuits. We derive standard
OWFs (so computable) by observing that the standard amplification of one-way functions (cf., e. g., [5,
Sec. 2.3]) applies to the current (monotone) setting.
The basic idea is to transform a standard OWF into a weak monotone OWF by restricting its “actual
action” to the middle slice, and modifying it on all others slices so as to obtain a monotone function.
1 As usual, in the uniform case, we consider probabilistic circuits.
T HEORY OF C OMPUTING, Volume 8 (2012), pp. 231–238 233
O DED G OLDREICH AND R ANI I ZSAK
Recall that the k-slice of a Boolean function b : {0, 1}n → {0, 1} is defined as {x ∈ {0, 1}n : wt(x) = k},
def
where wt(x) = |{i : xi = 1}| denotes the Hamming weight of x. Now, given a OWF F, we define F 0 such
that F 0 (x) = F(x) if wt(x) = b|x|/2c (i. e., x is in the middle slice) and F 0 (x) = σ |F(x)| otherwise, where
σ = 1 if wt(x) > b|x|/2c and σ = 0 if wt(x) < b|x|/2c.
The function F 0 is monotone, since for every x ≺ y it holds that at most one of these strings belongs
to the middle slice while the values of F 0 on all other slices conform with any value given to the strings
on the middle slice. However, this does not mean that F 0 can be computed by polynomial-size monotone
circuit. Nevertheless, the latter fact is a direct corollary of Berkowitz’s theorem [3]:
Theorem 3.1. Let b : {0, 1}n → {0, 1} be a Boolean function and let C be a circuit computing it. Then,
for every k ∈ {1, . . . , n} there exists a monotone circuit CM of size poly(n) · size(C) that computes the
k-slice function of b (i. e., the function that agrees with b on the k-slice, is zero on lower slices and one on
higher slices). Moreover, CM is polynomial-time constructible, given C as an input.
Specifically, let Tk : {0, 1}n → {0, 1} denote the kth threshold function (i. e., Tk (x) = 1 iff wt(x) ≥ i)
and recall that size(Tk ) = O(n) e (cf. [1]). Let C0 : {0, 1}2n → {0, 1} be the monotone circuit obtained from
C by pushing all negations to the bottom level and replacing negated variables by auxiliary variables;
that is, C(x) = C0 (x, x), where xi = ¬xi . The crucial observation is that for any x such that wt(x) = k, it
holds that ¬xi = Tk (x ∧ 1i−1 01n−i ) (since in that case Tk (x ∧ 1i−1 01n−i ) = 1 iff xi = 0). Letting N(x) =
(Tk (x ∧ 01n−1 ), . . . , Tk (x ∧ 1n−1 0)), we get CM (x) = (Tk (x) ∧C0 (x, N(x))) ∨ Tk+1 (x), which is a monotone
circuit computing the k-slice function of b.
It follows that F 0 has (uniform) monotone polynomial-size circuits, and it is left to show that F 0 is a
weak OWF.
Proposition 3.2. Let F be a (strong) one-way function and let F 0 be as above. Then, no polynomial-size
√
circuits may invert F 0 on F 0 (Un ) with success probability exceeding 1 − Ω(1/ n).
Proof. Intuitively, if the potential inverter has success probability exceeding Pr[wt(Un ) 6= bn/2c], then
the excess must be due to preimages that reside in the middle slice. But since F 0 agrees with F on the
middle slice, this excess translates to a success probability of inverting F.
The actual proof follows by using a standard reducibility argument. Specifically, suppose that
algorithm A inverts F 0 (Un ) with success probability at least 1 − ρ(n) + ε(n), where ρ(n) = Pr[wt(Un ) =
√
bn/2c] = Ω(1/ n). For simplicity, assume first that neither 0n nor 1n is in the image of F, which implies
that for every x ∈ {0, 1}n such that wt(x) = bn/2c it holds that F 0 −1 (y) ⊆ F −1 (y), where y = F 0 (x) = F(x).
Then, it must be that
Pr A(F(Un )) ∈ F −1 (F(Un )) ≥ Pr A(F(Un )) ∈ F −1 (F(Un )) ∧ wt(Un ) = bn/2c
h i
−1
≥ Pr A(F 0 (Un )) ∈ F 0 (F 0 (Un )) ∧ wt(Un ) = bn/2c
h i h i
−1
≥ Pr A(F 0 (Un )) ∈ F 0 (F 0 (Un )) − Pr wt(Un ) 6= bn/2c
≥ ε(n) .
Thus, if A is efficient then ε must be negligible, otherwise we reach a contradiction to the hypothesis
that F is (strongly) one-way. The simplifying assumption (regarding the image of F) may be avoided by
T HEORY OF C OMPUTING, Volume 8 (2012), pp. 231–238 234
M ONOTONE C IRCUITS : O NE -WAY F UNCTIONS VERSUS P SEUDORANDOM G ENERATORS
noting that for any one-way function F it holds that Pr[F(Un ) ∈ {0n , 1n }] is negligible.2 The proposition
follows.
√
Conclusion: It follows that F 0 is an Ω(1/ n)-hard OWF that is computable by (uniform) polynomial-size
monotone circuits. Applying the standard hardness amplification process (i. e., letting
F 00 (z) = F 0 (z[1,m] )F 0 (z[m+1,2m] ) · · · F 0 (z[(m−1)m+1,m2 ] ) ,
where |z| = m2 and z[i, j] = zi · · · z j for i < j), completes the proof of Theorem 1.1.
4 No PRGs are monotone
In this section, we prove Theorem 1.2. Intuitively, we prove that any monotone function that stretches its
input either has a biased output bit or has two output bits that are correlated in a noticeable way. In each
of these two cases, we obtain a very simple circuit that distinguishes the output of the function from a
random sequence of the same length.
4.1 Technical background
We start by defining the core concepts.
Definition 4.1 (ε-biased function). Let b : {0, 1}n → {0, 1} be a Boolean function. We say that b is
ε-biased if
| Pr[b(x) = 1] − Pr[b(x) = 0]| ≤ 2ε . (1)
x x
We say that b is unbiased if it is 0-biased.
Note that equation (1) can be written as | Pr[b(x) = 1] − 1/2| ≤ ε.
x
Definition 4.2 (influence [8]). Let b : {0, 1}n → {0, 1} be a Boolean function. We define the influence
of the ith input bit on b as
Ib (i) = Pr b(x) 6= b(x ⊕ 0i−1 10n−i ) .
x
We next recall two fundamental results regarding these concepts. The first is a theorem proved by
Kahn, Kalai, and Linial [8].
Theorem 4.3. Let b : {0, 1}n → {0, 1} be an unbiased Boolean function. Then, there exists an integer
i ∈ [n] such that Ib (i) = Ω((log n)/n).
(Here as well as in the sequel, n is viewed as a variable.) An almost immediate corollary of
Theorem 4.3 is the following:
Corollary 4.4. Let b : {0, 1}n → {0, 1} be an o((log n)/n)-biased Boolean function. Then, there exists
an integer i ∈ [n] such that Ib (i) = Ω((log n)/n).
2 Alternatively, it suffices to prove the proposition for functions F that satisfy the simplifying assumption.
T HEORY OF C OMPUTING, Volume 8 (2012), pp. 231–238 235
O DED G OLDREICH AND R ANI I ZSAK
Proof. Let b0 : {0, 1}n → {0, 1} be an unbiased Boolean function that is closest to b (i. e., for which
Prx [b0 (x) 6= b(x)] is minimal). Then, Prx [b(x) 6= b0 (x)] = o((log n)/n). By Theorem 4.3, there exists an
integer i, such that Ib0 (i) = Ω((log n)/n). Using
Ib (i) = Pr[b(x) 6= b(x ⊕ 0i−1 10n−i )]
x
≥ Pr[b0 (x) 6= b0 (x ⊕ 0i−1 10n−i )] − 2 · Pr[b(x) 6= b0 (x)]
x x
0
= Ib0 (i) − 2 · Pr[b(x) 6= b (x)] ,
x
the claim follows.
The following theorem was proved by Talagrand [10].
Theorem 4.5. For some universal constant c > 0, we consider the function ϕ(t) = c · t/ log(e/t). Then,
for all n and all monotone functions f , g : {0, 1}n → {0, 1}, it holds that
!
Pr [ f (x) = 1 ∧ g(x) = 1] − Pr [ f (x) = 1] · Pr [g(x) = 1] ≥ ϕ ∑ I f (i) · Ig (i) . (2)
x x x
i∈[n]
It is crucial that the functions considered here are monotone; indeed, the claim fails for general
functions (e. g., consider any pair of distinct linear functions).
4.2 Proof of Theorem 1.2
We now prove Theorem 1.2. Fix any n. Let f1 , . . . , fn+1 be the output bits of f . We shall look at this
sequence as a sequence of n + 1 monotone Boolean functions; that is, functions of the n input variables
x1 , . . . , xn .
If there exists i such that fi is not 1/n2 -biased (i. e., | Pr[ fi (Un ) = 1] − 1/2| > 1/n2 ), then we consider
the (monotone NC0 ) distinguisher Di : {0, 1}n+1 → {0, 1} defined by Di (z) = zi (i. e., the ith bit of z), and
observe that
1
Pr [Di (Un+1 ) = 1] − Pr [Di ( f (Un )) = 1] = − Pr [ fi (Un ) = 1] > 1/n2 .
2
Otherwise (i. e., each fi is 1/n2 -biased), by Corollary 4.4, for each fi , there exists a corresponding input
variable x j such that I fi ( j) = Ω((log n)/n). Then, there exist two output indexes i1 , i2 ∈ [n + 1] and
an input index j ∈ [n] such that both I fi1 ( j) = Ω((log n)/n) and I fi2 ( j) = Ω((log n)/n). Therefore, by
Theorem 4.5, we get:
Pr[ fi1 (x) = 1 ∧ fi2 (x) = 1] − Pr[ fi1 (x) = 1] · Pr[ fi2 (x) = 1]
x x x
!
≥ ϕ ∑ I f (k) · I f (k)
ii ij
k∈[n]
≥ ϕ I fi1 ( j) · I fi2 ( j)
!
log n 2
= ϕ Ω
n
T HEORY OF C OMPUTING, Volume 8 (2012), pp. 231–238 236
M ONOTONE C IRCUITS : O NE -WAY F UNCTIONS VERSUS P SEUDORANDOM G ENERATORS
which is Ω((log n)/n2 ). Then, for the (monotone NC0 ) distinguisher Di1 ,i2 : {0, 1}n+1 → {0, 1} defined
by Di1 ,i2 (z) = zi1 ∧ zi2 , we get
Pr [Di1 ,i2 (Un+1 ) = 1] − Pr [Di1 ,i2 ( f (Un )) = 1]
1
= − Pr [ fi1 (Un ) = fi2 (Un ) = 1]
4
1 log n
≥ − Pr[ fi (x) = 1] · Pr[ fi2 (x) = 1] − Ω
4 x 1 x n2
2
1 1 1 log n log n
≥ − − −Ω ≥ Ω .
4 2 n2 n2 n2
Thus, for each n either one of the n + 1 first distinguishers (i. e., the Di ) or one of the n+1
2 latter
distinguishers (i. e., the Di1 ,i2 ) distinguishes the output of f from a truly random n + 1-bit long string. The
Theorem follows.
References
[1] M. A JTAI , J. KOMLÓS , AND E. S ZEMERÉDI: An O(n log n) sorting network. In Proc. 15th STOC,
pp. 1–9. ACM Press, 1983. [doi:10.1145/800061.808726] 234
[2] B ENNY A PPLEBAUM , Y UVAL I SHAI , AND E YAL K USHILEVITZ: Cryptography in NC0 . SIAM J.
Comput., 36:845–888, 2006. [doi:10.1137/S0097539705446950] 232
[3] S. J. B ERKOWITZ: On some relationships between monotone and non-monotone circuit complexity.
Technical report, University of Toronto, 1982. 234
[4] M ANUEL B LUM AND S ILVIO M ICALI: How to generate cryptographically strong sequences of
pseudo-random bits. SIAM J. Comput., 13:850–864, 1984. Preliminary version in FOCS’82.
[doi:10.1137/0213053] 232
[5] O DED G OLDREICH: Foundations of Cryptography: Basic Tools. Volume 1. Cambridge University
Press, 2001. 231, 232, 233
[6] O DED G OLDREICH: Computational Complexity: A Conceptual Perspective. Cambridge University
Press, 2008. 231
[7] J OHAN H ÅSTAD , RUSSELL I MPAGLIAZZO , L EONID A. L EVIN , AND M ICHAEL L UBY: A
pseudorandom generator from any one-way function. SIAM J. Comput., 28:1364–1396, 1999.
[doi:10.1137/S0097539793244708] 232
[8] J EFF K AHN , G IL K ALAI , AND NATHAN L INIAL: The influence of variables on Boolean functions.
In Proc. 29th FOCS, pp. 68–80. IEEE Comp. Soc. Press, 1988. [doi:10.1109/SFCS.1988.21923]
235
T HEORY OF C OMPUTING, Volume 8 (2012), pp. 231–238 237
O DED G OLDREICH AND R ANI I ZSAK
[9] N OAM N ISAN AND AVI W IGDERSON: Hardness vs. randomness. J. Comput. System Sci., 49:149–
167, 1994. Preliminary version in FOCS’88. [doi:10.1016/S0022-0000(05)80043-1] 232
[10] M ICHEL TALAGRAND: How much are increasing sets positively correlated? Combinatorica,
16:243–258, 1996. [doi:10.1007/BF01844850] 236
[11] A NDREW C. YAO: Theory and application of trapdoor functions. In Proc. 23rd FOCS, pp. 80–91.
IEEE Comp. Soc. Press, 1982. [doi:10.1109/SFCS.1982.95] 232
AUTHORS
Oded Goldreich
professor
Weizmann Institute of Science, Rehovot, Israel
oded goldreich weizmann ac il
http://www.wisdom.weizmann.ac.il/~oded/
Rani Izsak
Ph. D. student
Weizmann Institute of Science, Rehovot, Israel
ran izsak weizmann ac il
ABOUT THE AUTHORS
O DED G OLDREICH (b. 1957) is a professor of Computer Science at the Faculty of Mathemat-
ics and Computer Science of the Weizmann Institute of Science, Israel. His professional
career was greatly influenced by his graduate studies advisor, Shimon Even, and by
his post-doctoral period (1983-86) at the theory group of the Laboratory for Computer
Science of MIT. Oded feels privileged being a faculty member at Weizmann since 1994,
and has enjoyed visits at MIT (1995-98), the Miller Institute of UC-Berkeley (1996), the
Radcliffe Institute of Harvard University (2003-4), and the Institute for Advanced Study
(2011-12). His research interests include the interplay of randomness and computation,
the foundations of cryptography, and computational complexity. He has contributed to
the development of pseudorandomness, zero knowledge proofs, secure function evalu-
ation, property testing, and other areas in cryptography and computational complexity.
He has authored numerous surveys and several books, including the two-volume work
“Foundations of Cryptography” (2001 and 2004) and “Computational Complexity: A
Conceptual Perspective” (2008).
R ANI I ZSAK is a Ph. D. student, supervised by Uri Feige, at the Faculty of Mathematics and
Computer Science of the Weizmann Institute of Science, Israel. His research interests
include computational complexity theory and the design of algorithms.
T HEORY OF C OMPUTING, Volume 8 (2012), pp. 231–238 238