Parallel Implementation of GC-Based MPC Protocols in the Semi-Honest Setting

Parallel computing offers the chance of improving the efficiency of Garbled Circuit technique in multi-party computation protocols. We propose two different types of parallelization: fine-grained, based on the parallel evaluation of gates, and coarse grained, based on the parallelization of macro-blocks. To analyze the efficiency of parallel implementation, a biometric scenario, having an intrinsically parallel nature, is considered. Moreover our approach is compared to previous works by using a privacy preserving implementation of AES encryption. We show that both fine-grained and coarse-grained solutions provide significant runtime improvements. Better results are obtained by the coarse-grained parallelization, which, however, can be exploited only when the same block is used more than once in parallel, whereas fine-grained parallelization can be applied to any garbled circuit.