# Secure Two-Party Computation Based on Fast Cut-and-Choose Bilateral Oblivious Transfer

Authors: Yongjun Wang; Kun Xiong; He Tian; Jing Zhang; Xixi Yan
Journal: Security and Communication Networks
 (2022)

---

## Abstract

In secure two-party computation, each party has its input and wants to jointly compute a function from which it obtains the output corresponding to its respective inputs. For achieving security against a malicious adversary, an effective approach is using cut-and-choose, which requires the circuit constructorP1 to construct S copies of the circuit C (C is used to compute the function F). The circuit evaluator P2 selects S∕2 circuits to open for the check. If these S∕2 circuits are correctly constructed, P2 assumes that the remaining S∕2 circuits are also correctly constructed and uses the remaining circuits to compute. However, this method introduces significant computational complexity and interactive rounds, mainly due to more circuits that must be used for security purposes and the need for multiple interactions to transmit the keys. In this paper, regarding the issue above, we present a novel secure two-party computation protocol, and it can achieve security against the malicious adversary. Concretely, we still use the idea of cut-and-choose but improve the cut-and-choose oblivious transfer (CCOT) of the usual secure two-party computation protocol into cut-and-choose bilateral oblivious transfer (CCBOT) and propose a variant of it that we call batch single-choice CCBOT, which makes our protocol only needs two rounds of interaction to complete the transmission of all keys and 28Sl of exponentiations. In addition, we use a check mechanism to prevent the case that p1 cheats, but P2 is powerless. Our proposed protocol with an error probability of 2–s of P1 significantly optimizes the communication rounds and computation overheads, solves the selective failure attack, and ensures the consistency of the input.


---

## Body

## 1. Introduction

### 1.1. Background

Secure two-party computation means that two mutually untrusted participants, each holding their input, collaborate to compute a function through a two-party computation protocol that satisfies multiple security properties and obtain the corresponding function output. These security properties mainly include privacy, correctness, input independence, guaranteed output delivery, and fairness [1]. Since professor Yao proposed secure two-party computation [2], it has become the subject of extensive research, with a focus on improving security and efficiency.Yao’s protocol based on oblivious transfer (OT) [3] and garbled circuit (GC) [2] is a well-known protocol of secure two-party computation. However, it only achieves security against the semihonest adversary. Because only one circuit is constructed, P1 can easily cheat by constructing a wrong circuit. For improving the correctness of circuit computation and the security of the protocol, it is best to construct multiple circuits. Part of the circuits are used to check whether they are constructed correctly, and the rest circuits are used to compute the function. This method of dividing circuits to check and then for evaluation is called cut-and-choose [4]. It can solve the problem that Yao’s protocol cannot achieve security against the malicious adversary. Its main idea is that P1 constructs s identical circuits (only one circuit in Yao’s protocol). Then P2 selects some of them (usually half of the total) to check whether these selected circuits (called check circuits) are correct. If the check passes, P2 can consider that the rest circuits (called computation circuits or evaluation circuits) are all correct. Finally, P2 uses the evaluation circuits to compute and uses most of the same outputs as the final function output.Although the protocols for cut-and-choose can combine the check of circuits and the oblivious transfer for transmitting keys to solve the problem of selective failure attacks [5], these protocols use CCOT [6–8] to transmit garbled keys. One significant feature of CCOT is that it can only transmit keys associated with P2,s input wire. This feature to only transmit keys associated with one party will cause the protocol to generate many additional interactions for separately transmitting the relevant keys on P1’s input wire in check circuits and evaluation circuits, which seriously increases the number of interactions and round complexity. The CCOT protocol used in the famous Lindell and Pinkas protocol [9] requires 6 rounds of communication and cannot transmit all required keys. Additionally, it also requires additional interactions for zero-knowledge proofs, and there are 12 rounds of communication of the whole protocol. In addition to transmitting keys, additional interaction is needed to send the set J and verify its consistency of it in two interactions. The protocol [10] of Huang et al. uses a kind of multistage CCOT that still needs to send a cut-and-choose challenge and then uses additional interactions to send garbled input values. Similarly, more [11, 12] have the same problem. In addition, in most of Yao’s garbled circuit protocols based on CCOT, the result takes most of the same values in all evaluation circuits. If there are a few evaluation circuits with different output values, then P1 has cheated. However, P2 will take most of the same value as the result according to the requirements of the protocol, even if it knows that P1 is cheating. This method is likely to leak P2’s private input. P1 can construct the wrong garbled circuits to cheat, but P2 is powerless in this case.With the intensive study of CCOT, CCBOT [13] has emerged. In CCBOT, the receiver R selects the received value according to its input, and the sender S can also actively choose other values to send to R. Compared with CCOT, CCBOT only needs one interaction to send all required keys. Almost all the secure two-party computation protocols using cut-and-choose technology complete the transmission of keys through CCOT. Currently, there has been a great deal of interest in CCBOT research, but there is still a lack of a complete and efficient secure two-party computation protocol that uses CCBOT to complete keys transfer. CCBOT makes the protocols for cut-and-choose have a new improvement. We believe that designing a secure and efficient two-party computing protocol based on CCBOT is research-intensive and challenging. Security here consists mainly of solving the input consistency problem and selective failure attack and achieving security against the malicious adversary. Efficiency is improved by using CCBOT to reduce the rounds of interaction and the complexity of communication between two parties. In addition, we are also committed to solving the problem that P1 cheats, but P2 is powerless.In our paper,P1 needs to construct many copies of the circuit, so we first introduce the cut-and-choose (introduce a new parameter s) into the CCBOT protocol of reference [14]. Then, for making P2 input the same choice bit on each input wire, we improve CCBOT to the single-choice CCBOT. Since each input wire in each circuit must perform a single-choice CCBOT, it is necessary to perform the transfer key phase in batches. After the above improvements, we propose a batch single-choice CCBOT protocol, and see Section 4 for more details. Next, for the input consistency problem of P1, we use a Diffie–Hellman pseudorandom synthesizer [15] to generate the keys gai0⋅rj and gai1⋅rj of its own input bits. This key structure makes it easy for P1 to use the DDH assumption to prove the consistency of its inputs across all circuits. In addition, in our protocol, the inputs of both parties are done through only one interaction, which prevents the problem of inconsistent inputs between different interactions. And then, a selective failure attack is caused by the separation of circuit division from the oblivious transfer. Based on the features of the CCBOT protocol, we intertwine transmission keys with circuit checks. This method does not require the use of larger inputs and more circuits for the security of the protocol. Finally, for the problem that P2 cannot abort the protocol when P1 constructs the wrong circuits to cheat we have added an additional check mechanism. When the outputs of all evaluation circuits are inconsistent, P2 will store a “proof” and then input this “proof” into the secure check protocol to obtain the private input of P1 and compute fx,y locally. The mechanism is detailed in reference [16].


### 1.2. Our Contributions

We first improve the CCBOT protocol of reference [14] and formalize the improved protocol. Based on this, we present a novel secure two-party protocol. It can achieve security against the malicious adversary. Our contribution consists mainly of the following:(1)
We improve the original CCBOT protocol to a variant called batch single-choice CCBOT. It can complete the oblivious transfer tasks of each gate in all circuits in parallel and requires two rounds of communication and15sℓ exponents. Since only two rounds are required to complete all key transmissions, no additional interaction is required to send the keys associated with their own inputs in check circuits and evaluation circuits.(2)
We apply our batch single-choice CCBOT on Yao’s protocol and propose a new secure two-party computation protocol that can solve the problem of input consistency and selective failure attack. It achieves security against the malicious adversary. Moreover,P1’s error probability is the optimal 2−s in our protocol.(3)
We use a check mechanism of work [16] to prevent the case that P2 finds out that P1 is cheating but P2 is powerless. In general, when the outputs of all evaluation circuits are inconsistent, P2 will find the wire in s copies of the circuit but output different results and then store the garbled values b0 corresponding to 0 and b1 corresponding to 1 for the output of this output wire in different circuits. Finally, P2 inputs them into the check protocol to obtain the private input of P1, so as to calculate fx,y locally.


## 1.1. Background

Secure two-party computation means that two mutually untrusted participants, each holding their input, collaborate to compute a function through a two-party computation protocol that satisfies multiple security properties and obtain the corresponding function output. These security properties mainly include privacy, correctness, input independence, guaranteed output delivery, and fairness [1]. Since professor Yao proposed secure two-party computation [2], it has become the subject of extensive research, with a focus on improving security and efficiency.Yao’s protocol based on oblivious transfer (OT) [3] and garbled circuit (GC) [2] is a well-known protocol of secure two-party computation. However, it only achieves security against the semihonest adversary. Because only one circuit is constructed, P1 can easily cheat by constructing a wrong circuit. For improving the correctness of circuit computation and the security of the protocol, it is best to construct multiple circuits. Part of the circuits are used to check whether they are constructed correctly, and the rest circuits are used to compute the function. This method of dividing circuits to check and then for evaluation is called cut-and-choose [4]. It can solve the problem that Yao’s protocol cannot achieve security against the malicious adversary. Its main idea is that P1 constructs s identical circuits (only one circuit in Yao’s protocol). Then P2 selects some of them (usually half of the total) to check whether these selected circuits (called check circuits) are correct. If the check passes, P2 can consider that the rest circuits (called computation circuits or evaluation circuits) are all correct. Finally, P2 uses the evaluation circuits to compute and uses most of the same outputs as the final function output.Although the protocols for cut-and-choose can combine the check of circuits and the oblivious transfer for transmitting keys to solve the problem of selective failure attacks [5], these protocols use CCOT [6–8] to transmit garbled keys. One significant feature of CCOT is that it can only transmit keys associated with P2,s input wire. This feature to only transmit keys associated with one party will cause the protocol to generate many additional interactions for separately transmitting the relevant keys on P1’s input wire in check circuits and evaluation circuits, which seriously increases the number of interactions and round complexity. The CCOT protocol used in the famous Lindell and Pinkas protocol [9] requires 6 rounds of communication and cannot transmit all required keys. Additionally, it also requires additional interactions for zero-knowledge proofs, and there are 12 rounds of communication of the whole protocol. In addition to transmitting keys, additional interaction is needed to send the set J and verify its consistency of it in two interactions. The protocol [10] of Huang et al. uses a kind of multistage CCOT that still needs to send a cut-and-choose challenge and then uses additional interactions to send garbled input values. Similarly, more [11, 12] have the same problem. In addition, in most of Yao’s garbled circuit protocols based on CCOT, the result takes most of the same values in all evaluation circuits. If there are a few evaluation circuits with different output values, then P1 has cheated. However, P2 will take most of the same value as the result according to the requirements of the protocol, even if it knows that P1 is cheating. This method is likely to leak P2’s private input. P1 can construct the wrong garbled circuits to cheat, but P2 is powerless in this case.With the intensive study of CCOT, CCBOT [13] has emerged. In CCBOT, the receiver R selects the received value according to its input, and the sender S can also actively choose other values to send to R. Compared with CCOT, CCBOT only needs one interaction to send all required keys. Almost all the secure two-party computation protocols using cut-and-choose technology complete the transmission of keys through CCOT. Currently, there has been a great deal of interest in CCBOT research, but there is still a lack of a complete and efficient secure two-party computation protocol that uses CCBOT to complete keys transfer. CCBOT makes the protocols for cut-and-choose have a new improvement. We believe that designing a secure and efficient two-party computing protocol based on CCBOT is research-intensive and challenging. Security here consists mainly of solving the input consistency problem and selective failure attack and achieving security against the malicious adversary. Efficiency is improved by using CCBOT to reduce the rounds of interaction and the complexity of communication between two parties. In addition, we are also committed to solving the problem that P1 cheats, but P2 is powerless.In our paper,P1 needs to construct many copies of the circuit, so we first introduce the cut-and-choose (introduce a new parameter s) into the CCBOT protocol of reference [14]. Then, for making P2 input the same choice bit on each input wire, we improve CCBOT to the single-choice CCBOT. Since each input wire in each circuit must perform a single-choice CCBOT, it is necessary to perform the transfer key phase in batches. After the above improvements, we propose a batch single-choice CCBOT protocol, and see Section 4 for more details. Next, for the input consistency problem of P1, we use a Diffie–Hellman pseudorandom synthesizer [15] to generate the keys gai0⋅rj and gai1⋅rj of its own input bits. This key structure makes it easy for P1 to use the DDH assumption to prove the consistency of its inputs across all circuits. In addition, in our protocol, the inputs of both parties are done through only one interaction, which prevents the problem of inconsistent inputs between different interactions. And then, a selective failure attack is caused by the separation of circuit division from the oblivious transfer. Based on the features of the CCBOT protocol, we intertwine transmission keys with circuit checks. This method does not require the use of larger inputs and more circuits for the security of the protocol. Finally, for the problem that P2 cannot abort the protocol when P1 constructs the wrong circuits to cheat we have added an additional check mechanism. When the outputs of all evaluation circuits are inconsistent, P2 will store a “proof” and then input this “proof” into the secure check protocol to obtain the private input of P1 and compute fx,y locally. The mechanism is detailed in reference [16].


## 1.2. Our Contributions

We first improve the CCBOT protocol of reference [14] and formalize the improved protocol. Based on this, we present a novel secure two-party protocol. It can achieve security against the malicious adversary. Our contribution consists mainly of the following:(1)
We improve the original CCBOT protocol to a variant called batch single-choice CCBOT. It can complete the oblivious transfer tasks of each gate in all circuits in parallel and requires two rounds of communication and15sℓ exponents. Since only two rounds are required to complete all key transmissions, no additional interaction is required to send the keys associated with their own inputs in check circuits and evaluation circuits.(2)
We apply our batch single-choice CCBOT on Yao’s protocol and propose a new secure two-party computation protocol that can solve the problem of input consistency and selective failure attack. It achieves security against the malicious adversary. Moreover,P1’s error probability is the optimal 2−s in our protocol.(3)
We use a check mechanism of work [16] to prevent the case that P2 finds out that P1 is cheating but P2 is powerless. In general, when the outputs of all evaluation circuits are inconsistent, P2 will find the wire in s copies of the circuit but output different results and then store the garbled values b0 corresponding to 0 and b1 corresponding to 1 for the output of this output wire in different circuits. Finally, P2 inputs them into the check protocol to obtain the private input of P1, so as to calculate fx,y locally.


## 2. Related Work

Secure multiparty computation is an active research field of cryptography, and there is more and more extensive research on secure two-party computation. Its classical architectures often use garbled circuits [17] or GMW protocols [18], with the main research being on using garbled circuits to design an efficient secure computation protocol in different security models [19, 20] and optimizing the efficiency of various security protocols [21–23]. Particularly, the problem of efficiency has attracted a great deal of attention due to the large amount of bandwidth it requires. How to efficiently perform the computation in a malicious model is essential. Taking the running time of the entire protocol into account, the cut-and-choose approach is almost the best method to achieve security against the malicious adversary.Pinkas et al. first introduced the cut-and-choose approach [4] into the garbled circuit in 2003, and Lindell proposed the first secure two-party protocol with complete security proof in 2007 [24]. The most classic protocol can be traced back to reference [9]. It divides 50% check circuits and 50% evaluation circuits to achieve security against the malicious adversary, and P1’s cheating probability is 2−0.311s. Therefore, an error probability of 2−40 can only be achieved when s is set to 132 (132 gates). This means the cost of achieving security against the malicious adversary is 132 times that of a semihonest adversary. In contrast, it divides 60% check circuits and 40% evaluation circuits to get an error probability of 2−0.32s in reference [25]. Reference [26] proposed the idea of a symmetrical cut-and-choose. The idea is essentially that two parties involved work together to construct s copies of garbled circuits, which are then checked by someone else. The probability of an error is 2−k+Οlogk. In reference [27], it applies the cut-and-choose technique to three-party computation. The cost of achieving security against a malicious adversary is comparatively small to other semihonest 3PC.Using the cut-and-choose technique will bring some problems. In order to solve the input consistency problem, earlier work [4] used commitment schemes, but the communication overhead was significant. Shelat and Shen proposed a consistency detection method [25] in 2011 that reduces the communication overhead by transmitting a small number of parameters instead of zero-knowledge proofs. In 2014, Frederiksen constructed a circuit extension [28] that uses function f′ instead of fx,y. With this modification, the calculation result of the new function f′ is the same as the original fx,y, but it needs to come from the constructor P1 and the evaluator P2 additional random input bits. With statistical security, it can be verified that the inputs of both parties to all circuits are consistent. In addition, there are some schemes [29–31] that also give solutions to the problem of input consistency. For the selective failure attack problem, the evaluator in work [24] takes the XOR value of the real input and multiple random bits as the OT input so that the evaluator has nothing to do with the real input when it exits. The constructor cannot infer the evaluator input by selective failure attack. References [25, 32] solved this problem by a committing OT and a circuit extension, respectively.Reference [16] uses a check mechanism to prevent P2 from being powerless. If P2 finds that the output values of all evaluation circuits are inconsistent, it stores a piece of evidence and then inputs this evidence in the check protocol to obtain the private input x of P1 and finally calculates the function fx,y locally. The work [33] proposed a method to encode trapdoors in the output wires, allowing the evaluator to recover the input of the constructor when multiple outputs are obtained.In 2015, Zhao et al. first proposed the CCBOT primitive based on the CCOT protocol and constructed a complete CCBOT protocol based on homomorphic encryption. This CCBOT protocol achieved security against the malicious adversary. And then, an improved version of CCBOT based on the decisional Diffie–Hellman (DDH) assumption [14] was proposed in 2016. It greatly improved the efficiency of CCBOT but without using cut-and-choose. Ning and Wang proposed a novel CCBOT protocol [34] based on the computational Diffie–Hellman (CDH) assumption in 2020. It achieved security against the malicious adversary and the error probability of P1 is 2−s.


## 3. Preliminaries

We defineℓ, n, a, and s as the length of inputs, computational safety parameter, arbitrary strings, and statistical security parameter, respectively. In order to give a formal definition of security, we first introduce how to describe the indistinguishability of the probability ensemble. As we know, the cut-and-choose technique requires multiple circuits. Therefore, the probability ensemble is related to computational security parameter n, arbitrary strings a, and statistical security parameter s. In this paper, we use n,s−indistinguishability to describe the indistinguishability of the probability ensemble, and its formal definition is as follows:


### 3.1.n,s−Indistinguishability

There are two probability ensemblesX and Y. They are in the form of X=Xa,n,sn,s∈ℕ;a∈0,1∗ and Y=Ya,n,sn,s∈ℕ;a∈0,1∗ and satisfy that for any n and s, the value range of the two probability distributions is a string of length l, where l is represented as a polynomial of n+s. If for every nonuniform polynomial-time distinguisher D, s∈ℕ, polynomial p⋅, a∈0,1∗, and n∈ℕ, there exists a constant −1<c<0, and the following inequality satisfies(1)PrDXa,n,s,a,n,s=1−PrDYa,n,s,a,n,s=1<1pn+12c⋅s.We can sayX and Y are n,s−indistinguishability and denoted by Xn,s≡Y.


### 3.2. Ideal/Real Simulation Paradigm and Definition of Security

In this paradigm, there is an ideal world and a real world. In the real world, adversaryA executes the secure computation protocol jointly with another honest party (joint output is denoted as IDEALf,Sz,ix,y,n,s), and in the ideal world, the simulator S executes the secure computation protocol jointly with another honest participant (joint output is denoted as REALπ,Az,ix,y,n,s). Below, we express the security of a secure two-party computation protocol:(2)IDEALf,Sz,ix,y,n,s≡n,sREALπ,Az,ix,y,n,s,where x,y,z∈0,1∗, x=y, and n,s∈ℕ. Then, we can conclude protocol π securely computes function f.


## 3.1.n,s−Indistinguishability

There are two probability ensemblesX and Y. They are in the form of X=Xa,n,sn,s∈ℕ;a∈0,1∗ and Y=Ya,n,sn,s∈ℕ;a∈0,1∗ and satisfy that for any n and s, the value range of the two probability distributions is a string of length l, where l is represented as a polynomial of n+s. If for every nonuniform polynomial-time distinguisher D, s∈ℕ, polynomial p⋅, a∈0,1∗, and n∈ℕ, there exists a constant −1<c<0, and the following inequality satisfies(1)PrDXa,n,s,a,n,s=1−PrDYa,n,s,a,n,s=1<1pn+12c⋅s.We can sayX and Y are n,s−indistinguishability and denoted by Xn,s≡Y.


## 3.2. Ideal/Real Simulation Paradigm and Definition of Security

In this paradigm, there is an ideal world and a real world. In the real world, adversaryA executes the secure computation protocol jointly with another honest party (joint output is denoted as IDEALf,Sz,ix,y,n,s), and in the ideal world, the simulator S executes the secure computation protocol jointly with another honest participant (joint output is denoted as REALπ,Az,ix,y,n,s). Below, we express the security of a secure two-party computation protocol:(2)IDEALf,Sz,ix,y,n,s≡n,sREALπ,Az,ix,y,n,s,where x,y,z∈0,1∗, x=y, and n,s∈ℕ. Then, we can conclude protocol π securely computes function f.


## 4. Cut-and-Choose Bilateral Obvious Transfer

The key transfer phase of our secure protocol uses the CCBOT protocol. A CCBOT protocol is a variant of CCOT with the additional property that the sender can actively send its own values to the receiver based on the subset selected by the receiver. The starting point for us to construct the CCBOT for Yao’s protocol is the protocol of Wei et al. [14]. In the protocol of reference [14], b is the permutation bit of the sender S, and the value σ and τ are the choice-bit of the sender S and R, respectively. x0,x1 are the garbled keys corresponding to 0 and 1 of S’s input wires, and r0,r1 are the garbled keys corresponding to 0 and 1 of R’s input wires. Moreover, the receiver R has a choice-bit and indices set so that it can obtain the value of r corresponding to the choice-bit. Then it uses five tuples T1,T2,T3,T4,T5 to transfer the values xσ,x1−σ,σ⊕b,r0 and r1, respectively. After the transfer is complete, R either obtains the pairs xb,x1−b, r0,r1 or receives xσ and rτ. According to the value of j, R varies whether each of the five tuples is a DH tuple. If all the DH tuples have the same witness, S can obtain the corresponding values by the witness. To prevent the malicious R, here needs the zero-knowledge proof of the DH tuple to prove that the DH tuples generated by R are correct. We give the details of zero-knowledge proof of the DH tuple in the appendix.It is worth noting that the CCBOT protocol constructed in reference [14] does not use the cut-and-choose technique. In order to apply the CCBOT protocol to Yao’s protocol, the first step is to introduce the cut-and-choose technique into it, so a security parameter s is added. The essence of the CCBOT with the introduction of the cut-and-choose technique is to run s copies of the CCBOT protocol of reference [14]. Next, we will describe the functionality of CCBOT and improve it to single-choice CCBOT and batch single-choice CCBOT that we will use. As both single-choice CCBOT and batch single-choice CCBOT are based on the original CCBOT with certain restrictions and processing, these changes do not affect the security of the protocols, so we omit the security proofs for the following protocols, but give their functionality, detailed description, and approximate efficiency. In Figure 1, we formally define the functions of CCBOT, which are denoted by ℱccbot. In this protocol, there are 30s exponents and two rounds of communication.Figure 1
The CCBOT functionalityℱccbot between the sender and the receiver.For instantiating the CCBOT function, we describe its functionality in a secure protocol. Throughℱccbot, parts of these circuits are opened. P2 obtains all the keys on the input wires of P1 and P2 in this part of the circuit. For the remaining circuit, P2 receives the keys corresponding to its own input and the keys sent by P1. For security, the order of the keys corresponding to P2’s input wires received by P2 is replaced at random in check circuits. Obviously, P2 can obtain the keys that are used to check circuits and evaluation circuits at one time, without the need for additional interactions to send additional keys and other proof of consistency.


### 4.1. Single-Choice CCBOT

There will be a problem that the functionalityℱccbot cannot guarantee that R inputs the identical choice-bit in the same input wire of all circuits. As we know, every bit of R’s input needs an oblivious transfer. Therefore, it must be ensured that the inputs on the same input wire of R in all garbled circuits are identical. So we propose a variant of the original CCBOT protocol. Here, we use a single-choice CCBOT functionality ℱccbotS that is implemented by modifying the CCBOT protocol during the transmission phase for ensuring that R inputs the same choice-bit in each pair of tuples. Since R uses the same choice-bit in different tuples, then the key value associated with R’s input wire only needs to be computed once so that this will reduce s−1 exponents. As a result, in this protocol, there are 29s exponents and two rounds of communication.In Figure2, we formally define the protocol of single-choice CCBOT functionality ℱccbotS, and a simple example is provided in Figure 3.Figure 2
The single-choice CCBOT functionalityℱccbotS between the sender and the receiver.Figure 3
A detailed description ofℱccbotS where j∈J and τ=0.


### 4.2. Batch Single-Choice CCBOT

Using the cut-and-choose approach requires the construction ofs circuits. Single-choice CCBOT needs to be performed on all wires in every circuit. Hence, there we use an improvement of single-choice CCBOT called batch single-choice CCBOT. There are 15sℓ exponents and two rounds of communication in this protocol. In Figure 4, we formally define the protocol of batch single-choice CCBOT functionality ℱccbotS,B, and a simple example is provided in Figure 5.Figure 4
The batch single-choice CCBOT functionalityℱccbotS,B between the sender and the receiver.Figure 5
A detailed description ofℱccbotS,B where j∈J and σi=0.


## 4.1. Single-Choice CCBOT

There will be a problem that the functionalityℱccbot cannot guarantee that R inputs the identical choice-bit in the same input wire of all circuits. As we know, every bit of R’s input needs an oblivious transfer. Therefore, it must be ensured that the inputs on the same input wire of R in all garbled circuits are identical. So we propose a variant of the original CCBOT protocol. Here, we use a single-choice CCBOT functionality ℱccbotS that is implemented by modifying the CCBOT protocol during the transmission phase for ensuring that R inputs the same choice-bit in each pair of tuples. Since R uses the same choice-bit in different tuples, then the key value associated with R’s input wire only needs to be computed once so that this will reduce s−1 exponents. As a result, in this protocol, there are 29s exponents and two rounds of communication.In Figure2, we formally define the protocol of single-choice CCBOT functionality ℱccbotS, and a simple example is provided in Figure 3.Figure 2
The single-choice CCBOT functionalityℱccbotS between the sender and the receiver.Figure 3
A detailed description ofℱccbotS where j∈J and τ=0.


## 4.2. Batch Single-Choice CCBOT

Using the cut-and-choose approach requires the construction ofs circuits. Single-choice CCBOT needs to be performed on all wires in every circuit. Hence, there we use an improvement of single-choice CCBOT called batch single-choice CCBOT. There are 15sℓ exponents and two rounds of communication in this protocol. In Figure 4, we formally define the protocol of batch single-choice CCBOT functionality ℱccbotS,B, and a simple example is provided in Figure 5.Figure 4
The batch single-choice CCBOT functionalityℱccbotS,B between the sender and the receiver.Figure 5
A detailed description ofℱccbotS,B where j∈J and σi=0.


## 5. Secure Two-Party Computation Protocol

### 5.1. Protocol Description

The circuit constructorP1 first locally constructs s garbled circuits as follows. P1 chooses random value a10,a11,…,aℓ0,aℓ1 and r1,…,rs. Let the values gai0⋅r and gai1⋅r be the keys of P1’s input wire corresponding to 0 and 1 on the ith input wire in the jth circuit, respectively. The keys associated with P2’s input wires are set to be z⟶1,…,z⟶ℓ. After two parties run the batch single-choice CCBOT protocol, P2 has obtained all the keys (z⟶j, gaibi⋅rj, and gai1−bi⋅rjj∈J) on the input wires of both parties in check circuits and the keys (zyj and gaiσi⋅rjj∉J) associated with the true inputs of both parties in evaluation circuits. Next, P2 checks whether check circuits are correctly constructed and then decrypts evaluation circuits. If the output values of all evaluation circuits are inconsistent, P2 will store the garbled values b0 corresponding to 0 and b1 corresponding to 1 for the output of this output wire of different circuits, respectively, and then P1 and P2 run a check protocol for preventing cheat. Essentially, P1 and P2 run the secure protocol of reference [9], and the circuits used in the secure protocol are for computing a bit-by-bit comparison function. If the check protocol is not aborted, P2 obtains x and computes the function fx,y locally.Before giving a detailed protocol, it is worth noting that we have revised the garbled table (output translation table) commonly used in Yao’s protocol. We respectively defineki0 as the garbled value corresponding to the bit 0, ki1 as the garbled value corresponding to the bit 1 of the wire i, and H as a hash function. Therefore, the garbled table on this wire is Hki0,Hki1, where ki0≠ki1 and Hki0≠Hki1. The complete protocol is shown in Figure 6.Figure 6
Protocol of computingfx,y.


### 5.2. Proof of Security

Here, we demonstrate the security of our protocolΠ2pc that is expressed as follows through the real/ideal simulation paradigm [35].Theorem 1.
Assume that the batch single-choice CCBOT functionality in Section4.2 is secure and the DDH assumption is hard. Then, the secure protocol in Figure 6 is secure for computing function fx,y against the malicious adversary.Proof.
We analyze our secure protocolΠ2pc in a hybrid model with a trusted party. The role of this trusted party is mainly to ensure the secure operation of batch single-choice CCBOT functionality of step 2 and the zero-knowledge proof of step 7. We prove the ability of our secure protocol against the malicious adversary in two parts: the first is the case of P1 being corrupted, and the second is the case of P2 being corrupted.
P1 is corrupted: intuitively, one way for P1 to cheat is by constructing the wrong circuit. In our secure protocol Π2pc, due to the check mechanism, if the output values of evaluation circuits are inconsistent, P2 obtains the private input x of P1 via the secure computation protocol of step 6. For causing the check mechanism to fail, the output values of all evaluation circuits must not differ. In that way, only when all check circuits are correctly constructed (check passes in step 4, and then P2 decrypts evaluation circuits) and all evaluation circuits are not correctly constructed (because all evaluation circuits are wrong, no correct result output), P1 can cheat. It is worth noting that after the batch single-choice CCBOT protocol of step 2 has been run and completed, whether a circuit is a check circuit or an evaluation circuit, whether it is correct, and whether it can be calculated has been determined. Of course, P1 could also try to cheat by sending the incorrect values to the circuit input wires. However, these incorrect values do not pass the check of zero-knowledge proof, and the protocol is aborted. As a result, with the protocol in Figure 6, P2 always obtains the final result fx,y except in the case where all check circuits are correctly constructed and all evaluation circuits are incorrectly constructed, either because all the evaluation circuits are correct and output the same result or because P1 cheats so that P2 learns P1’s input x. Through the above analysis, below, we provide the formal proof.
We defineA as the adversary controlling P1 during the execution of the secure protocol. In the ideal world, there is a simulator S and a trusted party f. Simulator S plays the role of the real-world adversary A and executes the secure protocol with the trusted party f and P2. Here is how S would work in the ideal world:(1)
S obtains the inputs that the adversary A inputs to the trusted party for the batch single-choice CCBOT functionality. These inputs form a l×s matrix of pairs x0i,j,x1i,j,z0i,j,z1i.j, where i=1,…,ℓ and j=1,…,s. S play the honest P2 with input y=0ℓ.(2)
S receives s copies of the circuit GC1,…,GCs that send by A and the values i,0,gai0,i,1,gai1i=1ℓ and j,grji=1s.(3)
Under the restriction that the probability thatj belongs to J is one half, S randomly selects a subset J⊂s and sends x0i,j,x1i,j,z0i,j,z1i.j to A, where j∈J.(4)
S obtains all the keys of P1 and P2’s input wires when j∈J. Then, S decrypts the circuit through these keys and judges whether it is constructed correctly. Otherwise, S send ⊥ to the trusted party and simulates aborting.(5)
Letx=x1,…,xℓ be the witness of the zero-knowledge proof in step 7. S receives x=x1,…,xℓ from A. If one of the x1,…,xℓ is invalid, simulates aborting. Otherwise, S obtains x and sends it to the trusted party.
There we denote our secure protocol byπ. We can conclude that(3)IDEALf,Sx,y,z,n,sx,y,z∈0,1∗;n,s∈ℕ≡n,sREALπ,Ax,y,n,sx,y,z∈0,1∗;n,s∈ℕ,where x|=y.
Now, we formally calculate the probability of successful cheating forP1. Let badAll be the case where all evaluation circuits are wrongly constructed and noAbort be the case where P2 is not aborted in step 4.Claim 1.
For everys∈ℕ, it holds that(4)PrnoAbort∧badAll=12s=2−s.
For proof of security, the joint distribution must be indistinguishable, that is, the joint distribution consisting of the outputs ofA and P2 of the real execution is indistinguishable from the joint distribution consisting of the outputs of S and P2 of the ideal execution. It should be noted that since the input of P2 in the simulation is y=0ℓ, which is different from the input to P2 in the real world. This may lead to a different probability of S aborting in the simulation than in the reality of P2. In addition, We also need to show that if P2 does not abort in a real protocol execution, then the probability that it also outputs an error result is 2−s+ε⋅, where ε⋅ is a negligible function.
Here, we define good and bad circuits. From the whole protocol, we can know whether a circuit is good or bad has been determined in step 3, and it is important to note that a circuit is either good or bad. We claim that a circuit is bad if it cannot be decrypted using the keysHga10⋅rj,Hga11⋅rj,…,Hgaℓ0⋅rj,Hgaℓ0⋅rj of P1’s input and the keys corresponding to P2’s input (z01,j,z11,j,…,z0ℓ,j,z1ℓ,j) to get the correct output. These key values are part of the P1’s inputs to the batch single-choice CCBOT.
We now prove then,s−indistinguishability according to claim 1. In fact, as long as the event noAbort∧badAll does not occur, the views of the ideal and real world are identically distributed. Firstly, we discuss that if there is a check circuit that is bad, then P2 will detect and abort the protocol. Next, if all check circuits are good and at least one good circuit exists in the remaining evaluation circuits, and P2 is not aborted during the entire protocol execution, then P2 has the same output distribution in the real and simulated execution. This is due to the fact that if one of the evaluation circuits is good, then P2 must be able to get the correct output from this circuit. And if a bad circuit outputs a result different from the correct output fx,y, P2 must receive two different valid outputs on the same output wire in different evaluation circuits and saves a “proof”, then P2 will obtain P1’s private input x in step 6. Because the secure computation protocol in [9] has an error probability of 2−0.311s, so we use 3s to guarantee an error probability of 2−s+ε⋅ for step 6, As a result, P2 either obtains x or aborts the protocol in step 6. Finally, there is a case where an output wire does not output a valid value in all the evaluation circuits; then P2 aborts. This is because in this case all the evaluation circuits are wrong and P2 will continue with step 6. If there is a bad check circuit in step 6, then P2 aborts; conversely, though all check circuits are good, P2 still aborts because no valid value is received. Here, it may differ from the simulation, as it depends on the input of P2. We conclude that P2 obtains fx,y in real and ideal executions as long as no aborts occur, which is exactly the same as the view of A in the execution.
From the above analysis, we know that the adversary cannot know whether the outputfx,y of P2 is due to all evaluation circuits being correct so the outputs are the same or due to P2 detecting cheating and then learning P1’s private input x. In addition, the adversary also does not know whether P2 aborts the protocol because P1 find that the check circuit is bad or because all the evaluation circuits do not output the same result. As a result, if and only if all check circuits are good and all evaluation circuits are bad, the simulation deviates from the real output distribution. Since the probability of each circuit being good or bad is exactly 1/2, the probability of P1 cheating successfully is 2−s.
P2 is corrupted: In this case, since P1 is honest, all circuits are good, and a circuit is either a check circuit or an evaluation circuit. P2 will only obtain the same output. In other words, P2 can only obtain the same value on the same output wire of different evaluation circuits. The security here is guaranteed by the DDH assumption. However, a malicious P2 may cheat and want to obtain the private input x of P1 by the following method. P2 declares that it has obtained two different values on the same output wire of different evaluation circuits and then forges these two different values b0 and b1 in step 6 in order to obtain the value of x. In this case, since the hardcoded circuit is random and the computation protocol is secure in step 6, the probability of successful forgery is negligible. Below, we provide the formal proof.
We defineA as the adversary controlling P2 during the execution of the secure protocol Π2pc. In the ideal world, there is a simulator S and a trusted party f. Simulator S plays the role of the real-world adversary A and executes the secure protocol with the trusted party f and S. Here is how S would work in the ideal world:(1)
S obtains P2’s inputs that include y=σ1,…,σℓ and a set J⊂s from A.(2)
S sends y=σ1,…,σℓ to the trusted party and obtains the output z=fx,y.(3)
S randomly selects a pair of values b0,b1 and uses them as the input of P2 in step 6.(4)
Ifb0=bi0 and b1=bi1, then simulation aborted. Otherwise, the simulation continues according to the protocol of step 6 and then ends.
We can conclude that(5)IDEALf,Sx,y,z,n,sx,y,z∈0,1∗;n,s∈ℕ≡n,sREALπ,Ax,y,n,sx,y,z∈0,1∗;n,s∈ℕ,where x|=y.
We know that the probability ofP2 successfully forging b0 and b1 is negligible. In the following, we need to prove that when the above situation does not exist, that is, when P2 forgery fails, the output distribution of the real world and the simulated world are indistinguishable. In the ideal world, the simulation aborts if P2 is successfully faked. Conversely, if the forgery fails and the simulation continues, then the secure computing protocol in step 6 has no output, that is, P2 cannot obtain the private input of P1 (P2) only obtains fx,y from the trusted party f. In the real world, P2 obtains fx,y by decrypting the circuit, so the output distribution of the ideal world and the real world are indistinguishable.


### 5.3. Efficiency

As shown in Table1, we analyze the approximate efficiency of the entire protocol, including the exponentiations, symmetric encryptions, group elements sent, and communication rounds. According to the form, xa⋅yb only need 1.25 standard exponentiations; we calculate the exponentiations for each step: (1) 2sℓ for the input key choice and circuit preparation in step 1, (2) 15sℓ for the batch single-choice CCBOT of step 2, (3) 9sℓ for the secure check protocol of step 6, and (4) 2sℓ for verifying the consistency of P1’s input in step 7. In total, there are 28sℓ in our protocol.Table 1
Efficiency analysis of each step of our protocol.
StepExponentiationsSymmetric encryptionsGroup elements sentCommunication rounds ofℱccbotS,B/ ℱccbotS,Bwith zero-knowledge proof12sℓ8Cs2/6215sℓ11sℓ34s/2⋅8C5s/2⋅2C69sℓ39sℓ72sℓ21sℓ8Total28sℓ13Cs+39sℓ32sℓFor the symmetric encryptions, we calculate as follows:8C for each circuit construction (s circuits, total 8Cs). After running step 2, there are roughly s/2 check circuits and s/2 evaluation circuits. A total of s/2⋅8C+s/2⋅2C=5Cs symmetric encryptions are required for check and evaluation. In addition, the error probability of the security computation protocol [9] used by the check mechanism of step 6 is 2−0.311s. Therefore, 3s circuits are required so that keep the error probability at 2−s and need 3×13⋅s⋅ℓ=39sℓ. In total, there has 8Cs+5Cs+39sℓ=13Cs+39sℓ symmetric encryptions.


## 5.1. Protocol Description

The circuit constructorP1 first locally constructs s garbled circuits as follows. P1 chooses random value a10,a11,…,aℓ0,aℓ1 and r1,…,rs. Let the values gai0⋅r and gai1⋅r be the keys of P1’s input wire corresponding to 0 and 1 on the ith input wire in the jth circuit, respectively. The keys associated with P2’s input wires are set to be z⟶1,…,z⟶ℓ. After two parties run the batch single-choice CCBOT protocol, P2 has obtained all the keys (z⟶j, gaibi⋅rj, and gai1−bi⋅rjj∈J) on the input wires of both parties in check circuits and the keys (zyj and gaiσi⋅rjj∉J) associated with the true inputs of both parties in evaluation circuits. Next, P2 checks whether check circuits are correctly constructed and then decrypts evaluation circuits. If the output values of all evaluation circuits are inconsistent, P2 will store the garbled values b0 corresponding to 0 and b1 corresponding to 1 for the output of this output wire of different circuits, respectively, and then P1 and P2 run a check protocol for preventing cheat. Essentially, P1 and P2 run the secure protocol of reference [9], and the circuits used in the secure protocol are for computing a bit-by-bit comparison function. If the check protocol is not aborted, P2 obtains x and computes the function fx,y locally.Before giving a detailed protocol, it is worth noting that we have revised the garbled table (output translation table) commonly used in Yao’s protocol. We respectively defineki0 as the garbled value corresponding to the bit 0, ki1 as the garbled value corresponding to the bit 1 of the wire i, and H as a hash function. Therefore, the garbled table on this wire is Hki0,Hki1, where ki0≠ki1 and Hki0≠Hki1. The complete protocol is shown in Figure 6.Figure 6
Protocol of computingfx,y.


## 5.2. Proof of Security

Here, we demonstrate the security of our protocolΠ2pc that is expressed as follows through the real/ideal simulation paradigm [35].Theorem 1.
Assume that the batch single-choice CCBOT functionality in Section4.2 is secure and the DDH assumption is hard. Then, the secure protocol in Figure 6 is secure for computing function fx,y against the malicious adversary.Proof.
We analyze our secure protocolΠ2pc in a hybrid model with a trusted party. The role of this trusted party is mainly to ensure the secure operation of batch single-choice CCBOT functionality of step 2 and the zero-knowledge proof of step 7. We prove the ability of our secure protocol against the malicious adversary in two parts: the first is the case of P1 being corrupted, and the second is the case of P2 being corrupted.
P1 is corrupted: intuitively, one way for P1 to cheat is by constructing the wrong circuit. In our secure protocol Π2pc, due to the check mechanism, if the output values of evaluation circuits are inconsistent, P2 obtains the private input x of P1 via the secure computation protocol of step 6. For causing the check mechanism to fail, the output values of all evaluation circuits must not differ. In that way, only when all check circuits are correctly constructed (check passes in step 4, and then P2 decrypts evaluation circuits) and all evaluation circuits are not correctly constructed (because all evaluation circuits are wrong, no correct result output), P1 can cheat. It is worth noting that after the batch single-choice CCBOT protocol of step 2 has been run and completed, whether a circuit is a check circuit or an evaluation circuit, whether it is correct, and whether it can be calculated has been determined. Of course, P1 could also try to cheat by sending the incorrect values to the circuit input wires. However, these incorrect values do not pass the check of zero-knowledge proof, and the protocol is aborted. As a result, with the protocol in Figure 6, P2 always obtains the final result fx,y except in the case where all check circuits are correctly constructed and all evaluation circuits are incorrectly constructed, either because all the evaluation circuits are correct and output the same result or because P1 cheats so that P2 learns P1’s input x. Through the above analysis, below, we provide the formal proof.
We defineA as the adversary controlling P1 during the execution of the secure protocol. In the ideal world, there is a simulator S and a trusted party f. Simulator S plays the role of the real-world adversary A and executes the secure protocol with the trusted party f and P2. Here is how S would work in the ideal world:(1)
S obtains the inputs that the adversary A inputs to the trusted party for the batch single-choice CCBOT functionality. These inputs form a l×s matrix of pairs x0i,j,x1i,j,z0i,j,z1i.j, where i=1,…,ℓ and j=1,…,s. S play the honest P2 with input y=0ℓ.(2)
S receives s copies of the circuit GC1,…,GCs that send by A and the values i,0,gai0,i,1,gai1i=1ℓ and j,grji=1s.(3)
Under the restriction that the probability thatj belongs to J is one half, S randomly selects a subset J⊂s and sends x0i,j,x1i,j,z0i,j,z1i.j to A, where j∈J.(4)
S obtains all the keys of P1 and P2’s input wires when j∈J. Then, S decrypts the circuit through these keys and judges whether it is constructed correctly. Otherwise, S send ⊥ to the trusted party and simulates aborting.(5)
Letx=x1,…,xℓ be the witness of the zero-knowledge proof in step 7. S receives x=x1,…,xℓ from A. If one of the x1,…,xℓ is invalid, simulates aborting. Otherwise, S obtains x and sends it to the trusted party.
There we denote our secure protocol byπ. We can conclude that(3)IDEALf,Sx,y,z,n,sx,y,z∈0,1∗;n,s∈ℕ≡n,sREALπ,Ax,y,n,sx,y,z∈0,1∗;n,s∈ℕ,where x|=y.
Now, we formally calculate the probability of successful cheating forP1. Let badAll be the case where all evaluation circuits are wrongly constructed and noAbort be the case where P2 is not aborted in step 4.Claim 1.
For everys∈ℕ, it holds that(4)PrnoAbort∧badAll=12s=2−s.
For proof of security, the joint distribution must be indistinguishable, that is, the joint distribution consisting of the outputs ofA and P2 of the real execution is indistinguishable from the joint distribution consisting of the outputs of S and P2 of the ideal execution. It should be noted that since the input of P2 in the simulation is y=0ℓ, which is different from the input to P2 in the real world. This may lead to a different probability of S aborting in the simulation than in the reality of P2. In addition, We also need to show that if P2 does not abort in a real protocol execution, then the probability that it also outputs an error result is 2−s+ε⋅, where ε⋅ is a negligible function.
Here, we define good and bad circuits. From the whole protocol, we can know whether a circuit is good or bad has been determined in step 3, and it is important to note that a circuit is either good or bad. We claim that a circuit is bad if it cannot be decrypted using the keysHga10⋅rj,Hga11⋅rj,…,Hgaℓ0⋅rj,Hgaℓ0⋅rj of P1’s input and the keys corresponding to P2’s input (z01,j,z11,j,…,z0ℓ,j,z1ℓ,j) to get the correct output. These key values are part of the P1’s inputs to the batch single-choice CCBOT.
We now prove then,s−indistinguishability according to claim 1. In fact, as long as the event noAbort∧badAll does not occur, the views of the ideal and real world are identically distributed. Firstly, we discuss that if there is a check circuit that is bad, then P2 will detect and abort the protocol. Next, if all check circuits are good and at least one good circuit exists in the remaining evaluation circuits, and P2 is not aborted during the entire protocol execution, then P2 has the same output distribution in the real and simulated execution. This is due to the fact that if one of the evaluation circuits is good, then P2 must be able to get the correct output from this circuit. And if a bad circuit outputs a result different from the correct output fx,y, P2 must receive two different valid outputs on the same output wire in different evaluation circuits and saves a “proof”, then P2 will obtain P1’s private input x in step 6. Because the secure computation protocol in [9] has an error probability of 2−0.311s, so we use 3s to guarantee an error probability of 2−s+ε⋅ for step 6, As a result, P2 either obtains x or aborts the protocol in step 6. Finally, there is a case where an output wire does not output a valid value in all the evaluation circuits; then P2 aborts. This is because in this case all the evaluation circuits are wrong and P2 will continue with step 6. If there is a bad check circuit in step 6, then P2 aborts; conversely, though all check circuits are good, P2 still aborts because no valid value is received. Here, it may differ from the simulation, as it depends on the input of P2. We conclude that P2 obtains fx,y in real and ideal executions as long as no aborts occur, which is exactly the same as the view of A in the execution.
From the above analysis, we know that the adversary cannot know whether the outputfx,y of P2 is due to all evaluation circuits being correct so the outputs are the same or due to P2 detecting cheating and then learning P1’s private input x. In addition, the adversary also does not know whether P2 aborts the protocol because P1 find that the check circuit is bad or because all the evaluation circuits do not output the same result. As a result, if and only if all check circuits are good and all evaluation circuits are bad, the simulation deviates from the real output distribution. Since the probability of each circuit being good or bad is exactly 1/2, the probability of P1 cheating successfully is 2−s.
P2 is corrupted: In this case, since P1 is honest, all circuits are good, and a circuit is either a check circuit or an evaluation circuit. P2 will only obtain the same output. In other words, P2 can only obtain the same value on the same output wire of different evaluation circuits. The security here is guaranteed by the DDH assumption. However, a malicious P2 may cheat and want to obtain the private input x of P1 by the following method. P2 declares that it has obtained two different values on the same output wire of different evaluation circuits and then forges these two different values b0 and b1 in step 6 in order to obtain the value of x. In this case, since the hardcoded circuit is random and the computation protocol is secure in step 6, the probability of successful forgery is negligible. Below, we provide the formal proof.
We defineA as the adversary controlling P2 during the execution of the secure protocol Π2pc. In the ideal world, there is a simulator S and a trusted party f. Simulator S plays the role of the real-world adversary A and executes the secure protocol with the trusted party f and S. Here is how S would work in the ideal world:(1)
S obtains P2’s inputs that include y=σ1,…,σℓ and a set J⊂s from A.(2)
S sends y=σ1,…,σℓ to the trusted party and obtains the output z=fx,y.(3)
S randomly selects a pair of values b0,b1 and uses them as the input of P2 in step 6.(4)
Ifb0=bi0 and b1=bi1, then simulation aborted. Otherwise, the simulation continues according to the protocol of step 6 and then ends.
We can conclude that(5)IDEALf,Sx,y,z,n,sx,y,z∈0,1∗;n,s∈ℕ≡n,sREALπ,Ax,y,n,sx,y,z∈0,1∗;n,s∈ℕ,where x|=y.
We know that the probability ofP2 successfully forging b0 and b1 is negligible. In the following, we need to prove that when the above situation does not exist, that is, when P2 forgery fails, the output distribution of the real world and the simulated world are indistinguishable. In the ideal world, the simulation aborts if P2 is successfully faked. Conversely, if the forgery fails and the simulation continues, then the secure computing protocol in step 6 has no output, that is, P2 cannot obtain the private input of P1 (P2) only obtains fx,y from the trusted party f. In the real world, P2 obtains fx,y by decrypting the circuit, so the output distribution of the ideal world and the real world are indistinguishable.


## 5.3. Efficiency

As shown in Table1, we analyze the approximate efficiency of the entire protocol, including the exponentiations, symmetric encryptions, group elements sent, and communication rounds. According to the form, xa⋅yb only need 1.25 standard exponentiations; we calculate the exponentiations for each step: (1) 2sℓ for the input key choice and circuit preparation in step 1, (2) 15sℓ for the batch single-choice CCBOT of step 2, (3) 9sℓ for the secure check protocol of step 6, and (4) 2sℓ for verifying the consistency of P1’s input in step 7. In total, there are 28sℓ in our protocol.Table 1
Efficiency analysis of each step of our protocol.
StepExponentiationsSymmetric encryptionsGroup elements sentCommunication rounds ofℱccbotS,B/ ℱccbotS,Bwith zero-knowledge proof12sℓ8Cs2/6215sℓ11sℓ34s/2⋅8C5s/2⋅2C69sℓ39sℓ72sℓ21sℓ8Total28sℓ13Cs+39sℓ32sℓFor the symmetric encryptions, we calculate as follows:8C for each circuit construction (s circuits, total 8Cs). After running step 2, there are roughly s/2 check circuits and s/2 evaluation circuits. A total of s/2⋅8C+s/2⋅2C=5Cs symmetric encryptions are required for check and evaluation. In addition, the error probability of the security computation protocol [9] used by the check mechanism of step 6 is 2−0.311s. Therefore, 3s circuits are required so that keep the error probability at 2−s and need 3×13⋅s⋅ℓ=39sℓ. In total, there has 8Cs+5Cs+39sℓ=13Cs+39sℓ symmetric encryptions.


## 6. Conclusion

In this paper, we propose an improvement of CCBOT that is called batch single-choice CCBOT. We formalize our batch single-choice CCBOT function and apply it to Yao’s protocol and then present a new secure two-party computation protocol that achieves security against the malicious adversary. Our new protocol not only can reduce the number of interactive rounds of the protocol but also can solve the problem of input consistency and prevent selective failure attacks. In addition, a check mechanism is used to preventP1 from cheating but P2 is powerless and the probability of error for P2 is 2-sIn the future, we will continue to study common secure computation protocols, focusing on efficient constant-round secure multiparty based on garbled circuits in the malicious model.



---

*Source: 3880413-2022-06-27.xml*