« Black-box and Non-black-box Lower Bounds on Assumptions behind IO
Black-box and Non-black-box Lower Bounds on Assumptions behind IO
June 08, 2017, 5:00 PM - 6:00 PM
Location:
CUNY Advanced Science Research Center
The City University of New York
85 St Nicholas Terrace
New York, NY 10031
Click here for map.
Mohammad Mahmoody, University of Virginia
In this talk, we will describe the recent progress on proving lower-bounds on assumptions behind Indistinguishability Obfuscations.
1. We start by discussing fully-black-box separations for IO from basic primitives such as collision-resistant hash functions (or "random oracle-based" primitives in general).
2. Then, in light of recent *positive* results on basing IO on functional encryption [Bitansky-Vaikuntanathan16,Ananth-Jain16] which are *not* black-box, we will see a more "extended" model of black-box constructions that covers constructions such as [BV16,AJ16]. The model is general and applies to "self eating" primitives (including IO itself) that accept generic circuits as inputs.
3. Finally, we will discuss some new lower bounds for IO in this model from primitives such as witness encryption and predicate encryption.
Based on several joint works with: Sanjam Garg, Ameer Mohammed, Soheil Nematihaji, Rafael Pass, Abhi Shelat.