Efficient Garbling from a Fixed-Key Blockcipher

By Mihir Bellare, Viet Tung Hoang, Sriram Keelveedhi, Phillip Rogaway. 2013

355 citations recorded by the source corpus.

We advocate schemes based on fixed-key AES as the best route to highly efficient circuit-garbling. We provide such schemes making only one AES call per garbled-gate evaluation. On the theoretical side, we justify the security of these methods in the random-permutation model, where parties have access to a public random permutation. On the practical side, we provide the Just Garble system, which implements our schemes. Just Garble evaluates moderate-sized garbled-circuits at an amortized cost of 23.2 cycles per gate (7.25 nsec), far faster than any prior reported results.

Subfields: Artificial Intelligence, Computer Vision and Pattern Recognition, Electrical and Electronic Engineering

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 Computer Vision and Pattern Recognition

In Electrical and Electronic Engineering

Citations in the corpus

Privacy-Preserving Distributed Linear Regression on High-Dimensional Data (2017, methodology): “Obliv-C includes an implementation of Yao’s garbled circuit protocol that incorporates recent optimizations including free XOR [44], garbled row reduction [56], fixed key block ciphers [3], and half gates [73].”
Prio: Private, Robust, and Scalable Computation of Aggregate Statistics (2017, background): “That said, there have been great advances in practical general-purpose MPC protocols of late [12,13,23,45,46,73,89,91,93,98].”
DeepSecure: Scalable Provably-Secure Deep Learning (2017, methodology): “Each row is the encryption of the correct output key using two input labels as the encryption key [13].”
Gazelle: A Low Latency Framework for Secure Neural Network Inference (2018, methodology): “Our garbling scheme is an extension of the one presented in JustGarble [3] which we modify to also incorporate the Half-Gates optimization [41].”
Chameleon: A Hybrid Secure Computation Framework for Machine Learning Applications (2018, methodology): “ wire w in the circuit, Alice generates and assigns two random k-bit strings, called labels, X w 0 and X1 w representing 0 and 1 Boolean values where k is a security parameter, usually set to k = 128 [14]. Next, she encrypts the output labels of a gate using the two corresponding input labels as the”
Server-Aided Secure Computation with Off-line Parties (2017, methodology): “We used JustGarble [9], a state-of-the-art tool with excellent performance for circuit garbling and evaluation.”
SecureML: A System for Scalable Privacy-Preserving Machine Learning (2017, methodology): “It implements the OT extension of [11], and applies free XOR [30] and fixed-key AES garbling [12] optimizations for garbled circuits.”
Scalable Private Set Intersection Based on OT Extension (2018, methodology): “An instantiation of the CRF in Yao’s garbled circuit protocol which uses ﬁxed-key AES and greatly improves performance was proposed in [Bellare et al. 2013] and reﬁned in [Zahur et al. 2015] for use in the half-gates scheme.”
XONN: XNOR-based Oblivious Deep Neural Network Inference (2019, methodology): “[32] have provided a way to perform garbling using efficient fixed-key AES encryption.”
GraphSC: Parallel Secure Computation Made Easy (2015, methodology): “We expect that the garbling and evaluation CPU will reduce noticeably if hardware AESNI were employed [76].”
BlindBox: Deep Packet Inspection over Encrypted Traffic (2015, background): “Since typical clients are not running in the same rack over a 10GbE links, in some experiments we reduced throughput to 20Mbps (typical of a broadband home link) and increased latency to 10ms RTT.”
Faster Secure Two-Party Computation in the Single-Execution Setting (2017, methodology): “We adopted most of the recent advances in the field [5,39,4,8,29] as well as the optimizations introduced in §4.”
More efficient oblivious transfer and extensions for faster secure computation (2013, background): “, [6,7,10,15,17,25,28,35,41–43,50,57], this conjecture has proven to be wrong and it is possible to carry out secure computation of complex functions at speeds that five years ago would have been unconceivable.”
Garbling Gadgets for Boolean and Arithmetic Circuits (2016, background): “A considerable amount of work [5, 16, 14, 18, 6, 13, 21, 11] has been dedicated to reducing the cost of garbled circuits since Yao’s seminal construction.”
Combining Secret Sharing and Garbled Circuits for Efficient Private IEEE 754 Floating-Point Computations (2015, neutral): “Recent garbling schemes already bring the cost of local computations to a minimum as demonstrated in [4].”
SoK: General Purpose Compilers for Secure Multi-Party Computation (2019, background): “The garbled circuit implementation in TinyGarble is a strict improvement over JustGarble, including recent protocol and circuit optimizations.”
ABY - A Framework for Efficient Mixed-Protocol Secure Two-Party Computation (2015, methodology): “For Arithmetic sharing (§III-A4) we generate multiplication triples via Paillier with packing [62], [66] or DGK with full decryption [22], [32], for Boolean sharing (§III-B) we use the multiplexer of [54] and OT extension [1], [41], and for Yao sharing (§III-C) we use fixed-key AES garbling [7].”
Fast Garbling of Circuits Under Standard Assumptions (2015, methodology): “AES-NI offers instructions for encryption/decryption and for the AES key expansion.”