Actively Secure Half-Gates with Minimum Overhead under Duplex Networks

Abstract 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 make significant progress in closing this gap by proposing two new actively secure constant-round 2PC protocols, one with one-way communication of $$2\kappa +5$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mn>2</mml:mn> <mml:mi>κ</mml:mi> <mml:mo>+</mml:mo> <mml:mn>5</mml:mn> </mml:mrow> </mml:math> bits per AND gate (for $$\kappa $$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mi>κ</mml:mi> </mml:math> -bit computational security and any statistical security) and one with total communication of $$2\kappa +\rho +5$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mn>2</mml:mn> <mml:mi>κ</mml:mi> <mml:mo>+</mml:mo> <mml:mi>ρ</mml:mi> <mml:mo>+</mml:mo> <mml:mn>5</mml:mn> </mml:mrow> </mml:math> bits per AND gate (for $$\rho $$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mi>ρ</mml:mi> </mml:math> -bit statistical security). In particular, our first protocol essentially matches the one-way communication of semi-honest half-gates protocol. Our optimization is achieved by three new techniques: The recent compression technique by Dittmer et al. (Crypto 13510:57–87, 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$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mn>5</mml:mn> <mml:mi>ρ</mml:mi> <mml:mo>+</mml:mo> <mml:mn>1</mml:mn> </mml:mrow> </mml:math> bits to 2 bits per AND gate for $$\rho $$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mi>ρ</mml:mi> </mml:math> -bit statistical security. Unfortunately, the above compressing technique is only compatible with a less compact authenticated garbled circuit of size $$2\kappa +3\rho $$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mn>2</mml:mn> <mml:mi>κ</mml:mi> <mml:mo>+</mml:mo> <mml:mn>3</mml:mn> <mml:mi>ρ</mml:mi> </mml:mrow> </mml:math> 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$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mn>2</mml:mn> <mml:mi>κ</mml:mi> <mml:mo>+</mml:mo> <mml:mn>1</mml:mn> </mml:mrow> </mml:math> bits per AND gate, and meanwhile keep compatible with the compression technique. Our new technique can achieve one-way communication of $$2\kappa +5$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mn>2</mml:mn> <mml:mi>κ</mml:mi> <mml:mo>+</mml:mo> <mml:mn>5</mml:mn> </mml:mrow> </mml:math> bits per AND gate. In terms of total communication, we notice that the communication overhead of the consistency checking method by Dittmer et al. (Crypto 13510:57–87, 2022) can be optimized by adding one-round of interaction and utilizing the Free-XOR property. This reduces the online communication from $$2\kappa +3\rho $$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mn>2</mml:mn> <mml:mi>κ</mml:mi> <mml:mo>+</mml:mo> <mml:mn>3</mml:mn> <mml:mi>ρ</mml:mi> </mml:mrow> </mml:math> bits down to $$2\kappa +\rho +1$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mn>2</mml:mn> <mml:mi>κ</mml:mi> <mml:mo>+</mml:mo> <mml:mi>ρ</mml:mi> <mml:mo>+</mml:mo> <mml:mn>1</mml:mn> </mml:mrow> </mml:math> bits per AND gate. Combined with our first contribution, this yields total amortized communication of $$2\kappa +\rho +5$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mn>2</mml:mn> <mml:mi>κ</mml:mi> <mml:mo>+</mml:mo> <mml:mi>ρ</mml:mi> <mml:mo>+</mml:mo> <mml:mn>5</mml:mn> </mml:mrow> </mml:math> bits.