TY - GEN
T1 - Garbling gadgets for boolean and arithmetic circuits
AU - Ball, Marshall
AU - Malkin, Tal
AU - Rosulek, Mike
N1 - Publisher Copyright:
© 2016 Copyright held by the owner/author(s). Publication rights licensed to ACM.
PY - 2016/10/24
Y1 - 2016/10/24
N2 - 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 stateof-the-art garbling schemes applied to boolean circuits.
AB - 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 stateof-the-art garbling schemes applied to boolean circuits.
UR - http://www.scopus.com/inward/record.url?scp=84995466556&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=84995466556&partnerID=8YFLogxK
U2 - 10.1145/2976749.2978410
DO - 10.1145/2976749.2978410
M3 - Conference contribution
AN - SCOPUS:84995466556
T3 - Proceedings of the ACM Conference on Computer and Communications Security
SP - 565
EP - 577
BT - CCS 2016 - Proceedings of the 2016 ACM SIGSAC Conference on Computer and Communications Security
PB - Association for Computing Machinery
T2 - 23rd ACM Conference on Computer and Communications Security, CCS 2016
Y2 - 24 October 2016 through 28 October 2016
ER -