Summer 2015

Lower Bounds on VBB and Indistinguishability Obfuscations in Idealized Models

Thursday, August 11th, 2016 12:00 pm12:20 pm

Add to Calendar

I will first show that VBB obfuscation is not possible to achieve in a large variety of structured and algebraic oracle models (e.g. random trapdooer permutation or constant-degree graded encoding model over any finite ring) and then show how to use this result to prove lower bounds on black-box complexity of indistinguishability obfuscation from a large set of primitives (e.g. TDPs or DDH). 

Based on joint works with Ameer Mohammed, Soheil Nematihaji, Rafael Pass, and Abhi Shelat.