Paper 2016/969

Garbling Gadgets for Boolean and Arithmetic Circuits

Marshall Ball, Tal Malkin, and Mike Rosulek

Abstract

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 {\em 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 {\em 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.

Metadata
Available format(s)
PDF
Category
Cryptographic protocols
Publication info
Published elsewhere. Minor revision. ACM CCS 2016
DOI
10.1145/2976749.2978410
Keywords
garbled circuitssecure computationarithmetic circuits
Contact author(s)
rosulekm @ eecs oregonstate edu
History
2016-10-10: received
Short URL
https://ia.cr/2016/969
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2016/969,
      author = {Marshall Ball and Tal Malkin and Mike Rosulek},
      title = {Garbling Gadgets for Boolean and Arithmetic Circuits},
      howpublished = {Cryptology ePrint Archive, Paper 2016/969},
      year = {2016},
      doi = {10.1145/2976749.2978410},
      note = {\url{https://eprint.iacr.org/2016/969}},
      url = {https://eprint.iacr.org/2016/969}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.