CSAIL Event Calendar

On extractable functions and other beasts

A key step in the security analysis of many cryptographic protocols is coming up with an efficient mechanism for extracting useful information (or, ``knowledge") that is buried inside the attackers algorithm. Often this is also the most challenging step. Indeed, the need for efficient extraction is a common hurdle in way of better protocols and analyses.

The notion of extractable functions (Canetti and Dakdouk, TCC 09) is aimed at distilling the challenge of efficient extraction: Essentially, a function f is extractable if any efficient algorithm A that outputs a value y in the range of f is guaranteed to come with an efficient ``knowledge extraction algorithm" that outputs a corresponding preimage x such that f(x)=y. (Here x can be thought of as the knowledge buried inside the code of A). When combined with appropriate hardness properties, extractable functions can be used as ``extractable computational gadgets" that simplify proofs of security and enable more efficient and powerful protocols.

We will demonstrate the power of extractable functions and related constructs in a number of areas in cryptography, including resettable Zero Knowledge, universally composable computation, program obfuscation and succinct delegation of computation protocols. We will also discuss candidate constructions of extractable functions and the types of hardness assumptions involved.

The talk is aimed at non-cryptographers. In other words it will attempt to extract useful information from adversarial cryptographers and present it in layman's terms.

Based on joint works with Bitansky, Chiesa, Dakdouk, Goldwasser, Lin, Paneth, Rubinstein and Tromer, and works of Bitansky and Paneth.

See other events that are part of Theory Colloquium 2012/2013

See other events happening in February 2013