Journal article:
Samuel R. Buss.
"Bounded arithmetic, cryptography and complexity."
Theoria 63 (1997)147-167
Download article: postscript or PDF.
Abstract: This survey discusses theories of bounded arithmetic, growth rates of definable functions, natural proofs, interpolation theorems, connections to cryptography, and the difficulty of obtaining independence results.
The outline of this paper is as follows. We presume the reader has knowledge of the PTIME, NP and the polynomial time hierarchy. We also presume knowledge of the main theories of bounded arithmetic, but we restate some of the definitions and the main witnessing theorems needed for this paper (see \cite{Buss:bookBA,HajekPudlak:book,Krajicek:book} for background on bounded arithmetic). We discuss the impossibility of getting better bounds on the degrees of the polynomial runtimes of functions extracted from $S^1_2$-proofs. Turning to the central theme of the paper, we discuss a natural approach that one might hope could establish the independence of PTIME=NP$ from $S^1_2$, but give evidence based on the theory of pseudorandom number generators that this approach is unlikely to work. Then we discuss the notion of natural proofs and the theorems of Razborov and Rudich stating that if a certain cryptographic conjecture holds, then there are no natural proofs and no $S^2_2(\alpha)$-proofs that NP requires superpolynomial size circuits. Finally we define the $\Delta^b_1$-interpolation property, and prove that if $S^1_2+\Phi$ has the $\Delta^b_1$-interpolation property then the Rabin encryption function $x\mapsto x^2 \bmod N$ is not secure. This result extends the above-mentioned results of Kraj\'\i\v cek and Pudl\'ak to a third cryptographic protocol, which is also generally believed to be cryptographically secure.