Adaptively Secure Garbled Circuits from One-Way Functions

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. In many settings, the circuit can be garbled off-line without strict efficiency constraints, but the input must be garbled very efficiently on-line, with much lower complexity than evaluating the circuit. Yao's garbling schemei?ź[31] has essentially optimal on-line complexity, but only achieves selective security, where the adversary must choose the input x prior to seeing the garbled circuit. It has remained an open problem to achieve adaptive security, where the adversary can choose x after seeing the garbled circuit, while preserving on-line efficiency. In this work, we modify Yao's scheme in a way that allows us to prove adaptive security under one-way functions. In our main instantiation we achieve on-line complexity only proportional to the width w of the circuit. Alternatively we can also get an instantiation with on-line complexity only proportional to the depth d and the output size of the circuit, albeit incurring in a $$2^{Od}$$ security loss in our reduction. More broadly, we relate the on-line complexity of adaptively secure garbling schemes in our framework to a certain type of pebble complexity of the circuit. As our maini?źtool, of independent interest, we develop a new notion of somewhere equivocal encryption, which allows us to efficiently equivocate on a small subset of the message bits.

混淆方案用于以一种能揭示输出$C(x)$但隐藏其他所有信息的方式混淆电路$C$和输入$x$。在许多情况下，电路可以在没有严格效率限制的情况下离线混淆，但输入必须在线非常高效地混淆，其复杂度要比评估电路低得多。姚氏混淆方案[31]具有基本最优的在线复杂度，但仅实现了选择安全性，即攻击者必须在看到混淆电路之前选择输入$x$。在保持在线效率的同时实现自适应安全性（即攻击者在看到混淆电路之后可以选择$x$）一直是一个未解决的问题。 在这项工作中，我们以一种能够在单向函数下证明自适应安全性的方式修改了姚氏方案。在我们的主要实例中，我们实现的在线复杂度仅与电路的宽度$w$成正比。或者，我们也可以得到一个在线复杂度仅与电路的深度$d$和输出大小成正比的实例，尽管在我们的归约中会有$2^{Od}$的安全性损失。更广泛地说，我们将我们框架中自适应安全混淆方案的在线复杂度与电路的某种 pebble复杂度相关联。作为我们具有独立研究价值的主要工具，我们提出了一种新的“某处含糊加密”概念，它使我们能够有效地对消息比特的一个小子集进行含糊处理。