We show that, assuming the existence of public-coin collision-resistant hash functions, there exists an efficient distributions Z such that either
- PC-diO for Turing machines does not exist, or
- extractable one-way functions w.r.t. auxiliary input Z do not exist.
A corollary of this result shows that additionally assuming existence of fully homomorphic encryption with decryption in NC1, there exists an efficient distribution Z such that either
- SNARKs for NP w.r.t. auxiliary input Z do not exist, or
- PC-diO for NC1 circuits does not exist.
To achieve our results, we develop a “succinct punctured program” technique, mirroring the powerful punctured program technique of Sahai and Waters (STOC’14), and present several other applications of this new technique. In particular, we construct succinct perfect zero knowledge SNARGs and give a universal instantiation of random oracles in full-domain hash applications, based on PC-diO.
As a final contribution, we demonstrate that even in the absence of auxiliary input, care must be taken when making use of extractability as- sumptions. We show that (standard) diO w.r.t. any distribution D over programs and bounded-length auxiliary input is directly implied by any obfuscator that satisfies the weaker indistinguishability obfuscation (iO) security notion and diO for a slightly modified distribution D′ of programs (of slightly greater size) and no auxiliary input. As a consequence, we directly obtain negative results for (standard) diO in the absence of auxiliary input.Category / Keywords: Extractability assumptions, obfuscation Original Publication (with major differences): IACR-ASIACRYPT-2015 Date: received 28 Oct 2013, last revised 24 Aug 2015 Contact author: eboyle at alum mit edu Available format(s): PDF | BibTeX Citation Version: 20150824:131043 (All versions of this report) Discussion forum: Show discussion | Start new discussion