Lower Bounds on Assumptions Behind Indistinguishability Obfuscation
Lower Bounds on Assumptions Behind Indistinguishability Obfuscation
复制标题
不可区分性混淆背后的假设下限
DOI：
10.1007/978-3-662-49096-9_3
复制
发表时间：
2016
期刊：
影响因子：
--
通讯作者：
Abhi Shelat
中科院分区：
文献类型：
--
作者：
Mohammad Mahmoody;Ameer Mohammed;Soheil Nematihaji;R. Pass;Abhi Shelat
自 Garg 等人的开创性工作以来。在 FOCS'13 中，他们提出了第一个不可区分性混淆的候选结构 iO，简称 iO，它已成为具有众多应用的核心密码原语。 Garg 等拟议建设的安全性。及其变体基于多线性映射 Garg 等人进行了证明。 Eurocrypt'13 及其理想化模型称为分级编码模型 Brakerski 和 Rothblum TCC'14 和 Barak 等人。 Eurocrypt'14。 iO 是否可以基于标准且经过充分研究的硬度假设仍然是一个难以捉摸的悬而未决的问题。
在这项工作中，我们基于计算假设，以黑盒方式证明了暗示 iO 的假设下限。请注意，iO 的任何下限都需要以某种方式依赖于计算假设，因为如果 $$\mathbf {P}= \mathbf {NP}$$ 则统计上安全的 iO 确实存在。我们的结果是双重的：
1.除非多项式层次结构崩溃，否则不存在由指数级安全防碰撞哈希函数完全黑盒构建的 iO。我们的下界扩展到以黑盒方式将 iO 与随机预言所隐含的任何原语分开。 2.令 $${\mathcal P}$$ 是相对于随机陷门排列存在的任何原语，任何有限阿贝尔群的通用群模型，或任何有限环的 O1 度分级编码模型。我们证明，从 $${\mathcal P}$$ 实现 iO 的黑盒构造与基于单向函数的公钥密码学一样困难。特别是，对于任何这样的原语 $${\mathcal P}$$，我们提出了一种构造性的过程，该过程从 $${\mathcal P}$$ 中获取 iO 的任何黑盒构造，并将其转换为任何单向函数的语义安全公钥加密的构造。即使 $${\mathcal P}$$ 的 iO 构造是半黑盒 Reingold、Trevisan 和 Vadhan、TCC'04，我们的分离仍然成立，并且安全性降低可以以非黑盒方式访问对手。
Since the seminal work of Garg eti¾?al. FOCS'13 in which they proposed the first candidate construction for indistinguishability obfuscation iO for short, iO has become a central cryptographic primitive with numerous applications. The security of the proposed construction of Garg eti¾?al. and its variants are proved based on multi-linear maps Garg eti¾?al. Eurocrypt'13 and their idealized model called the graded encoding model Brakerski and Rothblum TCC'14 and Barak eti¾?al. Eurocrypt'14. Whether or not iO could be based on standard and well-studied hardness assumptions has remain an elusive open question.
In this work we prove lower bounds on the assumptions that imply iO in a black-box way, based on computational assumptions. Note that any lower bound for iO needs to somehow rely on computational assumptions, because if $$\mathbf {P}= \mathbf {NP}$$ then statistically secure iO does exist. Our results are twofold:
1.There is no fully black-box construction of iO from exponentially secure collision-resistant hash functions unless the polynomial hierarchy collapses. Our lower bound extends to separate iO from any primitive implied by a random oracle in a black-box way.2.Let $${\mathcal P}$$ be any primitive that exists relative to random trapdoor permutations, the generic group model for any finite abelian group, or degree-O1 graded encoding model for any finite ring. We show that achieving a black-box construction of iO from $${\mathcal P}$$ is as hard as basing public-key cryptography on one-way functions. In particular, for any such primitive $${\mathcal P}$$ we present a constructive procedure that takes any black-box construction of iO from $${\mathcal P}$$ and turns it into a construction of semantically secure public-key encryption form any one-way functions. Our separations hold even if the construction of iO from $${\mathcal P}$$ is semi-black-box Reingold, Trevisan, and Vadhan, TCC'04 and the security reduction could access the adversary in a non-black-box way.