Improved Garbled Circuit Building Blocks and Applications to Auctions and Computing Minima

By Vladimir Kolesnikov, Ahmad-Reza Sadeghi, Thomas Schneider. 2009

286 citations recorded by the source corpus.

Subfields: Artificial Intelligence, Computational Theory and Mathematics, Information Systems

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 Computational Theory and Mathematics

In Information Systems

Citations in the corpus

Privacy-Preserving Ridge Regression on Hundreds of Millions of Records (2013, background): “Finally, the last optimization is the succinct " addition of 3 bits " circuit [27], which defines a circuit with four XOR gates (all of which are " free " in terms of communication and computation) and just one AND gate.”
Efficient Privacy-Preserving Biometric Identification (2011, methodology): “In contrast to the work of [8], we only need to compute the minimum value rather than the index of the minimum value.”
ABY2.0: Improved Mixed-Protocol Secure Two-Party Computation (2020, methodology): “For this, parties arrange the n values into an N-ary tree (tournament) composed of MAXN blocks with depth logN(n) and evaluate in a top-down fashion [64].”
InnerCircle: A parallelizable decentralized privacy-preserving location proximity protocol (2015, methodology): “Results using these three distance functions are combined with both the inequality function from Erkin et l. [8], and using garbled circuits using a technique from a work by Kolesnikov et al. [17].”
Secure Computation on Floating Point Numbers (2013, background): “While it is well known that any computable function can be evaluated securely (e.g., as a Boolean or arithmetic circuit), recently a substantial amount of literature (see, e.g., [19], [20], [32] among many others) has been dedicated to optimizing secure realizations of commonly used operations.”
Secure two-party computations in ANSI C (2012, background): “This capability forms the basis for the compiler which we describe in the next section.”
Automated Synthesis of Optimized Circuits for Secure Computation (2015, background): “Their circuit sizes and depths are equivalent to the hand-optimized circuits in [HEK12, SZ13]: ripple-carry adder and subtractor [BPP00, KSS09], n × (cid:96) -bit carry-save and ripple-carry network adders [Sav97, SZ13], multipliers and squar-ers [Sav97, KSS09, SZ13], depth-optimized multiplexer…”
More efficient oblivious transfer and extensions for faster secure computation (2013, unknown): “Using the minimum circuit construction of [31], our circuit has 2 (cid:96)N − 2 (cid:96) ≈ 40 , 000 , 000 AND gates and the client has N 2 = 10 , 000 , 000 input bits.”
TinyGarble: Highly Compressed and Scalable Sequential Garbled Circuits (2015, background): “The comparison function can be implemented in N steps of subtraction by keeping the carry bit [43].”
Faster Secure Two-Party Computation Using Garbled Circuits (2011, background): “Since XOR gates are free and an k -bit Adder needs only k non-XOR gates [17], the Hamming circuit with the na¨ıve Counter needs (cid:96) · (cid:100) log (cid:96) (cid:101) non-free gates.”
Privacy-Preserving ECG Classification With Branching Programs and Neural Networks (2011, background): “Subsequently, the system classifies ECG portions corresponding to single heart beats into six possible classes: five possible diseases and one healthy state (see Section II).”
Compacting privacy-preserving k-nearest neighbor search using logic synthesis (2015, methodology): “• Reduction in the size of the required memory for GC from O ( nw ) to O ( w ) compared with the best known GC implementation of 1-NN [17].”
Private Set Intersection: Are Garbled Circuits Better than Custom Protocols? (2012, methodology): “This design uses 4σ non-free binary gates to sort two σ -bit numbers, since the MIN and MAX circuits each use 2σ non-free gates [25].”
Privacy-preserving matrix factorization (2013, background): “FastGC also provides an “addition of 3 bits” circuit [33], enabling additions with 4 “free” xor gates and one and gate.”
Efficient Secure Computation with Garbled Circuits (2011, methodology): “The free-XOR technique [35, 36] realizes all XOR gates by just XOR-ing the input wire labels, without needing any encryption operations.”
Efficient Privacy-Preserving Face Recognition (2009, unknown): “As shown in [20], these GC based protocols clearly outperform comparison protocols based on homomorphic encryption [13,6,14,9,10].”
ABY - A Framework for Efficient Mixed-Protocol Secure Two-Party Computation (2015, methodology): “edu/libpaillier/ constructions described in [45], [54], [69].”