Abstract
We study the achievability of different forms of obfuscation and related primitives A,B through relations of the form A=>not(B) ---this says that A,B cannot both exist--- or A=>B ---this says that if A exists so does B or if B does not exist then neither does A. Specifically: (1) We show that VGBO (Virtual Grey Box Obfuscation) for all circuits, which has been conjectured to be achieved by candidate constructions, would imply the failure of Canetti's 1997 AI-DHI1
(auxiliary input DH inversion) assumption and corresponding AIPO (Auxiliary-Input Point-function Obfuscation) scheme (2) We recover AIPO via a variant AI-DHI2 assumption, certain forms of UCE (Universal Computational Extractors), and a construction from any auxiliary-input OWF (3) We show that iO (indistinguishability Obfuscation) for all circuits implies the impossibility of certain forms of leakage-resilient encryption and other forms of UCE.
Joint work with Mihir Bellare and Igors Stepanovs
http://eprint.iacr.org/2015/