Wednesday, August 06, 2008

A Theory of Reductions?

A guest post by Jens Zumbraegel

I am working on cryptography, and I came across complexity theory only recently. My question is whether a general framework for the various types of reduction exists. Let me give motivation:

The concept of reduction in order to compare the computational hardness of algorithmic problems is a very important one. However many types of reductions are used in the literature for different purposes. Trying a rough classification:

• "Classical" complexity theory: Karp/many-to-one or Cook reductions
• Average-case complexity: Karp reductions with a domination condition between distributional problems
• Cryptography: "reducibility arguments" in "provable security", i.e. ad-hoc reductions of the problem BREAKING-THE-CRYPTOSYSTEM to some well-known hard number theoretic problem, like FACTORING
I believe that a reduction theory for cryptographic purposes could simplify and structure many results in the area of provable security. Apparently there is not yet such a theory. One reason might be that although informally stated problems like "breaking the cryptosystem" have been formalized they do not fit into the framework of decision or search problems (they often involve oracle access for e.g. deciphering).

Back to my question - I wonder whether there is a general abstract theory of reductions, probably similar to category theory: One defines the class of algorithmic problems (the objects of the "category") and the type of reductions (the morphisms) one would like to consider. For example: (decision problems for languages in {0,1}*, Karp reductions). Such a general framework could help to set up a reduction theory for cryptography.

1. With only problems and reductions, you're not going to get much more than new terms for complexity concepts. For example:

Category theory <-> Complexity theory
objects <-> NP problems
morphisms <-> poly-time many-one reductions
initial objects <-> problems in P
final objects <-> NP-complete problems
direct sums <-> tagged unions
...

2. A paper which addresses this topic is "Notions of Reducibility between Cryptographic Primitives" by Omer Reingold, Luca Trevisan and Salil Vadhan (TCC 2004).

Hope this helps.

3. Why do you refer to the "reducibility arguments" in "provable security" as "ad-hoc"? It sounds like you are unaware of the way cryptographic proofs of security work; you might want to see the Katz-Lindell textbook for a good introduction to these topics.

4. Thanks - you two pointed me to interesting work...