Meta-Reductions

Add to your list(s) Download to your calendar using vCal

• Fischlin, M (TU, Darmstadt)
• Wednesday 11 April 2012, 10:00-11:00
• Seminar Room 1, Newton Institute.

If you have a question about this talk, please contact Mustapha Amrani.

Semantics and Syntax: A Legacy of Alan Turing

Meta-Reductions are a technique to show impossiblity results in reductionist cryptography. Roughly, such a meta-reduction M shows that there cannot exist a reduction R which turns a successful adversary against one cryptographic primitive into a successful adversary against another, hard primitive. This is shown by turning the reduction R through the meta-reduction M (a ‘reduction against the reduction’) into an algorithm solving the underlying primitive directly, without relying on the assumption of a successful adversary. Hence, either the reduction R cannot exist (if the primitive is really hard), or it is trivial (if the primitive is already easy). Unlike other separation techniques, meta-reductions usually work for all reductions R which treat the adversary as a black-box, but often do not impose any restriction on the primitives in question, i.e., the primitive may not be treated as a black-box, and the technique may thus apply to common primitives like RSA or DL. In return, all known meta-reductions work for specific primitives only. In this talk we survey the recent result on meta-reductions and shed light on the applicability of this technique.

This talk is part of the Isaac Newton Institute Seminar Series series.

This talk is included in these lists:

• All CMS events
• Featured lists
• INI info aggregator
• Isaac Newton Institute Seminar Series
• School of Physical Sciences
• Seminar Room 1, Newton Institute
• bld31

Note that ex-directory lists are not shown.