We show how to improve Garbled Circuit (GC) and GMW-based secure function evaluation (SFE) of circuits with if/switch clauses using such S-universal circuit.
The most interesting case here is the application to the GMW approach. We provide a novel observation that in GMW the cost of processing a gate is almost the same for 5 (or more) Boolean inputs, as it is for the usual case of 2 Boolean inputs. While we expect this observation to greatly improve general GMW-based computation, in our context this means that GMW gates can be programmed almost for free, based on the secret-shared programming of the clause.
Our approach naturally and cheaply supports nested clauses. Our algorithm is a heuristic; we show that solving the circuit embedding problem is NP-hard. Our algorithms are in the semi-honest model and are compatible with Free-XOR.
We report on experimental evaluations and discuss achieved performance in detail. For 32 diverse circuits in our experiment, our construction results 6.1x smaller circuit than prior techniques.Category / Keywords: set-universal circuit, secure computation, garbled circuit, GMW Date: received 7 Jul 2016, last revised 20 Oct 2016 Contact author: kolesnikov at research bell-labs com Available format(s): PDF | BibTeX Citation Note: slightly changed flow for clarity Version: 20161020:131812 (All versions of this report) Short URL: ia.cr/2016/685 Discussion forum: Show discussion | Start new discussion