Sorry, an error occurred while loading the content.
Browse Groups

• ## [Computational Complexity] A Theory of Reductions?

(1)
• NextPrevious
• 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
Message 1 of 1 , Aug 6, 2008
View Source
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.

Comments most welcome!

--
Posted By Lance to Computational Complexity at 8/06/2008 06:49:00 AM

Your message has been successfully submitted and would be delivered to recipients shortly.
• Changes have not been saved
Press OK to abandon changes or Cancel to continue editing
• Your browser is not supported
Kindly note that Groups does not support 7.0 or earlier versions of Internet Explorer. We recommend upgrading to the latest Internet Explorer, Google Chrome, or Firefox. If you are using IE 9 or later, make sure you turn off Compatibility View.