2013 · 46 citations · 15 references
ComputingComputer EngineeringComputer ScienceComputer SecurityCryptographyParallel ComputingGraphics Processing Unit ComputingGraphics Processing UnitsHardware AccelerationParallel ArchitecturesParallel Computing SystemsSecure Multi-party ComputationGpu ArchitectureParallel Computing ArchitecturesParallelizationSecure Multiparty ComputationSimd ArchitecturesSimd ExecutionSimd ParallelismYao's Garbled Circuits
Recent work demonstrates the feasibility and practical use of secure two-party computation [5, 9, 15, 23]. In this work, we present the first Graphical Processing Unit (GPU)-optimized implementation of an optimized Yao's garbled-circuit protocol for two-party secure computation in the honest-but-curious and 1-bit-leaked malicious models. We implement nearly all of the modern protocol advancements, such as Free-XOR, Pipelining, and OT extension. Our implementation is the first allowing entire circuits to be generated concurrently, and makes use of a modification of the XOR technique so that circuit generation is optimized for implementation on SIMD architectures of GPUs. In our best cases we generate about 75 million gates per second and we exceed the state of the art performance metrics on modern CPU systems by a factor of about 200, and GPU systems by about a factor of 2.3. While many recent works on garbled circuits exploit the embarrassingly parallel nature of many tasks that are part of a secure computation protocol, we show that there are still various forms and levels of parallelization that may yet improve the performance of these protocols. In particular, we highlight that implementations on the SIMD architecture of modern GPUs require significantly different approaches than the general purpose MIMD architecture of multi-core CPUs, which again differ from the needs of parallelizing on compute clusters. Additionally, modifications to the security models for many common protocols have large effects on reasonable parallel architectures for implementation.
15
How to generate and exchange secrets
Andrew Chi-Chih Yao · 1986 · 3.7K citations
IEEE Software · 2011 · 2K citations
Fairplay—a secure two-party computation system
Dahlia Malkhi, Noam Nisan, Benny Pinkas et al. · 2004 · 782 citations
A Proof of Security of Yao’s Protocol for Two-Party Computation
Yehuda Lindell, Benny Pinkas · Journal of Cryptology · 2008 · 655 citations · Full text