Two papers by Yan Huang, Jonathan Katz, Vladimir Kolesnikov, Ranjit Kumaresan, Alex J. Malozemoff and Yehuda Lindell, Ben Riva respectively
Blog written by Roberto Trifiletti
The second talk of the last session of CRYPTO14 was presented by Ranjit Kumaresan who presented two merged independent works on how to amortize the construction of garbled circuits for the batch/multiple execution setting. Additionally the work [LR14] consider the online/offline paradigm for secure computation and try to push as much of the computation as possible to the offline phase. Both works are motivated by the fact that practice shows that 99.999% of the cost of implemented protocols is due to the number of garbled circuits, so any reduction in the replication factor will have great performance implications. To get an idea of where the state of the art is Ranjit summarized the last couple of years improvements in the replication factor for achieving security $2^-40$:
– 680 [LP07]
– 128 [LP11]
– 125 [sS11]
– 48 [HKE]
– 40 [Lin13]
It seems inherent that one cannot go under 40 circuits for achieving security $2-40$, at least in a general setting where one garbles entire circuits. However, both works were inspired by the LEGO approach[NO09] which works slightly different than standard garbled circuits approaches. For a brief summary, the LEGO approach first garbles a large number of gates independent of the function to be evaluated and performs cut-and-choose on the gate level. Then at a later stage the wires of the remaining gates are soldered together to form buckets which now compose the desired circuit. For each bucket the output key is taken as the majority. Because of this the LEGO approach only requires a replication factor of O(s/log |C|) for security $2^-s$, meaning LEGO only gets more efficient the more gates you garble.
By restricting the setting to that of multiple execution (or batch setting) both [HKKKM14] and [LR14] are able to benefit from the above LEGO approach. Here the task is to evaluate the same function a number of times (on different inputs), which results in (amortized) much better replication factors than for a single execution. In both works one can think of each of the garbled circuits produced as a garbled gate in the LEGO setting. Thus the constructor garbles a lot of circuits for the same function f and the receiver performs cut-and-choose on these as usual. Next the receiver partitions the remaining garbled circuits into execution sets, where each set can be thought of as a soldered bucket in the LEGO setting. By using the forge-and-loose protocol of [L13], only a single circuit in each set is required to be correct which even further reduces the replication factor. Loosely, the forge-and-loose approach [B13, HKE13, L13] guarantees that if two circuits (on the same input) differ in output, then the receiver can extract the senders input and thereby finish the computation by himself. It is noted that [LR14] goes a little further for concrete efficiency and considers a varying check-fraction p, where usually protocols check 50% of all garbled circuits in cut-and-choose.
For concrete numbers [LR14] achieve for N = 1000 batch executions and for security 2^-40, their construction requires 7059 circuits, where p = 15% needs to be checked in the offline phase, and randomly mapping the remaining circuits into sets of size 6 and evaluate. This yields a replication factor of ~ 7.06 (when amortizing over all 1000 executions) which much surpassed the former 40 in the single execution setting. In the paper of [LR14] there are numerous tables and graphs for concrete security.