IACR News item: 03 November 2013
Elette Boyle, Rafael Pass
ePrint ReportWe show that, assuming the existence of collision-resistant hash functions, there exists a pair of efficient distributions Z, Z\'; such that either:
o extractable one-way functions w.r.t. Z do not exist, or
o 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
o extractability obfuscations for NC1 w.r.t. Z do not exist, or
o 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.
Additional news items may be found on the IACR news page.