@inproceedings{HMSG13,
 author = {Husted, Nathaniel and Myers, Steven and Shelat, Abhi and Grubbs, Paul},
 title = {GPU and CPU Parallelization of Honest-but-curious Secure Two-party Computation},
 booktitle = {ACSAC'13},
 year = {2013},
 pages = {169--178},
 numpages = {10},
} 

PDF

Recent work demonstrates the feasibility and practical use of secure two-party computation~\cite{frederiksen2012fast,huang2012quid,kreuter2012billion,pu2011fastplay}.
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.

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.