Metareductions

Marc Fischlin gave a talk on metareductions today. Metareductions are a technique to prove that a notion can not be derived from another in a "black box" manner. The technique itself has been known for a long time and crops up every now and then in different forms, but the name metareduction is comparatively new and the technique has been enjoying a lot of interest recently.

Among other results, Marc has identified the "habitat" of metareductions in an environment bounded bounded by different properties of reductions such as whether they treat the adversary, the underlying primitive or the construction as black boxes or not. A first description of this "environment" was given in the RTV framework; Marc introduced a new nomenclature which he calls CAP that directly mirrors the relevant properties. Metareductions live in the "*BN" layer, that is around reductions that treat the adversary as a black box but not the primitive in question.

The basic idea is the following. Security of a construction is defined by a game G, as in the statement that for any adversary A something holds for the interaction A-G.
To prove this statement under an assumption defined by a game C, one gives a reduction R and switches from the game A-G to A-R-C, arguing that A cannot tell -G from -R-C and that if A- breaks G then (A-R)- breaks C.
To prove that no such R exists, first choose an A. It is common to choose an "all-powerful" A that can extract discrete logarithms in one step, for example.
Assume that R exists: then A-R- breaks C, which is not surprising.
Now construct a metareduction M and change the game from A-R-C to M-R-C. M is no longer all-powerful but can rewind R when necessary to make up for this. As long as R cannot detect that it is playing with M instead of A, (M-R)- now breaks C without the help of A. This is a contradiction unless C was easy to break in the first place.

Unfortunately there is a lot more to constructing M than this. In many reductions one can get away with just considering negligible versus non-negligible functions or giving generous estimates. To get a metareduction argument to work at all, one needs a detailed knowledge of the probabilities involved and usually extra tools like the Chernoff bound.
Intuitively, what is going on is that R is reducing a scheme S to a "slightly simpler" assumption C, the smaller this difference in complexities the easier the job of R and the harder for M to exploit the difference.