Meta-Reductions

Duration: 44 mins 6 secs

Share this media item:

Embed this media item:

<iframe width="_width_" height="_height_" src="https://sms.cam.ac.uk/media/1246936/embed" frameborder="0" scrolling="no" allowfullscreen></iframe>

Choose size:

About this item

Available Formats

About this item

Description:	Fischlin, M (TU, Darmstadt) Wednesday 11 April 2012, 10:00-11:00


Created:	2012-04-23 14:15
Collection:	Semantics and Syntax: A Legacy of Alan Turing
Publisher:	Isaac Newton Institute
Copyright:	Fischlin, M
Language:	eng (English)


Abstract:	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.

Abstract:

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.

Available Formats

Format	Quality	Bitrate	Size
MPEG-4 Video	640x360	1.84 Mbits/sec	611.63 MB	View	Download
WebM	640x360	711.7 kbits/sec	229.88 MB	View	Download
Flash Video	484x272	568.6 kbits/sec	183.66 MB	View	Download
iPod Video	480x270	506.24 kbits/sec	163.52 MB	View	Download
MP3	44100 Hz	125.03 kbits/sec	40.25 MB	Listen	Download
Auto *	(Allows browser to choose a format it supports)