Paper 2016/685

Overlaying Circuit Clauses for Secure Computation

W. Sean Kennedy, Vladimir Kolesnikov, and Gordon Wilfong

Abstract

Given a set S = {C_1,...,C_k } of Boolean circuits, we show how to construct a universal for S circuit C_0, which is much smaller than Valiant’s universal circuit or a circuit incorporating all C_1,...,C_k. Namely, given C_1,...,C_k and viewing them as directed acyclic graphs (DAGs) D_1,...,D_k, we embed them in a new graph D_0. The embedding is such that a GC garbling of any of C_1,...,C_k could be implemented by a corresponding garbling of a circuit corresponding to D_0. 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.

Note: slightly changed flow for clarity

Metadata
Available format(s)
PDF
Publication info
Preprint.
Keywords
set-universal circuitsecure computationgarbled circuitGMW
Contact author(s)
kolesnikov @ research bell-labs com
History
2016-10-20: revised
2016-07-12: received
See all versions
Short URL
https://ia.cr/2016/685
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2016/685,
      author = {W.  Sean Kennedy and Vladimir Kolesnikov and Gordon Wilfong},
      title = {Overlaying Circuit Clauses for Secure Computation},
      howpublished = {Cryptology ePrint Archive, Paper 2016/685},
      year = {2016},
      note = {\url{https://eprint.iacr.org/2016/685}},
      url = {https://eprint.iacr.org/2016/685}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.