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’22), 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.

错误:搜索内容不能为空,请输入英文关键词
错误:关键词超出字数限制,请精简
高级检索

Row Reduction Techniques for n-Party Garbling

  • Kelong Cong,
  • Emmanuela Orsini,
  • Erik Pohle,
  • Oliver Zajonc

摘要

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’22), 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.