Adaptive Security of Yao's Garbled Circuits
Adaptive Security of Yao's Garbled Circuits
复制标题
Yao的乱码电路的自适应安全
DOI：
--
复制
发表时间：
2016
期刊：
影响因子：
--
通讯作者：
Daniel Wichs
中科院分区：
文献类型：
--
作者：
Zahra Jafargholi;Daniel Wichs
乱码方案用于以一种方式乱码电路C和输入x，该方式显示输出Cx但隐藏其他一切。Yao在80年代的构造被认为是实现选择性安全的，其中对手一次性选择电路C和输入x。它仍然是一个悬而未决的问题，该结构是否也实现了自适应安全性，其中对手可以在看到电路C的乱码版本后选择输入x。
Hemenway等人最近的一项工作修改了Yao的构造，并表明所得到的方案是自适应安全的。这是通过用一种特殊类型的“某处模糊加密”加密来自姚构造的乱码电路并将密钥与乱码输入一起给出来完成的。该方案的效率和安全损失的减少是通过一定的卵石游戏在电路上捕获。
在这项工作中，我们证明了姚明的建设本身已经是自适应安全的，安全损失可以被捕获相同的卵石游戏。例如，我们表明，对于深度为d的电路，我们的减少的安全损失是$2 ^{Od}$$2Od，这意味着姚的建设是自适应安全的NC 1电路，而不需要复杂性杠杆。我们的技术受到Fuchsbauer等人的“嵌套杂交”的启发。Asiacrypt'14，Asiacrypt'15，并依赖于一个仔细的杂交序列，其中每个杂交都涉及对对手的适应性选择的一些有限的猜测。虽然它不匹配Hemenway等人实现的参数。在他们的全部一般性，我们的工作的主要优点是证明姚的建设是安全的，没有任何额外的加密层。
A garbling scheme is used to garble a circuit C and an input x in a way that reveals the output Cx but hides everything else. Yao's construction from the 80's is known to achieve selective security, where the adversary chooses the circuit C and the input x in one shot. It has remained as an open problem whether the construction also achieves adaptive security, where the adversary can choose the input x after seeing the garbled version of the circuit C.
A recent work of Hemenway et al. CRYPTO'16 modifies Yao's construction and shows that the resulting scheme is adaptively secure. This is done by encrypting the garbled circuit from Yao's construction with a special type of "somewhere equivocal encryption" and giving the key together with the garbled input. The efficiency of the scheme and the security loss of the reduction is captured by a certain pebbling game over the circuit.
In this work we prove that Yao's construction itself is already adaptively secure, where the security loss can be captured by the same pebbling game. For example, we show that for circuits of depth d, the security loss of our reduction is $$2^{Od}$$ 2Od, meaning that Yao's construction is adaptively secure for NC1 circuits without requiring complexity leveraging. Our technique is inspired by the "nested hybrids" of Fuchsbauer et al. Asiacrypt'14, CRYPTO'15 and relies on a careful sequence of hybrids where each hybrid involves some limited guessing about the adversary's adaptive choices. Although it doesn't match the parameters achieved by Hemenway et al. in their full generality, the main advantage of our work is to prove the security of Yao's construction as is, without any additional encryption layer.