We show that, assuming the existence of collision-resistant hash functions, there exists a pair of efficient distributions Z, Z'; such that either:
• extractable one-way functions w.r.t. Z do not exist, or
• extractability obfuscations for Turing machines w.r.t. Z do not exist.
A corollary of this result shows that assuming existence of fully homomorphic encryption with decryption in NC1, there exist efficient distributions Z, Z' such that either
• extractability obfuscations for NC1 w.r.t. Z do not exist, or
• SNARKs for NP w.r.t. Z' do not exist.
To achieve our results, we develop a "succinct punctured program” technique, mirroring the powerful "punctured program” technique of Sahai and Waters (ePrint’13), and present several other applications of this new technique.Category / Keywords: Extractability assumptions, obfuscation Date: received 28 Oct 2013, last revised 6 Nov 2013 Contact author: ecb227 at cornell edu Available format(s): PDF | BibTeX Citation Version: 20131106:165151 (All versions of this report) Discussion forum: Show discussion | Start new discussion