Limits of extractability assumptions with distributional auxiliary input. (English) Zbl 1375.94106
Iwata, Tetsu (ed.) et al., Advances in cryptology – ASIACRYPT 2015. 21st international conference on the theory and application of cryptology and information security, Auckland, New Zealand, November 29 – December 3, 2015. Proceedings. Part II. Berlin: Springer (ISBN 978-3-662-48799-0/pbk; 978-3-662-48800-3/ebook). Lecture Notes in Computer Science 9453, 236-261 (2015).
Summary: 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 = 0.5cm
For the entire collection see [Zbl 1327.94002].
- –
- 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.
- –
- 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.
For the entire collection see [Zbl 1327.94002].
MSC:
94A60 | Cryptography |