Indistinguishability obfuscation from 5-linear maps: a reduction from flying pigs to jumping pigs

Indistinguishability obfuscation jumping pigs - Nir Bitansky

Nir Bitansky
Massachusetts Institute of Technology
March 13, 2017

Indistinguishability obfuscation has turned out to be an outstanding notion with strong implications not only to cryptography, but also other areas such as complexity theory, and differential privacy. Nevertheless, our understanding of how to construct indistinguishability obfuscators is still at its infancy. The first candidates, suggested only several years ago, were based on quite complex assumptions on little-studied multilinear maps. Since then, and especially in light of various attacks on current multilinear maps, there has been an ongoing effort aimed at basing indistinguishability obfuscation on simpler building blocks and better-studied computational assumptions.

This talk will overview one such line of works. I will first describe a reduction from indistinguishability obfuscation to a simpler and longer-studied object called functional encryption. I will then describe the main ideas behind recent constructions of such functional encryption from simple assumptions on 5-linear-map groups, coming closer to well-studied cryptographic objects such as bilinear-map groups.

We will cover the relevant definitions and techniques, often focusing on simplified instances of the above transformations. I will not assume any prior knowledge in cryptography.