One way to argue that open problems such as $P\stackrel{?}{=}NP$ are difficult is to demonstrate that {\em known} methods are inherently too weak to solve them. This approach was taken in Baker, Gill, and Solovay \cite{BGS} who used oracle separation results for many major complexity classes to argue that relativizing proof techniques could not solve these problems. Since relativizing proof techniques involving diagonalization and simulation were the only available tools at the time of their work (1975) progress along known lines was ruled out. Instead, people started to look at these problems in terms of Boolean complexity. Along these lines, many (non-relativizing) proof techniques have been discovered and used to prove lower bounds. These techniques are highly combinatorial; they exist in a much larger variety than their recursion-theoretic predecessors. In this talk, we do for the 90's what BGS did for the 70's. We introduce the notion of a {\em natural} proof. We argue that {\em all lower bound proofs known to us in non-monotone Boolean complexity either are natural or can be represented as natural}. We show that if a cryptographic hardness assumption is true, then {\em no natural proof can prove superpolynomial lower bounds for general circuits}. Furthermore, no complexity class containing good pseudo-random function generators has a natural proof against it. This gives a proof that the restriction methods which were sufficient to prove the parity lower bounds of FSS, Ajtai, Yao, and Hastad are inherently incapable of proving the bounds for $AC^0[q]$-circuits of Razborov and Smolensky. Razborov has recently found one application of the notion of natural proof to independence. He has shown that all lower bounds in a certain fragment of arithmetic naturalize in our sense. Thus, on a hardness assumption the question of whether SAT has polynomial sized circuits is independent of this fragment. (This is joint work with Alexander Razborov.)