Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden.
powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden.
powered by
Abstract
Extractability, or “knowledge,” assumptions 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 (public-coin) differing-inputs obfuscation ((PC-)\(di\mathcal {O}\)), 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 \(\mathcal {Z}\).
We show that, assuming the existence of public-coin collision-resistant hash functions, there exists an efficient distributions \(\mathcal {Z}\) such that either
PC-\(di\mathcal {O}\) for Turing machines does not exist, or
extractable one-way functions w.r.t. auxiliary input \(\mathcal {Z}\) do not exist.
A corollary of this result shows that additionally assuming existence of fully homomorphic encryption with decryption in \(NC^1\), there exists an efficient distribution \(\mathcal {Z}\) such that either
SNARKs for \(\mathsf {NP}\) w.r.t. auxiliary input \(\mathcal {Z}\) do not exist, or
PC-\(di\mathcal {O}\) for \(NC^1\) 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-\(di\mathcal {O}\).
As a final contribution, we demonstrate that even in the absence of auxiliary input, care must be taken when making use of extractability assumptions. We show that (standard) \(di\mathcal {O}\) w.r.t. any distribution \(\mathcal {D}\) over programs and bounded-length auxiliary input is directly implied by any obfuscator that satisfies the weaker indistinguishability obfuscation (i\(\mathcal {O}\)) security notion and \(di\mathcal {O}\) for a slightly modified distribution \(\mathcal {D}'\) of programs (of slightly greater size) and no auxiliary input. As a consequence, we directly obtain negative results for (standard) \(di\mathcal {O}\) in the absence of auxiliary input.
Anzeige
Bitte loggen Sie sich ein, um Zugang zu Ihrer Lizenz zu erhalten.
The notion of indistinguishability obfuscation [2] requires that obfuscations \(\mathcal {O}(C_1)\) and \(\mathcal {O}(C_2)\) of any two equivalent circuits \(C_1\) and \(C_2\) (i.e., whose outputs agree on all inputs) from some class \(\mathcal C\) are computationally indistinguishable. A candidate construction for general-purpose indistinguishability obfuscation was recently given by Garg et al. [18].
As far as we know, the only exceptions are in the context of zero-knowledge simulation, where the extractor is used in the simulation (as opposed to being used as part of a reduction), and we require simulation w.r.t. arbitrary auxiliary inputs. Nevertheless, as pointed out in the works on zero-knowledge [26, 27], to acheive “plain” zero-knowledge [3, 25] (where the verifier does not receive any auxiliary input), weaker “bounded” auxiliary input assumptions suffice.
A version of our paper with Theorems 1 and 2 for (standard) differing-inputs obfuscation in the place of public-coin \({di\mathcal {O}}\) has been on ePrint since October 2013 [12].
That is, a PRF where we can surgically remove one point in the domain of the PRF, keeping the rest of the PRF intact, and yet, even if we are given the seed of the punctured PRF, the value of the original PRF on the surgically removed point remains computationally indistinguishable from random.
That is, [28] shows that for every trapdoor one-to-one function, there exists some way to instantiate the random oracle so that the resulting scheme is secure. In contrast, our results shows that there exists a single instantiation that works no matter what the trapdoor function is.
[5] consider the setting of arbitrary auxiliary input; however, their construction directly implies similar results for specific auxiliary input distributions.