Paper 2023/278

Actively Secure Half-Gates with Minimum Overhead under Duplex Networks

Hongrui Cui, Shanghai Jiao Tong University
Xiao Wang, Northwestern University
Kang Yang, State Key Laboratory of Cryptology
Yu Yu, Shanghai Jiao Tong University

Actively secure two-party computation (2PC) is one of the canonical building blocks in modern cryptography. One main goal for designing actively secure 2PC protocols is to reduce the communication overhead, compared to semi-honest 2PC protocols. In this paper, we propose a new actively secure constant-round 2PC protocol with one-way communication of $2\kappa+5$ bits per AND gate (for $\kappa$-bit computational security and any statistical security), essentially matching the one-way communication of semi-honest half-gates protocol. This is achieved by two new techniques: 1. The recent compression technique by Dittmer et al. (Crypto 2022) shows that a relaxed preprocessing is sufficient for authenticated garbling that does not reveal masked wire values to the garbler. We introduce a new form of authenticated bits and propose a new technique of generating authenticated AND triples to reduce the one-way communication of preprocessing from $5\rho+1$ bits to $2$ bits per AND gate for $\rho$-bit statistical security. 2. Unfortunately, the above compressing technique is only compatible with a less compact authenticated garbled circuit of size $2\kappa+3\rho$ bits per AND gate. We designed a new authenticated garbling that does not use information theoretic MACs but rather dual execution without leakage to authenticate wire values in the circuit. This allows us to use a more compact half-gates based authenticated garbled circuit of size $2\kappa+1$ bits per AND gate, and meanwhile keep compatible with the compression technique. Our new technique can achieve one-way communication of $2\kappa+5$ bits per AND gate. Our technique of yielding authenticated AND triples can also be used to optimize the two-way communication (i.e., the total communication) by combining it with the authenticated garbled circuits by Dittmer et al., which results in an actively secure 2PC protocol with two-way communication of $2\kappa+3\rho+4$ bits per AND gate.

Available format(s)
Cryptographic protocols
Publication info
A major revision of an IACR publication in EUROCRYPT 2023
Garbled CircuitCorrelated Oblivious TransferDual Execution
Contact author(s)
rickfreeman @ sjtu edu cn
wangxiao @ cs northwestern edu
yangk @ sklc org
yuyu @ yuyu hk
2023-02-27: revised
2023-02-24: received
See all versions
Short URL
Creative Commons Attribution


      author = {Hongrui Cui and Xiao Wang and Kang Yang and Yu Yu},
      title = {Actively Secure Half-Gates with Minimum Overhead under Duplex Networks},
      howpublished = {Cryptology ePrint Archive, Paper 2023/278},
      year = {2023},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.