Office 7219 Gates and Hillman Centers
Phone (412) 268-7885
Computer Science Department
Algorithms and Complexity
The main focus of my research is in complexity theory and the foundations of cryptography. The wide applicability of the technical ideas in these two areas has allowed me to extend my work into learning theory, probability theory, and combinatorics.
I concern myself with the fundamental questions of each field: How can one obtain a separation result for interesting complexity classes? How can one reduce the security of a cryptographic protocol to the security of a simple primitive? What is a powerful inference method? How can one generalize probability theory to a theory where the events are almost independent?
I work most actively is the meta-theory of the above areas. This means questions like: What are the reducibilities among the above questions? What are the reducibilities among approaches to these questions? When are the perceived technical barriers to their answers related? When are they inherent?
I will mention two examples of these meta-theoretical results. Much of cryptography concerns the reduction of the security of complex protocols to the security of simpler ones. The most important question along these lines is whether a public-key cryptosystem can be based on a black-box, private-key system (such as the Clipper chip). Russell Impagliazzo and I showed that any proof of this particular reduction would contain inside it a proof that P<NP. It follows as a corollary that some 42 similar reductions between ``high'' and ``low'' cryptography are also difficult, because they too are disguised forms of the P v.s. NP question. I have shown that the same sort of thing applies to reductions between high and low interaction public-key protocols.
Curiously, current approaches to the P v.s. NP question are themselves disguised forms of a problem in cryptanalysis. In order to prove that a function f is not in a complexity class C, the standard approach is to exhibit some combinatorial property of the function that provably prevents it from being in the class C. Alexander Razborov and I have argued that all the known lower bound proofs in circuit complexity use what we call Natural combinatorial properties. Any proof that uses a Natural property and shows that some function is not contained in a complexity class C, can be transformed into a successful cryptographic attack against any private-key cryptosystem which is implementable in the class C. Thus, these proof techniques cannot apply to classes (plausibly P, NC 1, or even TC 0) that contain unbreakable cryptography. A corollary greatly extends my previous work with Len Berman by showing that the restriction methods, which were so successful in showing AC 0 lower bounds, are essentially useless in resolving frontier questions in circuit complexity. At this time it remains unclear if proof methods which avoid Natural properties exist. Razborov has shown that in a weak fragment of arithmetic all proof methods are Natural in our sense; it follows under a cryptographic assumption that P v.s. NP is independent of this fragment. I have extended the notion of Natural property to that of NP-Natural property. This generalization also extends Razborov's independence result to more general (but still quite weak) proof systems.