Paper 2015/581

Universal Computational Extractors and the Superfluous Padding Assumption for Indistinguishability Obfuscation

Chris Brzuska and Arno Mittelbach

Abstract

Universal Computational Extractors (UCEs), introduced by Bellare, Hoang and Keelveedhi (CRYPTO 2013), are a framework of assumptions on hash functions that allow to instantiate random oracles in a large variety of settings. Brzuska, Farshim and Mittelbach (CRYPTO 2014) showed that a large class of UCE assumptions with \emph{computationally} unpredictable sources cannot be achieved, if indistinguishability obfuscation exists. In the process of circumventing obfuscation-based attacks, new UCE notions emerged, most notably UCEs with respect to \emph{statistically} unpredictable sources that suffice for a large class of applications. However, the only standard model constructions of UCEs are for a small subclass considering only $q$-query sources which are \emph{strongly statistically} unpredictable (Brzuska, Mittelbach; Asiacrypt 2014). The contributions of this paper are threefold: 1) We show a surprising equivalence for the notions of strong unpredictability and (plain) unpredictability thereby lifting the construction from Brzuska and Mittelbach to achieve $q$-query UCEs for statistically unpredictable sources. This yields standard model instantiations for various ($q$-query) primitives including, deterministic public-key encryption, message-locked encryption, multi-bit point obfuscation, CCA-secure encryption, and more. For some of these, our construction yields the first standard model candidate. 2) We study the blow-up that occurs in indistinguishability obfuscation proof techniques due to puncturing and state the \emph{Superfluous Padding Assumption} for indistinguishability obfuscation which allows us to lift the $q$-query restriction of our construction. We validate the assumption by showing that it holds for virtual black-box obfuscation. 3) Brzuska and Mittelbach require a strong form of point obfuscation secure in the presence of auxiliary input for their construction of UCEs. We show that this assumption is indeed necessary for the construction of injective UCEs.