Welcome to the resource topic for 2025/829
Title:
Row Reduction Techniques for n-Party Garbling
Authors: Kelong Cong, Emmanuela Orsini, Erik Pohle, Oliver Zajonc
Abstract:Recent advancements in maliciously secure garbling have significantly improved the efficiency of constant-round multi-party computation. Research in the field has primarily focused on reducing communication complexity through row reduction techniques and improvements to the preprocessing phase with the use of simpler correlations.
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\kappa to 3n\kappa and from (4n-6)\kappa to 3(n-1)\kappa 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\times reduction in communication compared to HSS17 and a 2.2\times reduction over the state of the art authenticated garbling of Yang et al. for 3 parties in a circuit with 10 million AND gates.
ePrint: https://eprint.iacr.org/2025/829
See all topics related to this paper.
Feel free to post resources that are related to this paper below.
Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.
For more information, see the rules for Resource Topics .