In this work, we present two contributions to reduce the communication complexity of state of the art multi-party garbling with an arbitrary number of corruptions. First, we show how to achieve full row reduction for n-party garbled circuits in HSS17-style protocols (Hazay et al., Asiacrypt’17 & JC’20) and authenticated garbling (Yang et al., CCS’20), reducing the size of the garbled circuit by 25% from 4nκ to 3nκ and from (4n − 6)κ to 3(n − 1)κ bits per AND gate, respectively. Achieving row reduction in multi-party garbling has been an open problem which was partly addressed by the work of Yang et al. for authenticated garbling. In our work, we show a full row reduction for both garbling approaches, thus addressing this open problem completely. Second, drawing inspiration from the work of Dittmer et al. (Crypto 2022), we propose a new preprocessing protocol to obtain the required materials for the garbling phase using large field triples that can be generated with sublinear communication. The new preprocessing significantly reduces the communication overhead of garbled circuits. Our optimizations result in up to a 6× reduction in communication compared to HSS17 and a 2.2× reduction over the state of the art authenticated garbling of Yang et al. for 3 parties in a circuit with 10 million AND gates.

About the speaker: Erik Pohle is a Postdoc in the Cryptography and Cybersecurity Section