Garbling Gadgets for Boolean and Arithmetic Circuits

By Marshall Ball, Tal Malkin, Mike Rosulek. 2016

80 citations recorded by the source corpus.

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.

Subfields: Artificial Intelligence, Computational Theory and Mathematics

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Computational Theory and Mathematics

Citations in the corpus

Secure Evaluation of Quantized Neural Networks (2019, methodology): “A different approach is taken by Ball et al. [2] where the authors use the arithmetic garbling technique of Ball et al. [3] to evaluate Neural Networks.”
A Pragmatic Introduction to Secure Multi-Party Computation (2019, background): “, 2016), using high fan-in gates (Ball et al., 2016) and larger lookup tables (Dessouky et al.”