Revisiting Garbled Circuits

What happens if a garbled circuit performs a computation on masked data creating masked output and the computation leaks to side channels? Theory says, it does not matter and it has strong points to bolster its claim. Friday, at CHES 2010, Thomas Schneider showed that garbled circuits made another step towards being practical in his talk "Garbled Circuits for Leakage-Resilience: Hardware Implementation and Evaluation of One-Time Programs". (The paper has been written by K. Järvinen, V. Kolesnikov, A.-R. Sadeghi and T. Schneider.)

Their first achievement is that they implemented two architectures to evaluate garbled circuits in a FPGA and thus have the first timing data for garbled circuits on hardware. They obtained their performance figures for a garbled circuit computing AES. It still is rather slow compared to conventionally protected implementations but it is substantially faster than the currently best software implementation.

But they also achieve to make the output verifiable. To do this, they basically wrap a n-out-of-n secret sharing scheme around the garbled circuit. The shares traverse through the circuit and any manipulation of the computation destroys at least one share. In the end, the result is only unmasked if the secret can be reconstructed. The secret sharing has, just like the masking and unmasking of the data, to happen inside trusted hardware. This trusted hardware may be tamper proof devices but one can also imagine a scenario where the trusted hardware is your own computer while you outsource the heavy workload computation to rented, untrusted hardware.