You are looking at a specific version 20131106:165151 of this paper. See the latest version.

Paper 2013/703

Limits of Extractability Assumptions with Distributional Auxiliary Input

Elette Boyle and Rafael Pass

Abstract

Extractability, or “knowledge,” assumptions (such as the “knowledge-of-exponent” assumption) have recently gained popularity in the cryptographic community—leading to the study of primitives such as extractable one-way functions, extractable hash functions, succinct non- interactive arguments of knowledge (SNARKs), and extractable obfuscation, and spurring the development of a wide spectrum of new applications relying on these primitives. For most of these applications, it is required that the extractability assumption holds even in the presence of attackers receiving some auxiliary information that is sampled from some fixed efficiently computable distribution Z. 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.

Metadata
Available format(s)
PDF
Publication info
Preprint. MINOR revision.
Keywords
Extractability assumptionsobfuscation
Contact author(s)
ecb227 @ cornell edu
History
2015-08-24: last of 4 revisions
2013-11-03: received
See all versions
Short URL
https://ia.cr/2013/703
License
Creative Commons Attribution
CC BY
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.