*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

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.

Comments most welcome!

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

ReplyDeleteCategory 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

...

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

ReplyDeleteHope this helps.

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.

ReplyDeleteThanks - you two pointed me to interesting work...

ReplyDelete