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 <InlineEquation ID="IEq1"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="145_2025_9539_Article_IEq1.gif" Format="GIF" Height="14" Rendition="HTML" Resolution="72" Type="Linedraw" Width="47" /> </InlineMediaObject> <EquationSource Format="TEX">$2\kappa +5$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mn>2</mn> <mi>κ</mi> <mo>+</mo> <mn>5</mn> </mrow> </math></EquationSource> </InlineEquation> bits per AND gate (for <InlineEquation ID="IEq2"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="145_2025_9539_Article_IEq2.gif" Format="GIF" Height="10" Rendition="HTML" Resolution="72" Type="Linedraw" Width="13" /> </InlineMediaObject> <EquationSource Format="TEX">$\kappa $</EquationSource> <EquationSource Format="MATHML"><math> <mi>κ</mi> </math></EquationSource> </InlineEquation>-bit computational security and any statistical security) and one with total communication of <InlineEquation ID="IEq3"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="145_2025_9539_Article_IEq3.gif" Format="GIF" Height="16" Rendition="HTML" Resolution="72" Type="Linedraw" Width="76" /> </InlineMediaObject> <EquationSource Format="TEX">$2\kappa +\rho +5$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mn>2</mn> <mi>κ</mi> <mo>+</mo> <mi>ρ</mi> <mo>+</mo> <mn>5</mn> </mrow> </math></EquationSource> </InlineEquation> bits per AND gate (for <InlineEquation ID="IEq4"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="145_2025_9539_Article_IEq4.gif" Format="GIF" Height="12" Rendition="HTML" Resolution="72" Type="Linedraw" Width="13" /> </InlineMediaObject> <EquationSource Format="TEX">$\rho $</EquationSource> <EquationSource Format="MATHML"><math> <mi>ρ</mi> </math></EquationSource> </InlineEquation>-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: <OrderedList> <ListItem> <ItemNumber>1.</ItemNumber> <ItemContent> 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 <InlineEquation ID="IEq5"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="145_2025_9539_Article_IEq5.gif" Format="GIF" Height="16" Rendition="HTML" Resolution="72" Type="Linedraw" Width="46" /> </InlineMediaObject> <EquationSource Format="TEX">$5\rho +1$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mn>5</mn> <mi>ρ</mi> <mo>+</mo> <mn>1</mn> </mrow> </math></EquationSource> </InlineEquation> bits to 2 bits per AND gate for <InlineEquation ID="IEq6"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="145_2025_9539_Article_IEq6.gif" Format="GIF" Height="12" Rendition="HTML" Resolution="72" Type="Linedraw" Width="13" /> </InlineMediaObject> <EquationSource Format="TEX">$\rho $</EquationSource> <EquationSource Format="MATHML"><math> <mi>ρ</mi> </math></EquationSource> </InlineEquation>-bit statistical security. </ItemContent> </ListItem> <ListItem> <ItemNumber>2.</ItemNumber> <ItemContent> Unfortunately, the above compressing technique is only compatible with a less compact authenticated garbled circuit of size <InlineEquation ID="IEq7"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="145_2025_9539_Article_IEq7.gif" Format="GIF" Height="16" Rendition="HTML" Resolution="72" Type="Linedraw" Width="58" /> </InlineMediaObject> <EquationSource Format="TEX">$2\kappa +3\rho $</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mn>2</mn> <mi>κ</mi> <mo>+</mo> <mn>3</mn> <mi>ρ</mi> </mrow> </math></EquationSource> </InlineEquation> 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 <InlineEquation ID="IEq8"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="145_2025_9539_Article_IEq8.gif" Format="GIF" Height="14" Rendition="HTML" Resolution="72" Type="Linedraw" Width="47" /> </InlineMediaObject> <EquationSource Format="TEX">$2\kappa +1$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mn>2</mn> <mi>κ</mi> <mo>+</mo> <mn>1</mn> </mrow> </math></EquationSource> </InlineEquation> bits per AND gate, and meanwhile keep compatible with the compression technique. Our new technique can achieve one-way communication of <InlineEquation ID="IEq9"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="145_2025_9539_Article_IEq9.gif" Format="GIF" Height="14" Rendition="HTML" Resolution="72" Type="Linedraw" Width="47" /> </InlineMediaObject> <EquationSource Format="TEX">$2\kappa +5$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mn>2</mn> <mi>κ</mi> <mo>+</mo> <mn>5</mn> </mrow> </math></EquationSource> </InlineEquation> bits per AND gate. </ItemContent> </ListItem> <ListItem> <ItemNumber>3.</ItemNumber> <ItemContent> 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 <InlineEquation ID="IEq10"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="145_2025_9539_Article_IEq10.gif" Format="GIF" Height="16" Rendition="HTML" Resolution="72" Type="Linedraw" Width="58" /> </InlineMediaObject> <EquationSource Format="TEX">$2\kappa +3\rho $</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mn>2</mn> <mi>κ</mi> <mo>+</mo> <mn>3</mn> <mi>ρ</mi> </mrow> </math></EquationSource> </InlineEquation> bits down to <InlineEquation ID="IEq11"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="145_2025_9539_Article_IEq11.gif" Format="GIF" Height="16" Rendition="HTML" Resolution="72" Type="Linedraw" Width="76" /> </InlineMediaObject> <EquationSource Format="TEX">$2\kappa +\rho +1$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mn>2</mn> <mi>κ</mi> <mo>+</mo> <mi>ρ</mi> <mo>+</mo> <mn>1</mn> </mrow> </math></EquationSource> </InlineEquation> bits per AND gate. Combined with our first contribution, this yields total amortized communication of <InlineEquation ID="IEq12"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="145_2025_9539_Article_IEq12.gif" Format="GIF" Height="16" Rendition="HTML" Resolution="72" Type="Linedraw" Width="76" /> </InlineMediaObject> <EquationSource Format="TEX">$2\kappa +\rho +5$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mn>2</mn> <mi>κ</mi> <mo>+</mo> <mi>ρ</mi> <mo>+</mo> <mn>5</mn> </mrow> </math></EquationSource> </InlineEquation> bits. </ItemContent> </ListItem> </OrderedList>

Actively Secure Half-Gates with Minimum Overhead under Duplex Networks

期刊论文
出版模式：

开放获取
发表日期：

2025年2月26日

查看全文

Hongrui Cui,
Xiao Wang,
Kang Yang,
Yu Yu

摘要

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$ $2 κ + 5$ bits per AND gate (for $\kappa $ $κ$ -bit computational security and any statistical security) and one with total communication of $2\kappa +\rho +5$ $2 κ + ρ + 5$ bits per AND gate (for $\rho $ $ρ$ -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: 1.

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$ $5 ρ + 1$ bits to 2 bits per AND gate for $\rho $ $ρ$ -bit statistical security.

Unfortunately, the above compressing technique is only compatible with a less compact authenticated garbled circuit of size $2\kappa +3\rho $ $2 κ + 3 ρ$ 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$ $2 κ + 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$ $2 κ + 5$ 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 $ $2 κ + 3 ρ$ bits down to $2\kappa +\rho +1$ $2 κ + ρ + 1$ bits per AND gate. Combined with our first contribution, this yields total amortized communication of $2\kappa +\rho +5$ $2 κ + ρ + 5$ bits.