Improved Garbled Circuit: Free XOR Gates and Applications

By Vladimir Kolesnikov, Thomas Schneider. 2008

851 citations recorded by the source corpus.

Subfields: Artificial Intelligence, Computer Networks and Communications, Privacy & Security

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 Networks and Communications

In Privacy & Security

Citations in the corpus

QUOTIENT: Two-Party Secure Neural Network Training and Prediction (2019, methodology): “The relevant observation to our work is the fact that the running time of a Garbled Circuits protocol is a function of the number of non-XOR gates in a circuit (this is thanks to the Free-XOR technique [32]).”
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].”
Privacy-Preserving Ridge Regression on Hundreds of Millions of Records (2013, methodology): “First, the communication and computation cost for XOR gates in the circuit is significantly reduced using the " free XOR " technique [24].”
DeepSecure: Scalable Provably-Secure Deep Learning (2017, methodology): “Following the Free-XOR optimization [15], the XOR gates are almost free of cost and the garbled table needs to be generated and transferred only for the non-XOR gates.”
Chameleon: A Hybrid Secure Computation Framework for Machine Learning Applications (2018, methodology): “its and created the .scdfiles for many primitive functions. A user can simply use these circuits by calling regular functions in the C++language. We include most recent optimizations for GC: Free XOR [55], fixed-key AES garbling [14], Half Gates [90], and sequential circuit garbling [87]. Our implem”
Trident: Efficient 4PC Framework for Privacy Preserving Machine Learning (2019, methodology): “We incorporate the recent optimisations including free XOR [?], [44], [45], half-gates [46], [47], fixed-key AES garbling [48].”
Privacy-preserving matrix factorization (2013, methodology): “Further additional optimizations, including reusing sorting results, and implementing operations via free xor gates [34], allow us to run matrix factorization over 10(4) ratings within a few hours.”
Fully Key-Homomorphic Encryption, Arithmetic Circuit ABE and Compact Garbled Circuits (2014, methodology): “The ﬁrst is the “free XOR” optimization for single-use garbling schemes introduced by Kolesnikov and Schneider [KS08] where one produces garbled tables only for the AND gates in the circuit C .”
Quid-Pro-Quo-tocols: Strengthening Semi-honest Protocols with Dual Execution (2012, methodology): “…technique that allows the circuit evaluator to decrypt only a single entry (rather than all four) in a garbled gate [29]; the free-XOR technique [23] that allows XOR gates to be executed without any encryption operations; Garbled Row Reduction (GRR) [34] that reduces the size of a garbled gate…”
Optimized Honest-Majority MPC for Malicious Adversaries — Breaking the 1 Billion-Gate Per Second Barrier (2017, neutral): “See [15], [18], [8], [14], [9], [19], [4], [17], [24], [20], [26], [16], [23] for just some examples.”
A New Approach to Practical Active-Secure Two-Party Computation (2012, methodology): “On the other hand, there is a growing interest in understanding the practical overhead of secure computation, and several works have perfected and implemented protocols based on Yao’s garbled circuits [28,3,26,23,30,31,16,27,25,1,17], protocols based on homomorphic encryption [21,10,22,4] and protoc”
Faster Secure Two-Party Computation in the Single-Execution Setting (2017, methodology): “Our implementation of garbled circuits uses all recent optimizations [22,32,5,21,39].”
Fast and Secure Three-party Computation: The Garbled Circuit Approach (2015, methodology): “First, we enable the free-XOR support [KS08] in JustGarble and also modify its code to make NOT gates free (no communication and computation) since the original JustGarble implementation treats NOT gates like other non-XOR gates.”
Secure Function Evaluation Using an FPGA Overlay Architecture (2017, methodology): “Free-xor signiﬁcantly reduces the computational cost of garbled xor gates. xor gates do not need to be encrypted and decrypted, as the xor output wire key is computed through an xor of the corresponding input keys.”
Secure two-party computations in ANSI C (2012, methodology): “This capability forms the basis for the compiler which we describe in the next section.”