TinyGarble: Highly Compressed and Scalable Sequential Garbled Circuits

By Ebrahim M. Songhori, Shehzeen Samarah Hussain, Ahmad-Reza Sadeghi, Thomas Schneider, Farinaz Koushanfar. 2015

236 citations recorded by the source corpus.

We introduce Tiny Garble, a novel automated methodology based on powerful logic synthesis techniques for generating and optimizing compressed Boolean circuits used in secure computation, such as Yao's Garbled Circuit (GC) protocol. Tiny Garble achieves an unprecedented level of compactness and scalability by using a sequential circuit description for GC. We introduce new libraries and transformations, such that our sequential circuits can be optimized and securely evaluated by interfacing with available garbling frameworks. The circuit compactness makes the memory footprint of the garbling operation fit in the processor cache, resulting in fewer cache misses and thereby less CPU cycles. Our proof-of-concept implementation of benchmark functions using Tiny Garble demonstrates a high degree of compactness and scalability. We improve the results of existing automated tools for GC generation by orders of magnitude, for example, Tiny Garble can compress the memory footprint required for 1024-bit multiplication by a factor of 4,172, while decreasing the number of non-XOR gates by 67%. Moreover, with Tiny Garble we are able to implement functions that have never been reported before, such as SHA-3. Finally, our sequential description enables us to design and realize a garbled processor, using the MIPS I instruction set, for private function evaluation. To the best of our knowledge, this is the first scalable emulation of a general purpose processor.

Subfields: Artificial Intelligence, Mechanical 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 Mechanical Engineering

Citations in the corpus

Privacy-Preserving Distributed Linear Regression on High-Dimensional Data (2017, methodology): “Popular applications used for the empirical evaluation of practical MPC systems include graph algorithms [5, 32, 42, 51, 57], data structure algorithms [42, 51], string matching and distance algorithms [36, 37, 66] and AES [3, 36, 37, 66].”
DeepSecure: Scalable Provably-Secure Deep Learning (2017, methodology): “We generate the netlists required for deep learning using logic synthesis tools with GC-optimized custom libraries as suggested in [7].”
Chameleon: A Hybrid Secure Computation Framework for Machine Learning Applications (2018, methodology): “ Oblivious Transfer and finally the security justification of Chameleon is given in §4.6. 4.1 GC and GMW Engines Chameleon’s implementation of the GC protocol is based on the methodology presented in [87]. Therefore, the input to the GC engine is the topologically sorted list of Boolean gates in the”
ObliVM: A Programming Framework for Secure Computation (2015, methodology): “Finally, in a concurrent work called TinyGarble [34], Songhori et al. show that by partially materializing a circuit, they can have a somewhat more global view of the circuit.”
Secure Linear Regression on Vertically Partitioned Datasets (2016, methodology): “Popular applications used for the empirical evaluation of implemented systems include graph algorithms [6, 18, 24, 29, 34, 45], data structure algorithms [24,29,42], string matching and distance algorithms [20,21,39] and AES [4,20,21,39].”
SoK: General Purpose Compilers for Secure Multi-Party Computation (2019, methodology): “Last major update EMP-toolkit [122] GC 2 09/2018 Obliv-C [129] GC 2 06/2018 ObliVM [97] GC 2 02/2016 TinyGarble [118] GC 2 10/2018 Wysteria [111] MC 2+ 10/2014 ABY [48] GC,MC 2 10/2018 SCALE-MAMBA - Hy 2+ 10/2018 Sharemind [24] Hy 3 09/2018 PICCO [134] Hy 3+ 10/2017 Frigate [101] 2+ - 05/2016 CBMC-G”
DeepAttest: An End-to-End Attestation Framework for Deep Neural Networks (2019, background): “Garbled Circuit (GC) is an alternative approach [38, 43] to HE which has smaller computation overhead but requires more communication.”
MP-SPDZ: A Versatile Framework for Multi-Party Computation (2020, methodology): “This framework only implements Yao’s garbled circuits with semi-honest security [71].”
A Pragmatic Introduction to Secure Multi-Party Computation (2019, methodology): “Cut-and-choose existed as a folklore technique in the cryptographic literature. Di erent cut-and-choose mechanisms were proposed by Mohassel and Franklin (2006) and Kiraz and Schoenmakers (2006), but without security proofs.”
ABY3: A Mixed Protocol Framework for Machine Learning (2018, methodology): “Alternatively, a size optimized circuit [59] or a depth optimized circuit[17] could be employed.”
Compacting privacy-preserving k-nearest neighbor search using logic synthesis (2015, methodology): “Our work is inspired by TinyGarble methodology [30].”
Generalizing the SPDZ Compiler For Other Protocols (2018, background): “In addition, the paradigm of working with static circuits is problematic for huge computations, due to the size of the circuit that must be dealt with (this issue has been considered in [29] and elsewhere, but can still be an issue).”
UnLynx: A Decentralized System for Privacy-Conscious Data Sharing (2017, background): “based on secret sharing (SS) [3, 14, 26, 49] or secure multiparty computation (SMPC) [11, 28, 33, 40, 42, 50] have intrinsic limitations in terms of control over data and scalability.”