Two Halves Make a Whole - Reducing Data Transfer in Garbled Circuits Using Half Gates

By Samee Zahur, Mike Rosulek, David E. Evans. 2015

368 citations recorded by the source corpus.

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

1. David E. Evans
2. Adrià Gascón
3. Thomas Schneider
4. Farinaz Koushanfar
5. Jonathan Katz
6. Mike Rosulek
7. Marcel Keller
8. Mariana Raykova

In Computational Theory and Mathematics

1. David E. Evans
2. Thomas Schneider
3. Jonathan Katz
4. Mike Rosulek
5. Xiao Shaun Wang
6. Kim Laine
7. Yehuda Lindell
8. Yan Huang

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].”
• DeepSecure: Scalable Provably-Secure Deep Learning (2017, methodology): “There are several optimizations for the GC protocol including Free-XOR [10], Row Reduction [11], Half Gates [12], and Fixed-Key Cipher [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): “We include most recent optimizations for GC: Free XOR [52], fixed-key AES garbling [14], Half Gates [84], and sequential circuit garbling [81].”
• Garbling Gadgets for Boolean and Arithmetic Circuits (2016, methodology): “The numbers in the table reflect the cost to garble each such subcircuit using the state-of-the art half-gates garbling scheme [21].”
• Circuit ORAM: On Tightness of the Goldreich-Ostrovsky Lower Bound (2015, methodology): “When the bandwidth is 20Mbps, we use the halfgate optimization [60] instead.”
• 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].”
• ABY2.0: Improved Mixed-Protocol Secure Two-Party Computation (2020, methodology): “Using the half-gates technique [99], this has setup communication of 2`κ bits.”
• ObliVM: A Programming Framework for Secure Computation (2015, background): “Besides general types, ObliVM-lang also supports generic constants to further improve the reusability.”
• TinyGarble: Highly Compressed and Scalable Sequential Garbled Circuits (2015, methodology): “Beside user’s manual optimization, TinyGarble performs various optimizations through standard HDL synthesis tools to generate an optimized netlist, i.e., list of gates, which is then transformed to be used with a GC protocol implementation, e.g., JustGarble [2] or Half Gates [72].”
• A Pragmatic Introduction to Secure Multi-Party Computation (2019, methodology): “1See Zahur et al. (2015) for a precise formulation of this class.”
• Scalable Private Set Intersection Based on OT Extension (2018, methodology): “An instantiation of the CRF in Yao’s garbled circuit protocol which uses fixed-key AES and greatly improves performance was proposed in [Bellare et al. 2013] and refined in [Zahur et al. 2015] for use in the half-gates scheme.”
• 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.”