On the Implausibility of Differing-Inputs Obfuscation and Extractable Witness Encryption with Auxiliary Input

摘要

The notion of differing-inputs obfuscation (diO) was introduced by Barak et al. (CRYPTO, pp 1-18, 2001). It guarantees that, for any two circuits C-0,C-1 for which it is difficult to come up with an input x on which C-0(x) not equal C-1(x), it should also be difficult to distinguish the obfuscation of C-0 from that of C-1. This is a strengthening of indistinguishability obfuscation, where the above is only guaranteed for circuits that agree on all inputs. Two recent works of Ananth et al. (Differing-inputs obfuscation and applications, http://eprint.iacr.org/, 2013) and Boyle et al. (Lindell, pp 52-73, 2014) study the notion of diO in the setting where the attacker is also given some auxiliary information related to the circuits, showing that this notion leads to many interesting applications. In this work, we show that the existence of general-purpose diO with general auxiliary input has a surprising consequence: it implies that a specific circuit C* with specific auxiliary input aux* cannot be obfuscated in a way that hides some specific information. In other words, under the conjecture that such special-purpose obfuscation exists, we show that general-purpose diO cannot exist. This conjecture is a falsifiable assumption which we do not know how to break for candidate obfuscation schemes. We also show similar implausibility results for extractable witness encryption with auxiliary input and for "output-only dependent" hardcore bits for general one-way functions.