[Resource Topic] 2025/614: Highly Efficient Actively Secure Two-Party Computation with One-Bit Advantage Bound

Welcome to the resource topic for 2025/614

Title:
Highly Efficient Actively Secure Two-Party Computation with One-Bit Advantage Bound

Authors: Yi Liu, Junzuo Lai, Peng Yang, Anjia Yang, Qi Wang, Siu-Ming Yiu, Jian Weng

Abstract:

Secure two-party computation (2PC) enables two parties to jointly evaluate a function while maintaining input privacy. Despite recent significant progress, a notable efficiency gap remains between actively secure and passively secure protocols. In S&P’12, Huang, Katz, and Evans formalized the notion of \emph{active security with one-bit leakage}, providing a promising approach to bridging this gap. Protocols derived from this notion have become foundational in designing highly efficient actively secure 2PC protocols. However, a critical challenge identified by Huang, Katz, and Evans remains unexplored: these protocols face significant weaknesses in ensuring fairness for honest parties when employed in standalone settings rather than as components within larger protocols. While the authors proposed two potential solutions to mitigate this issue, both approaches are prohibitively expensive and lack formalization of security guarantees.

In this paper, we first formally define an enhanced notion called \emph{active security with one-bit-advantage bound}, in which the adversaries’ advantages are strictly bounded to at most one bit beyond what honest parties obtain. This bound is enforced through a \emph{progressive revelation} mechanism, where the evaluation result is disclosed incrementally bit by bit. In addition, we propose a novel approach leveraging label structures within garbled circuits to design a highly efficient constant-round 2PC protocol that achieves active security with one-bit advantage bound. Our protocol demonstrates \emph{runtime performance nearly identical to that of passively secure garbled-circuit counterparts} in duplex networks (\eg 1.033\times for the {\tt SHA256} circuit in LAN), with \emph{low overhead} for output progressive revelation (only 80 communicated bytes per bit release).

With its strengthened security guarantees and minimal overhead, our protocol is highly suitable for practical 2PC applications.

ePrint: https://eprint.iacr.org/2025/614

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 .