International Association
for Cryptologic Research

We introduce a new technique, component-based garbled circuits, for increasing the efficiency of secure two-party computation in the offline/online semi-honest setting. We observe that real-world functions are generally constructed in a modular way, comprising many standard components such as arithmetic operations and other common tasks. Our technique allows circuits for these common tasks to be garbled and shared during an offline phase; once the function to compute is specified, these pre-shared components can be chained together to create a larger garbled circuit. We stress that we do not assume that the function is known during the offline phase — only that it uses some common, predictable components.

Improving on the above technique, we give a second method of chaining, which we call single communication multiple connections chaining, which allows blocks of consecutive wires holding multi-bit pieces of data to be connected between components with only a single transmitted wire label. This means that connecting components requires minimal communication.

Finally, we give an implementation, CompGC, of these techniques and measure the efficiency gains for various examples. We find that our techniques result in roughly an order of magnitude performance improvement over standard garbled circuit-based secure two-party computation.