Garbling Gadgets for Boolean and Arithmetic Circuits
Garbling Gadgets for Boolean and Arithmetic Circuits
复制标题
用于布尔和算术电路的乱码小工具
DOI：
10.1145/2976749.2978410
复制
发表时间：
2016
期刊：
影响因子：
--
通讯作者：
Mike Rosulek
中科院分区：
文献类型：
--
作者：
Marshall Ball;T. Malkin;Mike Rosulek
我们提出了简单，实用，功能强大的新技术的乱码电路。这些技术的结果显着的具体和渐进的改进，在国家的最先进的，几种自然的计算。对于整数运算电路，我们的建设结果在乱码电路与自由加法，加权阈值门的成本独立于扇入，并通过一个固定的指数与成本独立的指数取幂。对于布尔电路，我们的结构给出了一个指数级的改善，超过了现有技术的阈值门（包括与/或门）的高扇入。我们的构造可以用实际的密钥原语（例如，AES），并且在与Free-XOR乱码方案（Kolesnikov & Schneider，ICALP 2008）类似的假设下被证明是安全的。我们给我们的计划和国家的最先进的乱码计划适用于布尔电路之间的广泛比较。
We present simple, practical, and powerful new techniques for garbled circuits. These techniques result in significant concrete and asymptotic improvements over the state of the art, for several natural kinds of computations. For arithmetic circuits over the integers, our construction results in garbled circuits with free addition, weighted threshold gates with cost independent of fan-in, and exponentiation by a fixed exponent with cost independent of the exponent. For boolean circuits, our construction gives an exponential improvement over the state of the art for threshold gates (including AND/OR gates) of high fan-in. Our construction can be efficiently instantiated with practical symmetric-key primitives (e.g., AES), and is proven secure under similar assumptions to that of the Free-XOR garbling scheme (Kolesnikov & Schneider, ICALP 2008). We give an extensive comparison between our scheme and state-of-the-art garbling schemes applied to boolean circuits.