David Heath -- Stacked Garbling: Garbled Circuit Proportional to Longest Execution Path

<br>Abstract:<br><br><br><span>Secure two party computation (2PC) of arbitrary programs can be&nbsp;efficiently achieved using garbled circuits (GC).&nbsp;The bottleneck of GC efficiency is communication.&nbsp;It is widely believed that it is necessary to transmit the entire GC&nbsp;during 2PC, even for conditional branches that are not taken.</span><br><span><br>This folklore belief is false.</span><br><span><br>In this talk, I will present Stacked Garbling (Heath and Kolesnikov,&nbsp;Crypto 2020), a technique that eliminates the communication cost of inactive&nbsp;conditional branches.&nbsp;I will begin by discussing two prior works, Free If (Kolesnikov, Asiacrypt 2018) and Stacked Garbling for Zero Knowledge (Heath and&nbsp;Kolesnikov, Eurocrypt 2020), which respectively eliminate inactive&nbsp;branch communication when the circuit generator/circuit evaluator&nbsp;knows the active branch.&nbsp;I will then show how these ideas can be combined and extended to eliminate the&nbsp;communication cost of&nbsp;inactive branches, even when no player knows which branch is taken.&nbsp;The presented approach is of theoretical interest and is also practical:&nbsp;the approach is compatible with prior GC enhancements and concretely&nbsp;outperforms naive GC branching in most settings.</span>

Thursday, September 24, 2020 - 3:00pm to 4:00pm