# Postquantum Cut-and-Choose Oblivious Transfer Protocol Based on LWE

Authors: Hangchao Ding; Han Jiang; Qiuliang Xu
Journal: Security and Communication Networks
 (2021)

---

## Abstract

We propose postquantum universal composable (UC) cut-and-choose oblivious transfer (CCOT) protocol under the malicious adversary model. In secure two-party computation, we constructs copies’ garbled circuits, including half check circuit and half evaluation circuit. The sender can transfer the key to the receiver by CCOT protocol. Compared to PVW-OT [6] framework, we invoke WQ-OT [35] framework with reusability of common random string (crs) and better security. Relying on LWE’s assumption and the property of the Rounding function, we construct an UC-CCOT protocol, which can resist quantum attack in secure two-party computation.


---

## Body

## 1. Introduction

### 1.1. Background

In secure two-party computation, senderP1 and receiver P2 jointly compute the value of function fx,y. P1 inputs x and P2 inputs y. Then, P1 and P2 obtain the value of fx,y. Yao’s garbled circuits, used in secure two-party computation, are only secure in the semihonest adversary model. In Yao’s protocol, a single garbled circuit is constructed to evaluate. For better security, we apply s copies garbled circuits in secure two-party computation. For constructing secure protocol under the malicious adversary model, cut-and-choose methodology is used to prevent malicious party from cheating by constructing incorrect garbled circuits in secure two-party computation. This methodology needs to construct s copies’ garbled circuits.Secure two-party computation protocol is implemented byGarbled Circuit (GC). Sender P1 and receiver P2 jointly compute the value of fx,y by computing Cx,y (fx,y=Cx,y), which satisfy security, privacy, correctness, and input’s independence. In 1986, Yao [1] proposed a secure two-party computation protocol, which is mainly based on GC and Oblivious Transfer (OT).Yao’s protocol is only secure and efficient in the semihonest adversary model. However, this protocol cannot obtain the security of the malicious adversary model. In 1987, Goldreich and Micali [2] proposed a GMW compiler, which can compile protocols under the semihonest adversary model to protocols under the malicious adversary model. Application for the GMW compiler needs a number of zero-knowledge proof and commitment mechanisms. This operation results in high complexity and low efficiency. Construction of Universal Composable (UC) protocol under the malicious adversary model has great significance in secure two-party computation.In Yao’s protocol, senderP1 constructs a garbled circuit, including 2n wires. In these wires, each wire corresponds to a garbled circuit key kib,b∈0,1, where b represents the corresponding value of wires. Sender P1 inputs X=x1,x2,…,xn, xi∈0,1, in n copies’ wires, Receiver P2 inputs Y=y1,y2,…,yn,yi∈0,1, in remaining n copies’ wires. P1 sends X and k1x1,k2x2,…,knxn to P2. P2, as the circuit evaluator, needs P1’s input’s value X and corresponding garbled circuit key’s value. For computing CX,Y, P2 inputs Y and needs corresponding key’s value in remaining wires. P2 needs to obtain corresponding key’s value about Y=y1,y2,…,yn. It means that P2 needs to obtain corresponding kn+iyi from kn+i0,kn+i1,i=1,2,…,n. So, P2 can apply OT protocol to obtain corresponding garbled key’s value.


### 1.2. Related Work

#### 1.2.1. Oblivious Transfer

OT protocol, as a basic building primitive in cryptography, has great security significance in secure two-party computation or multiparty computation. For better, intuitively, understandingOT21 protocol, we give a brief introduction about its ideal function FOT in Figure 1.Figure 1
The ideal functionFOT.Denote ideal functionFOT:m0,m1×σ⟶⊥,mσ. For better understanding this process on the Internet, we consider session identity sid for our description. This function is implemented by the interaction between the sender S and the receiver R.For understanding the ideal function FOT, we introduce an OT21protocol for understanding OT’s role in Figure 2. The sender has two-message m0 and m1. The receiver wants to obtain message mσ, σ∈0,1. Then, the sender and the receiver apply OT21 protocol. The receiver can obtain message mσ. In this process, the sender has no information about receiver’s selected bit σ. The receiver has no information about m1−σ.Figure 2
The process of the OT protocol.The OT protocol can be constructed by the public key encryption (PKE) system or trapdoor permutation function. We consider constructing a PKE-based OT protocol. Next, we introduce this construction, given a series of PKE algorithmsKeyGen,Enc,Dec as follows:


#### 1.2.2. Cut-and-Choose Technique

For better understanding the importance of cut-and-choose technique in secure two-party computation, firstly, we give a brief description about basic Yao’s protocol in Figure3, which is the original secure two-party computation protocol.Figure 3
Yao’s protocol.Yao’s protocol, used to compute the function, is only secure in the semihonest adversary model, which is just based on a single garbled circuit for evaluation. The circuit of this construction is not enough secure, which cannot obtain malicious adversary’s security. Considering its single garbled circuit, if someone cheats in this protocol, it cannot be detected. It can be solved by applying the GMW compiler to obtain malicious adversary’s security. However, this needs extracomputation.For correctly computing the value of functionfx,y, it is better to construct many circuits for computation. Circuit constructor constructs many garbled circuits and sends these circuits to the circuit evaluator. Then, some circuits are used for check circuit and used to check the correctness of garbled circuits. Some circuits are used for evaluation circuit, for evaluating the value of function. This technique is called cut-and-choose methodology, meaning cutting some garbled circuits in the first step and then choosing some circuits for checking in the second step.Cut-and-choose methodology, as a tool used in secure two-party computation, can prevent the circuit constructor from cheating in constructing incorrect circuits. This technique can reduce the use of zero-knowledge proof techniques, which can improve the efficiency of secure computation protocols.For better understanding this process, we give a brief description about cut-and-choose process in Figure4. Here, we mainly introduce a universal technique “cut‐and‐choose” methodology.Figure 4
Cut-and-choose methodology.Firstly,P1 constructs s copies’ garbled circuits and sends these circuits to P2. Secondly, P2 chooses s/2 circuits for checking. Denote set CGC as check-circuit set, including s/2 copies’ check circuits. Otherwise, the rest of s/2 circuits are used for evaluating circuits. Define EGC as evaluation-circuit set. P2 obtains check circuits for checking correctness of half circuits and then evaluates fx,y in remaining evaluation circuits. Some garbled circuits maybe incorrectly constructed, so evaluator P2 can use majority of evaluation-circuit output as value of fx,y.Considering cut-and-choose technique applied on secure two-party computation,P1 may carry out select failure attack for P2. P1 may use different input values to obtain different ciphertexts and confuse some values about index bit j from P2’s evaluation set. The main reason about this attack is the separation between cut-and-choose methodology with oblivious transfer process. So, it is crucial to combine cut-and-choose methodology with oblivious transfer protocol, called the CCOT protocol.OT is a basic protocol in secure two-party computation, whereP1 sends garbled key’s value of every wire in the garbled circuit to P2. If cut-and-choose methodology is separated from the OT protocol, this separation may result in selection failure attack. It is crucial to combine cut−and−choose methodology with the OT protocol, that is, cut−and−choose oblivious transfer (CCOT) protocol. This has crucial significance about security in secure two-party computation protocol.


#### 1.2.3. Related Reference

OT was firstly proposed by Rabin [3]. OT is a fundamental primitive in secure two-party and multiparty computation. In secure two-party computation, receiver P2 obtains one or two values from sender P1 through the OT protocol. As a result, receiver P2 only obtains corresponding values and has nothing about other information. Sender P1 is oblivious to P2’s selection bit. In 2007, Peikert and Waters [4] proposed a primitive ‘lossy trapdoor functions’ (lossy TDFs) and applied ‘lossy TDFs’ to construct trapdoor function. In 2008, Peikert and Vaikuntanathan [5] proposed a framework for efficient and composable OT, which is constructed by the dual-mode PKE System, called PVW-OT framework. In Peikert’s dual-mode encryption system, it includes messy mode and decryption mode (called Dec mode). However, common random string (crs) can be reused with bounded limitation. Sender’s computational security in messy mode and receiver’s computational security in Dec mode can be obtained in this scheme. However, it cannot suffice for each party’s statistical security in both modes. Peikert also construct corresponding schemes based on DDH, QR, and LWE’s assumption. Fully simulatable PVW-OT protocol’s security is universally composable (UC), which can compose securely other protocols in complex Internet. UC security is proposed by Canetti [6]. This guarantees security when many protocols are executed in parallel under malicious adversary’s environment. Some lattice-based oblivious transfer protocols are proposed in postquantum era; most of these protocols are based on LWE’s assumption under the semihonest, malicious, or covert adversary model [7–9].In 2020, Quach [10] proposed a UC-secure OT protocol based on LWE’s assumption and rounding function, which can be seen as a modified framework of PVW-OT, called WQ-OT. In WQ-OT protocol, the rounding function is applied on constructing UC-OT. Considering that the rounding function is a smooth projective hash function (SPHF), it can be applied on our scheme with the property of rounding function’s hash key and projective key. In WQ-OT, crs can be reused many times without limitation, and statistical security of the sender and the receiver can be obtained in both messy mode and Dec mode.SPHF has a wide range of applications, such as key exchange and oblivious transfer [11, 12]. In 2012, Halevi and Kalai [13] proposed a two-message OT, which is based on projective hashing function. Cramer and Shoup [14] proposed a universal hash proof in the standard model, which corresponds to adaptive-CCA secure public-key encryption. Kalai [13] proposed a two-message oblivious transfer based on modification of Cramer and Shoup’s SPHF. In 2018, Benhamouda and Blazy [15] proposed a hash proof system or SPHF. It gives an SPHF under standard LWE ciphertext’s languages, which is based on IND-CCA2 MP’s encryption [16]. Before this SPHF proposed by Benhamouda, Katz and Vaikuntanathan [11, 17] proposed a SPHF based on lattice in the standard model, whose language is not valid in standard LWE’s ciphertext. Zhang and Yu [18] proposed a SPHF based on LWE’s assumption under random oracle. Brakerski [19] proposed a two-message OT based on LWE’s assumption which guarantees sender’s statistical privacy under the model of malicious adversary.In 2007, Lindell and Pinkas [20] proposed cut-and-choose technique for secure two-party computation under the malicious adversary model. Circuit constructor P1 constructs s copies’ GC. Circuit evaluator P2 chooses s/2 copies’ GC for check circuit and remaining half s/2 copies’ GC for evaluation circuit. P2 checks correctness of the key’s value in each wire of check garbled circuit. P1 and P2 apply remaining half garbled circuits for computing fx,y.In secure two-party computation, cut-and-choose methodology can be applied to prevent malicious adversary from cheating in this process. As an important technique in secure two-party computation, cut-and-choose is applied to normalize and constrain parties for honestly executing protocols in garbled circuits. In cut-and-choose methodology, constructorP1 constructs s copies’ garbled circuits. Evaluator P2 chooses some garbled circuits for checking. When these check circuits are correctly constructed, the evaluator applies remaining garbled circuits to evaluate corresponding function by evaluation circuits.In this process, the OT protocol is applied for transferring corresponding key’s value through wires of the garbled circuit. The OT protocol can be applied on transferring senderP1’s key to receiver P2 through garbled circuit’s wires. If these two processes are done separately, the overall protocol may lead to selective-failure attacks, which are introduced in [20, 21]. Combining cut-and-choose detection with oblivious transfer, we can transfer keys by wires between the sender (circuit constructor) and the receiver (circuit evaluator).Lindell [22] applied cut-and-choose methodology [20] for constructing fully simulatable OT protocols. Lindell [23] proposed a new primitive in secure two-party computation, called CCOT protocol, which can avoid selective-failure attacks. After CCOT primitive proposed by Lindell, some scholars have proposed some schemes about construction of CCOT, which are mostly modified CCOT protocol, such as batch CCOT and bilateral CCOT [24–28].TraditionalOT21 are applied in transferring key or message by number theory’s assumption, such as DDH and QR assumption. Classical number theory assumptions cannot resist quantum attacks. It is necessary to design postquantum cryptography schemes. Considering lattice’s specific linear structure, lattice-based protocols can be applied to resist quantum attacks.There exist some cryptographic protocols based on lattice’s assumption, which can resist quantum attack with the specific construction of lattice. Reduction from worst case to average case in lattice, trapdoors algorithm and some lattice theory are mentioned in [29–32].In secure two-party computation, the CCOT protocol can resist malicious adversary’s attack. Considering postquantum era, designing the CCOT protocol based on lattice assumption can resist quantum attacks. Combining with lattice theory, designing LWE-based CCOT protocol is of great significance to resist quantum attacks in secure two-party computation. Then, we can expand CCOT to batch-CCOT protocol, which can be applied on secure multiparty computation.


### 1.3. Our Contribution

(i)
We construct a CCOT protocol based on LWE’s assumption and rounding function. Applying WQ-OT [10] encryption scheme based on the rounding function and combining with PVW’s dual framework [5], we design a UC-secure cut-and-choose OT protocol under the malicious adversary model.(ii)
Our CCOT protocol has better security property. For better understanding CCOT’s security, we give a security analysis under the malicious adversary’s corruption in smooth projective hash proof system, which is mainly based on simulation proof methodology.(iii)
In our scheme,crs can be reused many times, and all parties can achieve statistical security. The rounding function, as smooth projective hash function (SPHF), has better security in transferring P1’s garbled key to P2. Due to the special property of the hash key and the projective key, this rounding function can guarantee CCOT protocol’s correctness, privacy, and indistinguishability between the Messy mode and Dec mode.(iv)
Apply the CCOT protocol on secure two-party computation, which is mainly based on garbled circuits.


### 1.4. Organization

(i)
In Section1, we give an overall introduction about background, related work about the CCOT protocol. Finally, we give our contribution and paper’s organization.(ii)
In Section2, we mainly introduce some preliminaries about lattice theory and some knowledge used in scheme’s construction.(iii)
In Section3, we introduce some basic tools applied on our scheme. It includes OT-based dual-mode encryption, which is initiated by Regev’s encryption and rounding function. As an important methodology in secure two-party computation, cut-and-choose technique is also introduced in this part. This dual-mode encryption’s framework security is mostly based on LWE’s assumption, where indistinguishability between the Messy Mode and the Dec Mode is based on DLWE’s assumption.(iv)
In Section4, cut-and-choose oblivious transfer (CCOT) protocol, as an important protocol, is applied on secure two-party computation. We construct a CCOT protocol and embed this CCOT protocol into secure two-party computation. Then, we expand CCOT to BCCOT by batch operation and embed this BCCOT protocol into secure two-party computation.


## 1.1. Background

In secure two-party computation, senderP1 and receiver P2 jointly compute the value of function fx,y. P1 inputs x and P2 inputs y. Then, P1 and P2 obtain the value of fx,y. Yao’s garbled circuits, used in secure two-party computation, are only secure in the semihonest adversary model. In Yao’s protocol, a single garbled circuit is constructed to evaluate. For better security, we apply s copies garbled circuits in secure two-party computation. For constructing secure protocol under the malicious adversary model, cut-and-choose methodology is used to prevent malicious party from cheating by constructing incorrect garbled circuits in secure two-party computation. This methodology needs to construct s copies’ garbled circuits.Secure two-party computation protocol is implemented byGarbled Circuit (GC). Sender P1 and receiver P2 jointly compute the value of fx,y by computing Cx,y (fx,y=Cx,y), which satisfy security, privacy, correctness, and input’s independence. In 1986, Yao [1] proposed a secure two-party computation protocol, which is mainly based on GC and Oblivious Transfer (OT).Yao’s protocol is only secure and efficient in the semihonest adversary model. However, this protocol cannot obtain the security of the malicious adversary model. In 1987, Goldreich and Micali [2] proposed a GMW compiler, which can compile protocols under the semihonest adversary model to protocols under the malicious adversary model. Application for the GMW compiler needs a number of zero-knowledge proof and commitment mechanisms. This operation results in high complexity and low efficiency. Construction of Universal Composable (UC) protocol under the malicious adversary model has great significance in secure two-party computation.In Yao’s protocol, senderP1 constructs a garbled circuit, including 2n wires. In these wires, each wire corresponds to a garbled circuit key kib,b∈0,1, where b represents the corresponding value of wires. Sender P1 inputs X=x1,x2,…,xn, xi∈0,1, in n copies’ wires, Receiver P2 inputs Y=y1,y2,…,yn,yi∈0,1, in remaining n copies’ wires. P1 sends X and k1x1,k2x2,…,knxn to P2. P2, as the circuit evaluator, needs P1’s input’s value X and corresponding garbled circuit key’s value. For computing CX,Y, P2 inputs Y and needs corresponding key’s value in remaining wires. P2 needs to obtain corresponding key’s value about Y=y1,y2,…,yn. It means that P2 needs to obtain corresponding kn+iyi from kn+i0,kn+i1,i=1,2,…,n. So, P2 can apply OT protocol to obtain corresponding garbled key’s value.


## 1.2. Related Work

### 1.2.1. Oblivious Transfer

OT protocol, as a basic building primitive in cryptography, has great security significance in secure two-party computation or multiparty computation. For better, intuitively, understandingOT21 protocol, we give a brief introduction about its ideal function FOT in Figure 1.Figure 1
The ideal functionFOT.Denote ideal functionFOT:m0,m1×σ⟶⊥,mσ. For better understanding this process on the Internet, we consider session identity sid for our description. This function is implemented by the interaction between the sender S and the receiver R.For understanding the ideal function FOT, we introduce an OT21protocol for understanding OT’s role in Figure 2. The sender has two-message m0 and m1. The receiver wants to obtain message mσ, σ∈0,1. Then, the sender and the receiver apply OT21 protocol. The receiver can obtain message mσ. In this process, the sender has no information about receiver’s selected bit σ. The receiver has no information about m1−σ.Figure 2
The process of the OT protocol.The OT protocol can be constructed by the public key encryption (PKE) system or trapdoor permutation function. We consider constructing a PKE-based OT protocol. Next, we introduce this construction, given a series of PKE algorithmsKeyGen,Enc,Dec as follows:


### 1.2.2. Cut-and-Choose Technique

For better understanding the importance of cut-and-choose technique in secure two-party computation, firstly, we give a brief description about basic Yao’s protocol in Figure3, which is the original secure two-party computation protocol.Figure 3
Yao’s protocol.Yao’s protocol, used to compute the function, is only secure in the semihonest adversary model, which is just based on a single garbled circuit for evaluation. The circuit of this construction is not enough secure, which cannot obtain malicious adversary’s security. Considering its single garbled circuit, if someone cheats in this protocol, it cannot be detected. It can be solved by applying the GMW compiler to obtain malicious adversary’s security. However, this needs extracomputation.For correctly computing the value of functionfx,y, it is better to construct many circuits for computation. Circuit constructor constructs many garbled circuits and sends these circuits to the circuit evaluator. Then, some circuits are used for check circuit and used to check the correctness of garbled circuits. Some circuits are used for evaluation circuit, for evaluating the value of function. This technique is called cut-and-choose methodology, meaning cutting some garbled circuits in the first step and then choosing some circuits for checking in the second step.Cut-and-choose methodology, as a tool used in secure two-party computation, can prevent the circuit constructor from cheating in constructing incorrect circuits. This technique can reduce the use of zero-knowledge proof techniques, which can improve the efficiency of secure computation protocols.For better understanding this process, we give a brief description about cut-and-choose process in Figure4. Here, we mainly introduce a universal technique “cut‐and‐choose” methodology.Figure 4
Cut-and-choose methodology.Firstly,P1 constructs s copies’ garbled circuits and sends these circuits to P2. Secondly, P2 chooses s/2 circuits for checking. Denote set CGC as check-circuit set, including s/2 copies’ check circuits. Otherwise, the rest of s/2 circuits are used for evaluating circuits. Define EGC as evaluation-circuit set. P2 obtains check circuits for checking correctness of half circuits and then evaluates fx,y in remaining evaluation circuits. Some garbled circuits maybe incorrectly constructed, so evaluator P2 can use majority of evaluation-circuit output as value of fx,y.Considering cut-and-choose technique applied on secure two-party computation,P1 may carry out select failure attack for P2. P1 may use different input values to obtain different ciphertexts and confuse some values about index bit j from P2’s evaluation set. The main reason about this attack is the separation between cut-and-choose methodology with oblivious transfer process. So, it is crucial to combine cut-and-choose methodology with oblivious transfer protocol, called the CCOT protocol.OT is a basic protocol in secure two-party computation, whereP1 sends garbled key’s value of every wire in the garbled circuit to P2. If cut-and-choose methodology is separated from the OT protocol, this separation may result in selection failure attack. It is crucial to combine cut−and−choose methodology with the OT protocol, that is, cut−and−choose oblivious transfer (CCOT) protocol. This has crucial significance about security in secure two-party computation protocol.


### 1.2.3. Related Reference

OT was firstly proposed by Rabin [3]. OT is a fundamental primitive in secure two-party and multiparty computation. In secure two-party computation, receiver P2 obtains one or two values from sender P1 through the OT protocol. As a result, receiver P2 only obtains corresponding values and has nothing about other information. Sender P1 is oblivious to P2’s selection bit. In 2007, Peikert and Waters [4] proposed a primitive ‘lossy trapdoor functions’ (lossy TDFs) and applied ‘lossy TDFs’ to construct trapdoor function. In 2008, Peikert and Vaikuntanathan [5] proposed a framework for efficient and composable OT, which is constructed by the dual-mode PKE System, called PVW-OT framework. In Peikert’s dual-mode encryption system, it includes messy mode and decryption mode (called Dec mode). However, common random string (crs) can be reused with bounded limitation. Sender’s computational security in messy mode and receiver’s computational security in Dec mode can be obtained in this scheme. However, it cannot suffice for each party’s statistical security in both modes. Peikert also construct corresponding schemes based on DDH, QR, and LWE’s assumption. Fully simulatable PVW-OT protocol’s security is universally composable (UC), which can compose securely other protocols in complex Internet. UC security is proposed by Canetti [6]. This guarantees security when many protocols are executed in parallel under malicious adversary’s environment. Some lattice-based oblivious transfer protocols are proposed in postquantum era; most of these protocols are based on LWE’s assumption under the semihonest, malicious, or covert adversary model [7–9].In 2020, Quach [10] proposed a UC-secure OT protocol based on LWE’s assumption and rounding function, which can be seen as a modified framework of PVW-OT, called WQ-OT. In WQ-OT protocol, the rounding function is applied on constructing UC-OT. Considering that the rounding function is a smooth projective hash function (SPHF), it can be applied on our scheme with the property of rounding function’s hash key and projective key. In WQ-OT, crs can be reused many times without limitation, and statistical security of the sender and the receiver can be obtained in both messy mode and Dec mode.SPHF has a wide range of applications, such as key exchange and oblivious transfer [11, 12]. In 2012, Halevi and Kalai [13] proposed a two-message OT, which is based on projective hashing function. Cramer and Shoup [14] proposed a universal hash proof in the standard model, which corresponds to adaptive-CCA secure public-key encryption. Kalai [13] proposed a two-message oblivious transfer based on modification of Cramer and Shoup’s SPHF. In 2018, Benhamouda and Blazy [15] proposed a hash proof system or SPHF. It gives an SPHF under standard LWE ciphertext’s languages, which is based on IND-CCA2 MP’s encryption [16]. Before this SPHF proposed by Benhamouda, Katz and Vaikuntanathan [11, 17] proposed a SPHF based on lattice in the standard model, whose language is not valid in standard LWE’s ciphertext. Zhang and Yu [18] proposed a SPHF based on LWE’s assumption under random oracle. Brakerski [19] proposed a two-message OT based on LWE’s assumption which guarantees sender’s statistical privacy under the model of malicious adversary.In 2007, Lindell and Pinkas [20] proposed cut-and-choose technique for secure two-party computation under the malicious adversary model. Circuit constructor P1 constructs s copies’ GC. Circuit evaluator P2 chooses s/2 copies’ GC for check circuit and remaining half s/2 copies’ GC for evaluation circuit. P2 checks correctness of the key’s value in each wire of check garbled circuit. P1 and P2 apply remaining half garbled circuits for computing fx,y.In secure two-party computation, cut-and-choose methodology can be applied to prevent malicious adversary from cheating in this process. As an important technique in secure two-party computation, cut-and-choose is applied to normalize and constrain parties for honestly executing protocols in garbled circuits. In cut-and-choose methodology, constructorP1 constructs s copies’ garbled circuits. Evaluator P2 chooses some garbled circuits for checking. When these check circuits are correctly constructed, the evaluator applies remaining garbled circuits to evaluate corresponding function by evaluation circuits.In this process, the OT protocol is applied for transferring corresponding key’s value through wires of the garbled circuit. The OT protocol can be applied on transferring senderP1’s key to receiver P2 through garbled circuit’s wires. If these two processes are done separately, the overall protocol may lead to selective-failure attacks, which are introduced in [20, 21]. Combining cut-and-choose detection with oblivious transfer, we can transfer keys by wires between the sender (circuit constructor) and the receiver (circuit evaluator).Lindell [22] applied cut-and-choose methodology [20] for constructing fully simulatable OT protocols. Lindell [23] proposed a new primitive in secure two-party computation, called CCOT protocol, which can avoid selective-failure attacks. After CCOT primitive proposed by Lindell, some scholars have proposed some schemes about construction of CCOT, which are mostly modified CCOT protocol, such as batch CCOT and bilateral CCOT [24–28].TraditionalOT21 are applied in transferring key or message by number theory’s assumption, such as DDH and QR assumption. Classical number theory assumptions cannot resist quantum attacks. It is necessary to design postquantum cryptography schemes. Considering lattice’s specific linear structure, lattice-based protocols can be applied to resist quantum attacks.There exist some cryptographic protocols based on lattice’s assumption, which can resist quantum attack with the specific construction of lattice. Reduction from worst case to average case in lattice, trapdoors algorithm and some lattice theory are mentioned in [29–32].In secure two-party computation, the CCOT protocol can resist malicious adversary’s attack. Considering postquantum era, designing the CCOT protocol based on lattice assumption can resist quantum attacks. Combining with lattice theory, designing LWE-based CCOT protocol is of great significance to resist quantum attacks in secure two-party computation. Then, we can expand CCOT to batch-CCOT protocol, which can be applied on secure multiparty computation.


## 1.2.1. Oblivious Transfer

OT protocol, as a basic building primitive in cryptography, has great security significance in secure two-party computation or multiparty computation. For better, intuitively, understandingOT21 protocol, we give a brief introduction about its ideal function FOT in Figure 1.Figure 1
The ideal functionFOT.Denote ideal functionFOT:m0,m1×σ⟶⊥,mσ. For better understanding this process on the Internet, we consider session identity sid for our description. This function is implemented by the interaction between the sender S and the receiver R.For understanding the ideal function FOT, we introduce an OT21protocol for understanding OT’s role in Figure 2. The sender has two-message m0 and m1. The receiver wants to obtain message mσ, σ∈0,1. Then, the sender and the receiver apply OT21 protocol. The receiver can obtain message mσ. In this process, the sender has no information about receiver’s selected bit σ. The receiver has no information about m1−σ.Figure 2
The process of the OT protocol.The OT protocol can be constructed by the public key encryption (PKE) system or trapdoor permutation function. We consider constructing a PKE-based OT protocol. Next, we introduce this construction, given a series of PKE algorithmsKeyGen,Enc,Dec as follows:


## 1.2.2. Cut-and-Choose Technique

For better understanding the importance of cut-and-choose technique in secure two-party computation, firstly, we give a brief description about basic Yao’s protocol in Figure3, which is the original secure two-party computation protocol.Figure 3
Yao’s protocol.Yao’s protocol, used to compute the function, is only secure in the semihonest adversary model, which is just based on a single garbled circuit for evaluation. The circuit of this construction is not enough secure, which cannot obtain malicious adversary’s security. Considering its single garbled circuit, if someone cheats in this protocol, it cannot be detected. It can be solved by applying the GMW compiler to obtain malicious adversary’s security. However, this needs extracomputation.For correctly computing the value of functionfx,y, it is better to construct many circuits for computation. Circuit constructor constructs many garbled circuits and sends these circuits to the circuit evaluator. Then, some circuits are used for check circuit and used to check the correctness of garbled circuits. Some circuits are used for evaluation circuit, for evaluating the value of function. This technique is called cut-and-choose methodology, meaning cutting some garbled circuits in the first step and then choosing some circuits for checking in the second step.Cut-and-choose methodology, as a tool used in secure two-party computation, can prevent the circuit constructor from cheating in constructing incorrect circuits. This technique can reduce the use of zero-knowledge proof techniques, which can improve the efficiency of secure computation protocols.For better understanding this process, we give a brief description about cut-and-choose process in Figure4. Here, we mainly introduce a universal technique “cut‐and‐choose” methodology.Figure 4
Cut-and-choose methodology.Firstly,P1 constructs s copies’ garbled circuits and sends these circuits to P2. Secondly, P2 chooses s/2 circuits for checking. Denote set CGC as check-circuit set, including s/2 copies’ check circuits. Otherwise, the rest of s/2 circuits are used for evaluating circuits. Define EGC as evaluation-circuit set. P2 obtains check circuits for checking correctness of half circuits and then evaluates fx,y in remaining evaluation circuits. Some garbled circuits maybe incorrectly constructed, so evaluator P2 can use majority of evaluation-circuit output as value of fx,y.Considering cut-and-choose technique applied on secure two-party computation,P1 may carry out select failure attack for P2. P1 may use different input values to obtain different ciphertexts and confuse some values about index bit j from P2’s evaluation set. The main reason about this attack is the separation between cut-and-choose methodology with oblivious transfer process. So, it is crucial to combine cut-and-choose methodology with oblivious transfer protocol, called the CCOT protocol.OT is a basic protocol in secure two-party computation, whereP1 sends garbled key’s value of every wire in the garbled circuit to P2. If cut-and-choose methodology is separated from the OT protocol, this separation may result in selection failure attack. It is crucial to combine cut−and−choose methodology with the OT protocol, that is, cut−and−choose oblivious transfer (CCOT) protocol. This has crucial significance about security in secure two-party computation protocol.


## 1.2.3. Related Reference

OT was firstly proposed by Rabin [3]. OT is a fundamental primitive in secure two-party and multiparty computation. In secure two-party computation, receiver P2 obtains one or two values from sender P1 through the OT protocol. As a result, receiver P2 only obtains corresponding values and has nothing about other information. Sender P1 is oblivious to P2’s selection bit. In 2007, Peikert and Waters [4] proposed a primitive ‘lossy trapdoor functions’ (lossy TDFs) and applied ‘lossy TDFs’ to construct trapdoor function. In 2008, Peikert and Vaikuntanathan [5] proposed a framework for efficient and composable OT, which is constructed by the dual-mode PKE System, called PVW-OT framework. In Peikert’s dual-mode encryption system, it includes messy mode and decryption mode (called Dec mode). However, common random string (crs) can be reused with bounded limitation. Sender’s computational security in messy mode and receiver’s computational security in Dec mode can be obtained in this scheme. However, it cannot suffice for each party’s statistical security in both modes. Peikert also construct corresponding schemes based on DDH, QR, and LWE’s assumption. Fully simulatable PVW-OT protocol’s security is universally composable (UC), which can compose securely other protocols in complex Internet. UC security is proposed by Canetti [6]. This guarantees security when many protocols are executed in parallel under malicious adversary’s environment. Some lattice-based oblivious transfer protocols are proposed in postquantum era; most of these protocols are based on LWE’s assumption under the semihonest, malicious, or covert adversary model [7–9].In 2020, Quach [10] proposed a UC-secure OT protocol based on LWE’s assumption and rounding function, which can be seen as a modified framework of PVW-OT, called WQ-OT. In WQ-OT protocol, the rounding function is applied on constructing UC-OT. Considering that the rounding function is a smooth projective hash function (SPHF), it can be applied on our scheme with the property of rounding function’s hash key and projective key. In WQ-OT, crs can be reused many times without limitation, and statistical security of the sender and the receiver can be obtained in both messy mode and Dec mode.SPHF has a wide range of applications, such as key exchange and oblivious transfer [11, 12]. In 2012, Halevi and Kalai [13] proposed a two-message OT, which is based on projective hashing function. Cramer and Shoup [14] proposed a universal hash proof in the standard model, which corresponds to adaptive-CCA secure public-key encryption. Kalai [13] proposed a two-message oblivious transfer based on modification of Cramer and Shoup’s SPHF. In 2018, Benhamouda and Blazy [15] proposed a hash proof system or SPHF. It gives an SPHF under standard LWE ciphertext’s languages, which is based on IND-CCA2 MP’s encryption [16]. Before this SPHF proposed by Benhamouda, Katz and Vaikuntanathan [11, 17] proposed a SPHF based on lattice in the standard model, whose language is not valid in standard LWE’s ciphertext. Zhang and Yu [18] proposed a SPHF based on LWE’s assumption under random oracle. Brakerski [19] proposed a two-message OT based on LWE’s assumption which guarantees sender’s statistical privacy under the model of malicious adversary.In 2007, Lindell and Pinkas [20] proposed cut-and-choose technique for secure two-party computation under the malicious adversary model. Circuit constructor P1 constructs s copies’ GC. Circuit evaluator P2 chooses s/2 copies’ GC for check circuit and remaining half s/2 copies’ GC for evaluation circuit. P2 checks correctness of the key’s value in each wire of check garbled circuit. P1 and P2 apply remaining half garbled circuits for computing fx,y.In secure two-party computation, cut-and-choose methodology can be applied to prevent malicious adversary from cheating in this process. As an important technique in secure two-party computation, cut-and-choose is applied to normalize and constrain parties for honestly executing protocols in garbled circuits. In cut-and-choose methodology, constructorP1 constructs s copies’ garbled circuits. Evaluator P2 chooses some garbled circuits for checking. When these check circuits are correctly constructed, the evaluator applies remaining garbled circuits to evaluate corresponding function by evaluation circuits.In this process, the OT protocol is applied for transferring corresponding key’s value through wires of the garbled circuit. The OT protocol can be applied on transferring senderP1’s key to receiver P2 through garbled circuit’s wires. If these two processes are done separately, the overall protocol may lead to selective-failure attacks, which are introduced in [20, 21]. Combining cut-and-choose detection with oblivious transfer, we can transfer keys by wires between the sender (circuit constructor) and the receiver (circuit evaluator).Lindell [22] applied cut-and-choose methodology [20] for constructing fully simulatable OT protocols. Lindell [23] proposed a new primitive in secure two-party computation, called CCOT protocol, which can avoid selective-failure attacks. After CCOT primitive proposed by Lindell, some scholars have proposed some schemes about construction of CCOT, which are mostly modified CCOT protocol, such as batch CCOT and bilateral CCOT [24–28].TraditionalOT21 are applied in transferring key or message by number theory’s assumption, such as DDH and QR assumption. Classical number theory assumptions cannot resist quantum attacks. It is necessary to design postquantum cryptography schemes. Considering lattice’s specific linear structure, lattice-based protocols can be applied to resist quantum attacks.There exist some cryptographic protocols based on lattice’s assumption, which can resist quantum attack with the specific construction of lattice. Reduction from worst case to average case in lattice, trapdoors algorithm and some lattice theory are mentioned in [29–32].In secure two-party computation, the CCOT protocol can resist malicious adversary’s attack. Considering postquantum era, designing the CCOT protocol based on lattice assumption can resist quantum attacks. Combining with lattice theory, designing LWE-based CCOT protocol is of great significance to resist quantum attacks in secure two-party computation. Then, we can expand CCOT to batch-CCOT protocol, which can be applied on secure multiparty computation.


## 1.3. Our Contribution

(i)
We construct a CCOT protocol based on LWE’s assumption and rounding function. Applying WQ-OT [10] encryption scheme based on the rounding function and combining with PVW’s dual framework [5], we design a UC-secure cut-and-choose OT protocol under the malicious adversary model.(ii)
Our CCOT protocol has better security property. For better understanding CCOT’s security, we give a security analysis under the malicious adversary’s corruption in smooth projective hash proof system, which is mainly based on simulation proof methodology.(iii)
In our scheme,crs can be reused many times, and all parties can achieve statistical security. The rounding function, as smooth projective hash function (SPHF), has better security in transferring P1’s garbled key to P2. Due to the special property of the hash key and the projective key, this rounding function can guarantee CCOT protocol’s correctness, privacy, and indistinguishability between the Messy mode and Dec mode.(iv)
Apply the CCOT protocol on secure two-party computation, which is mainly based on garbled circuits.


## 1.4. Organization

(i)
In Section1, we give an overall introduction about background, related work about the CCOT protocol. Finally, we give our contribution and paper’s organization.(ii)
In Section2, we mainly introduce some preliminaries about lattice theory and some knowledge used in scheme’s construction.(iii)
In Section3, we introduce some basic tools applied on our scheme. It includes OT-based dual-mode encryption, which is initiated by Regev’s encryption and rounding function. As an important methodology in secure two-party computation, cut-and-choose technique is also introduced in this part. This dual-mode encryption’s framework security is mostly based on LWE’s assumption, where indistinguishability between the Messy Mode and the Dec Mode is based on DLWE’s assumption.(iv)
In Section4, cut-and-choose oblivious transfer (CCOT) protocol, as an important protocol, is applied on secure two-party computation. We construct a CCOT protocol and embed this CCOT protocol into secure two-party computation. Then, we expand CCOT to BCCOT by batch operation and embed this BCCOT protocol into secure two-party computation.


## 2. Preliminary

### 2.1. Notation

Denoten as the security parameter throughout this paper and also meaning the dimension of LWE’s assumption. We denote a negligible function as in polynomial function negln, which is much smaller than the function close to zero, such as f=n−c, where c is a positive constant close to ∞. Similarly, we denote function 1−negln as an overwhelming function. Denote bold lowercase letter as the vector, e.g. v, and denote bold uppercase letter as matrix, e.g. M. Denote amodb=a−⌊a/b⌋b and ⌊a⌋=⌊a+1/2⌋. Denote k=0,1,…,k−1 as a residual class set, which can be obtained by any integers’ mod integer k. Denote quotient ring ℤq=ℤ/qℤ as a residual class set, where ℤ is modulo prime integer qq≥2. Denote T=ℝ/ℤ as group of reals [0, 1), according to modulo 1 addition. Define Ψα as the distribution on T, which has mean 0 and standard deviation α/2π. Denote vT and MT as an transpose operation of vector v and matrix M. Given probability distribution D, denote variable x⟵D as sampling variable x from certain distribution D. Usually, denote x⟵Uℤ as sampling from uniform distribution in ℤ.


### 2.2. Lattice Theory

Lattice, as a linear algebraic structure, can resist quantum attacks. Some lattice schemes are constructed by reduction from worst case to average case, such as reduction from SVP/CVP to LWE/SIS. Considering the size of keys and ciphertext and the structure of lattice, LWE’s assumption is more used in key exchange (KE), oblivious transfer (OT), and public key encryption (PKE). And, SIS’s assumption is more used in signature schemes. We apply LWE’s assumption to design an OT protocol.Lattice is a discrete additive subgroup. And, lattice is also a linear structure, which is constructed by lattice basis and integral coefficient.Definition 1 (LWE).
Learning with errorsLWE assumption can be regarded as an output by an random algorithm, which outputs a,a,s+e, a,s⟵U and e⟵D, such as Gaussian distribution and, centered binomial distribution. In this assumption, LWE’s pairs are indistinguishable from uniform distribution. Usually, we classify LWE’s assumption as SLWE and DLWE.Definition 2 (search-LWE).
Given some LWE’s pairs, the probability of findings is negligible.Definition 3 (decision-LWE).
Given some LWE’s pairs and uniform pairs, it is indistinguishable from LWE’s pairs to uniform pairs.Definition 4 (Gaussian probability function).
Gaussian distribution means that variablex samples from ℝ based on Gaussian function. Usually, denote function ρsx=exp−πx2/s2 with mean 0 and variance s2.Definition 5 (ideal lattice).
Ideal lattice can be regarded as an algebraic structure based on cyclic basis, which is constructed in quotient ringℤq. It has some advantages, such as shortening the size of keys and ciphertext.Definition 6 (ring-LWE).
Givena,s∈ℝq, certain distribution D, and output a,b=a,s+e∈ℝq×ℝq, let us denote As,χ as the distribution of LWE’s pairs.Definition 7 (search-RLWE).
Given RLWE’s pairsa,b=a,s+e∈ℝq×ℝq, it is difficult in finding s.Definition 8 (decision-RLWE).
Let RLWE’s pairs be sampled from distributionAs,D. DRLWE assumption means that it is indistinguishable from As,D to uniform distribution.
Given lattice basisA, we also define lattice as ΛA=z∈ℤm|∃s∈ℤqn,st.z=Asmodq and Λ⊥A=z∈ℤm|z,A=0modq, and dual lattice Λ∗A=x∈ℝn:∀v∈Λ,x,v∈ℤ.
Letλ1Λ be the shortest nonzero vector in lattice ΛA, which is denoted as λ1Λ=minx∈Λ,x≠0x.Definition 9 (smoothing parameter [29]).
Givenn-dimensional lattice ΛA, positive real ϵ≥0, and Gaussian function ρ1/sx, x∈Λ∗∖0, define smoothing parameter ηϵΛ as the smallest s, which satisfy ρ1/sxΛ∗∖0≤ϵ.Definition 10 (noise flooding [33]).
Given two integersB,B′∈ℤ and e∈−B′,B′, assuming that B′ is negligible compared to B, satisfying B′/B=negln. Then, following two distributions are indistinguishable between U−B,B and U−B,B+e, meaning that U−B,B≈sU−B,B+e, e∈−B′,B′.Lemma 1 (see [31]).
Given anyn-dimensional latticeΛandϵ≤0, obtainηϵΛ≤log2n/1+1/ϵπ/λ1Λ. For anyωlognfunction, there exists negligibleϵn, satisfyingηϵΛ≤ωlognλ1Λ∗orηϵΛ⊥≤ωlogn.Lemma 2 (see [31]).
Givenm≥2nlogq, for anyAfromℤqm×n, define eventE=Ais full rankand obtainPrE≥1−q−n. Givenm≥2nlogq, for anyAfromℤqm×n, obtainPrλ1Λ≥q/4≥1−q−n. So, we can obtainPrE∧λ1Λ≥q/4≥1−2q−n.


## 2.1. Notation

Denoten as the security parameter throughout this paper and also meaning the dimension of LWE’s assumption. We denote a negligible function as in polynomial function negln, which is much smaller than the function close to zero, such as f=n−c, where c is a positive constant close to ∞. Similarly, we denote function 1−negln as an overwhelming function. Denote bold lowercase letter as the vector, e.g. v, and denote bold uppercase letter as matrix, e.g. M. Denote amodb=a−⌊a/b⌋b and ⌊a⌋=⌊a+1/2⌋. Denote k=0,1,…,k−1 as a residual class set, which can be obtained by any integers’ mod integer k. Denote quotient ring ℤq=ℤ/qℤ as a residual class set, where ℤ is modulo prime integer qq≥2. Denote T=ℝ/ℤ as group of reals [0, 1), according to modulo 1 addition. Define Ψα as the distribution on T, which has mean 0 and standard deviation α/2π. Denote vT and MT as an transpose operation of vector v and matrix M. Given probability distribution D, denote variable x⟵D as sampling variable x from certain distribution D. Usually, denote x⟵Uℤ as sampling from uniform distribution in ℤ.


## 2.2. Lattice Theory

Lattice, as a linear algebraic structure, can resist quantum attacks. Some lattice schemes are constructed by reduction from worst case to average case, such as reduction from SVP/CVP to LWE/SIS. Considering the size of keys and ciphertext and the structure of lattice, LWE’s assumption is more used in key exchange (KE), oblivious transfer (OT), and public key encryption (PKE). And, SIS’s assumption is more used in signature schemes. We apply LWE’s assumption to design an OT protocol.Lattice is a discrete additive subgroup. And, lattice is also a linear structure, which is constructed by lattice basis and integral coefficient.Definition 1 (LWE).
Learning with errorsLWE assumption can be regarded as an output by an random algorithm, which outputs a,a,s+e, a,s⟵U and e⟵D, such as Gaussian distribution and, centered binomial distribution. In this assumption, LWE’s pairs are indistinguishable from uniform distribution. Usually, we classify LWE’s assumption as SLWE and DLWE.Definition 2 (search-LWE).
Given some LWE’s pairs, the probability of findings is negligible.Definition 3 (decision-LWE).
Given some LWE’s pairs and uniform pairs, it is indistinguishable from LWE’s pairs to uniform pairs.Definition 4 (Gaussian probability function).
Gaussian distribution means that variablex samples from ℝ based on Gaussian function. Usually, denote function ρsx=exp−πx2/s2 with mean 0 and variance s2.Definition 5 (ideal lattice).
Ideal lattice can be regarded as an algebraic structure based on cyclic basis, which is constructed in quotient ringℤq. It has some advantages, such as shortening the size of keys and ciphertext.Definition 6 (ring-LWE).
Givena,s∈ℝq, certain distribution D, and output a,b=a,s+e∈ℝq×ℝq, let us denote As,χ as the distribution of LWE’s pairs.Definition 7 (search-RLWE).
Given RLWE’s pairsa,b=a,s+e∈ℝq×ℝq, it is difficult in finding s.Definition 8 (decision-RLWE).
Let RLWE’s pairs be sampled from distributionAs,D. DRLWE assumption means that it is indistinguishable from As,D to uniform distribution.
Given lattice basisA, we also define lattice as ΛA=z∈ℤm|∃s∈ℤqn,st.z=Asmodq and Λ⊥A=z∈ℤm|z,A=0modq, and dual lattice Λ∗A=x∈ℝn:∀v∈Λ,x,v∈ℤ.
Letλ1Λ be the shortest nonzero vector in lattice ΛA, which is denoted as λ1Λ=minx∈Λ,x≠0x.Definition 9 (smoothing parameter [29]).
Givenn-dimensional lattice ΛA, positive real ϵ≥0, and Gaussian function ρ1/sx, x∈Λ∗∖0, define smoothing parameter ηϵΛ as the smallest s, which satisfy ρ1/sxΛ∗∖0≤ϵ.Definition 10 (noise flooding [33]).
Given two integersB,B′∈ℤ and e∈−B′,B′, assuming that B′ is negligible compared to B, satisfying B′/B=negln. Then, following two distributions are indistinguishable between U−B,B and U−B,B+e, meaning that U−B,B≈sU−B,B+e, e∈−B′,B′.Lemma 1 (see [31]).
Given anyn-dimensional latticeΛandϵ≤0, obtainηϵΛ≤log2n/1+1/ϵπ/λ1Λ. For anyωlognfunction, there exists negligibleϵn, satisfyingηϵΛ≤ωlognλ1Λ∗orηϵΛ⊥≤ωlogn.Lemma 2 (see [31]).
Givenm≥2nlogq, for anyAfromℤqm×n, define eventE=Ais full rankand obtainPrE≥1−q−n. Givenm≥2nlogq, for anyAfromℤqm×n, obtainPrλ1Λ≥q/4≥1−q−n. So, we can obtainPrE∧λ1Λ≥q/4≥1−2q−n.


## 3. Basic Tools

### 3.1. Dual-Mode PVW-PKE and Related PVW-OT Protocol

#### 3.1.1. Dual-Mode PVW-PKE Encryption System

We introduce a dual-mode encryption cryptosystem proposed by Peikert et al., called PVW framework [5]. This cryptosystem is usually applied on constructing the OT protocol. It includes messy-encryption mode (or Messy mode) and decryption-encryption mode (or Dec mode).We introduce relevant probability probabilistic algorithms, which includeSetup,KeyGen,Enc,Dec,FindMessy,TrapKeyGen algorithms. In these algorithms, message space is 0,1n and string crs is generically common in all algorithms, and we often omit them. Next, we introduce these Algorithms in Figure 5.Figure 5
Dual-mode PVW-PKE algorithms.Firstly, this cryptosystem can be initialized by a trusted setup phase,Setup algorithm, which outputs a string crs and a trapdoor t. When crs is uniformly distributed (Setup=SetupMessy), invoke Messy branch for our encryption (Setup=SetupDec). When crs is distributed by certain distribution, invoke decryption branch for our encryption. Considering the generation of crs, the property of dual-mode cryptosystem is that the distribution of crs in SeupMessy and SeupDec branch is indistinguishable.Secondly, we invoke corresponding public key encryption (PKE) scheme, which includesKeyGen, Enc, and Dec algorithm. In key generation phase, input a branch parameter σ and output pk,sk. The encrypter encrypts a message under chosen branch b (b,σ∈0,1).Whenb≠σ, we denote this mode as the messy mode. In this mode, the sender encrypts the message under branch b, and the receiver decrypts ciphertext under branch σ. Apparently, the decrypter cannot obtain the corresponding message. Usually, we can use a FindMessy algorithm to find messy branch.Whenb=σ, we denote this mode as Dec Mode. In this mode, the sender encrypts the message under branch b, and the receiver can correctly decrypt ciphertext under corresponding branch σb=σ. In Dec Mode, we apply a trapdoor generation algorithm TrapKeyGen in security proof. In security proof, we should notice that it is indistinguishable between the key pair from TrapKeyGen and the key pair from KeyGen.ThepropertiesofPVWframework are as follows:(1)
Completeness: for any branch b=σ∈0,1, the receiver can correctly decrypt ciphertext, meaning Decsk,Encpk,σ,m=m.(2)
Indistinguishability between two modes: it is indistinguishable between the Messy mode and the Dec mode, which is mainly indistinguishable between crsM and crsD.(3)
The property of messy mode: given crsM,tM from SetupMessy and any public key pk (including malformed pk) from the key generation phase under corresponding mode, invoke FindMessytM,pk algorithm to obtain messy branch b′. In Messy mode, it can obtain statistical security, which can hide some information about ciphertext, meaning Encpk,b′,m0≈sEncpk,b′,m1.(4)
The property of decryption mode: it is indistinguishable between key pairs generated by KeyGenσ and key pairs generated by TrapKeyGen, meaning pk,skσ≈sKeyGenσ.


#### 3.1.2. PVW-OT Framework

Peikert proposeddmmode protocol in Figure 6, which applies any mode in the dual-mode encryption system under the ℱCRS-hybrid UC model [6]. The dmmode protocol achieves the function of ideal FOT in Figure 1.Figure 6
dmmode for oblivious transfer.To achieve the messy and decryption mode, defineℱCRSmode to produce common string, which corresponds to relevant setup algorithm.Lemma 3 (see [5]).
In static corruption model, the protocoldmmodesecurely emulates ideal functionFOTin the universal composableℱCRSmode-hybrid model.


### 3.2. Dual-Mode WQ-PKE and Related WQ-OT Protocol

UC-OT based on PVW’s framework [5] can provide sender’s statistical security and receiver’s computational security in the messy mode. In Dec mode, sender’s security is computational and receiver’s security is statistical. This construction can only provide receiver’s computational security in Messy mode and sender’s computational security in Dec Mode. In addition, it has bounded limitation about reusability of crs.Considering about these limitations, apply superpolynomial LWE modulus and single ‘short’crs and then achieve statistical security in both mode and unbounded crs’s reusability.Apply the WQ-OT scheme [10] for our CCOT’s construction. WQ-OT is a two-round UC-OT based on Common References String (crs), and it is based on LWE assumption with subexponential modulus-to-noise ratio.Considering noise flooding technique is applied to strengthen reusability and statistical security, we need superpolynomial modulusq of LWE. However, this operation has negative impact on the security proof. And, the simulator of PVW-OT operates in linear q time, not superpolynomial, due to negative impact on security proof. For resolving this difficulty, apply randomized rounding function to PKE-based OT framework. Benhamouda [15] et al. proposed a rounding function.Considering about security proof, we apply the hash proof system, which mainly refers to lattice-based SPHFs. In the following, we will introduce a rounding function, which is viewed as an approximate hash proof system. Givenc=As+e∈ℤqm, A∈ℤqm×n, s∈ℤqn, e∈ℤqm, and ‘c’ as a vector is close to ΛA, the prover knows s and e and the prover needs to prove ‘c’ is the corresponding ciphertext for the verifier. The verifier samples a uniformly random vector r⟵Dℤ,sm. Let r be a hash key, and compute p=ATr as a projection key. The verifier sends projection key p to the prover, and the prover computes projection hash value pH=Rp,s=RpTs=RrTAs. The verifier computes hash value H=Rr,c=RrTc. Then, the verifier sends H to the prover. The prover checks whether H=pH to ensure the verifier is honest; then, the verifier approves the prover’s proof. This progress is zero knowledge. The prover has not revealed secret information s and e.The high probability ofH=pH implies the property of approximate correctness, which needs vector ‘c’ close to lattice ΛA, with distance less than B. For applying the approximate hash proof system better, the property of smoothness needs point ‘c’ far from ΛA, with minimum distance qm/s.


#### 3.2.1. Rounding Function

We describe a suitableq-periodic signal function, rounding function R, as follows. Given m=Θnlogq, define the rounding function R:ℤq⟶0,1 as follows:(1)Rx=2xqmod21,Pr=12+cos2πx/q2,0,Pr=12−cos2πx/q2.(i)
Smoothness: given full rank matrix A∈ℤqn×m, s≥ηεΛAε=negln, for all c∈ℤqm satisfying c,ΛA≥qm/s, achieve PrRrTc=1|rTA=pT≤1/2+neglnr∈Dℤ,smApproximatecorrectness: given s∈ℤqn,e∈ℤqm,B=Oq/ms, for all c=As+e, satisfying distc,ΛA≤B, achieve PrRrTAs=RrTc≥2/3r∈Dℤ,sm


#### 3.2.2. Smooth Projective Hash Function Encryption System

Apply this rounding function on our encryption system, which is likely Regev’s Encryption. Define this modified encryption system as the smooth encryption system. For better understanding the process of the smooth encryption system, we introduce the encryption process of single-bit messageu∈0,1 in Figure 7.(i)
Parameters: denote n as the security parameter in the whole scheme. Let prime integers q≥2 be modulus. Let m≥2n+1logq and s≥4m. Distribution χ is a B-bounded distribution (B≥Ωn). Usually, set B=Ωn; the value of B is a security limitation value, which guarantees LWE’s assumption for schemes. B′ is a negligible value compared to B, satisfying q≤wB′+nm.(ii)
Correctness: given B+B′·s·m=Oq and s≥ωlogm, decryption algorithm Decsk,ct can correctly decrypt with nonnegligible probability.Security: given m≥2n+1logq and s≥4m, the smooth encryption scheme based on LWE’s assumption can achieve corresponding security.Figure 7
SPHF encryption algorithms based on the rounding function.


#### 3.2.3. WQ-OT Framework

We give a brief introduction about dual-mode encryption based on the SPHF encryption system in Figure8, which is based on the hash key and projection key of SPHF-rounding function.(1)
Completeness: given s≥ωlogm and B+B′·s·m=Oq, then the scheme can correctly decrypt in the Dec mode.(2)
Indistinguishability between Messy mode and Dec mode: given string crs to any adversary, adversary cannot distinguish between the Messy mode with the Dec mode, implying SetupMessy∗1n≈cSetupDec∗1n. This indistinguishability implies the indistinguishability between LWE’s vector pairs with uniform vector pairs.(3)
Sufficient conditions for Messy key: given public key pk in the smooth encryption system, it satisfies SmoothEnc∗pk,0≈sSmoothEnc∗pk,1. Given full rank uniform matrix A⟵ℤqm×n and c∈ℤqm, when s≥ηϵΛA and dc,ΛA≥qm/s, then public key pk=A,c achieves the property of Messy key.(4)
RequirementsforMessykey: given parameter m≥2n+1logq, s≥4m, and sample A,c from ℤqm×n×ℤqm, satisfying dc,ΛA≥q/4, we obtain messy public key A,c with nonnegligible probability.(5)
VerificationofMessykey: given s≥6m and A,T generated by TrapGen∗1n,1m,q, which A is a full rank matrix, invoke IsMessy∗T,A,c algorithm, which inputs vector c to decide distance between c and lattice ΛA. When dc,ΛA≥qm/s, output Messy public key A,c with overwhelming probability.(6)
Messymode′s property: given s≥6m and m≥2n+1logq, then the scheme achieves security in the Messy mode, implying SmoothEnc∗crsM∗,pkM,0≈sSmoothEnc∗crsM∗,pkM,1.(7)
Dec: given B′, satisfying B/B′=negln, then the scheme achieve security in the Dec mode, implying the indistinguishability between pk0∗,skb∗ generated from KeyGen∗crsD∗,b and pk0,skb generated from TrapKeyGen∗tdD∗ in security proof.Figure 8
Dual-mode WQ-PKE algorithms.Lemma 4 (see [10]).
GivenLWEq,λ,n assumption with the corresponding parameter in WQ-OT’s construction, an dual-mode UC-secure oblivious transfer protocol under static corruption exists.


## 3.1. Dual-Mode PVW-PKE and Related PVW-OT Protocol

### 3.1.1. Dual-Mode PVW-PKE Encryption System

We introduce a dual-mode encryption cryptosystem proposed by Peikert et al., called PVW framework [5]. This cryptosystem is usually applied on constructing the OT protocol. It includes messy-encryption mode (or Messy mode) and decryption-encryption mode (or Dec mode).We introduce relevant probability probabilistic algorithms, which includeSetup,KeyGen,Enc,Dec,FindMessy,TrapKeyGen algorithms. In these algorithms, message space is 0,1n and string crs is generically common in all algorithms, and we often omit them. Next, we introduce these Algorithms in Figure 5.Figure 5
Dual-mode PVW-PKE algorithms.Firstly, this cryptosystem can be initialized by a trusted setup phase,Setup algorithm, which outputs a string crs and a trapdoor t. When crs is uniformly distributed (Setup=SetupMessy), invoke Messy branch for our encryption (Setup=SetupDec). When crs is distributed by certain distribution, invoke decryption branch for our encryption. Considering the generation of crs, the property of dual-mode cryptosystem is that the distribution of crs in SeupMessy and SeupDec branch is indistinguishable.Secondly, we invoke corresponding public key encryption (PKE) scheme, which includesKeyGen, Enc, and Dec algorithm. In key generation phase, input a branch parameter σ and output pk,sk. The encrypter encrypts a message under chosen branch b (b,σ∈0,1).Whenb≠σ, we denote this mode as the messy mode. In this mode, the sender encrypts the message under branch b, and the receiver decrypts ciphertext under branch σ. Apparently, the decrypter cannot obtain the corresponding message. Usually, we can use a FindMessy algorithm to find messy branch.Whenb=σ, we denote this mode as Dec Mode. In this mode, the sender encrypts the message under branch b, and the receiver can correctly decrypt ciphertext under corresponding branch σb=σ. In Dec Mode, we apply a trapdoor generation algorithm TrapKeyGen in security proof. In security proof, we should notice that it is indistinguishable between the key pair from TrapKeyGen and the key pair from KeyGen.ThepropertiesofPVWframework are as follows:(1)
Completeness: for any branch b=σ∈0,1, the receiver can correctly decrypt ciphertext, meaning Decsk,Encpk,σ,m=m.(2)
Indistinguishability between two modes: it is indistinguishable between the Messy mode and the Dec mode, which is mainly indistinguishable between crsM and crsD.(3)
The property of messy mode: given crsM,tM from SetupMessy and any public key pk (including malformed pk) from the key generation phase under corresponding mode, invoke FindMessytM,pk algorithm to obtain messy branch b′. In Messy mode, it can obtain statistical security, which can hide some information about ciphertext, meaning Encpk,b′,m0≈sEncpk,b′,m1.(4)
The property of decryption mode: it is indistinguishable between key pairs generated by KeyGenσ and key pairs generated by TrapKeyGen, meaning pk,skσ≈sKeyGenσ.


### 3.1.2. PVW-OT Framework

Peikert proposeddmmode protocol in Figure 6, which applies any mode in the dual-mode encryption system under the ℱCRS-hybrid UC model [6]. The dmmode protocol achieves the function of ideal FOT in Figure 1.Figure 6
dmmode for oblivious transfer.To achieve the messy and decryption mode, defineℱCRSmode to produce common string, which corresponds to relevant setup algorithm.Lemma 3 (see [5]).
In static corruption model, the protocoldmmodesecurely emulates ideal functionFOTin the universal composableℱCRSmode-hybrid model.


## 3.1.1. Dual-Mode PVW-PKE Encryption System

We introduce a dual-mode encryption cryptosystem proposed by Peikert et al., called PVW framework [5]. This cryptosystem is usually applied on constructing the OT protocol. It includes messy-encryption mode (or Messy mode) and decryption-encryption mode (or Dec mode).We introduce relevant probability probabilistic algorithms, which includeSetup,KeyGen,Enc,Dec,FindMessy,TrapKeyGen algorithms. In these algorithms, message space is 0,1n and string crs is generically common in all algorithms, and we often omit them. Next, we introduce these Algorithms in Figure 5.Figure 5
Dual-mode PVW-PKE algorithms.Firstly, this cryptosystem can be initialized by a trusted setup phase,Setup algorithm, which outputs a string crs and a trapdoor t. When crs is uniformly distributed (Setup=SetupMessy), invoke Messy branch for our encryption (Setup=SetupDec). When crs is distributed by certain distribution, invoke decryption branch for our encryption. Considering the generation of crs, the property of dual-mode cryptosystem is that the distribution of crs in SeupMessy and SeupDec branch is indistinguishable.Secondly, we invoke corresponding public key encryption (PKE) scheme, which includesKeyGen, Enc, and Dec algorithm. In key generation phase, input a branch parameter σ and output pk,sk. The encrypter encrypts a message under chosen branch b (b,σ∈0,1).Whenb≠σ, we denote this mode as the messy mode. In this mode, the sender encrypts the message under branch b, and the receiver decrypts ciphertext under branch σ. Apparently, the decrypter cannot obtain the corresponding message. Usually, we can use a FindMessy algorithm to find messy branch.Whenb=σ, we denote this mode as Dec Mode. In this mode, the sender encrypts the message under branch b, and the receiver can correctly decrypt ciphertext under corresponding branch σb=σ. In Dec Mode, we apply a trapdoor generation algorithm TrapKeyGen in security proof. In security proof, we should notice that it is indistinguishable between the key pair from TrapKeyGen and the key pair from KeyGen.ThepropertiesofPVWframework are as follows:(1)
Completeness: for any branch b=σ∈0,1, the receiver can correctly decrypt ciphertext, meaning Decsk,Encpk,σ,m=m.(2)
Indistinguishability between two modes: it is indistinguishable between the Messy mode and the Dec mode, which is mainly indistinguishable between crsM and crsD.(3)
The property of messy mode: given crsM,tM from SetupMessy and any public key pk (including malformed pk) from the key generation phase under corresponding mode, invoke FindMessytM,pk algorithm to obtain messy branch b′. In Messy mode, it can obtain statistical security, which can hide some information about ciphertext, meaning Encpk,b′,m0≈sEncpk,b′,m1.(4)
The property of decryption mode: it is indistinguishable between key pairs generated by KeyGenσ and key pairs generated by TrapKeyGen, meaning pk,skσ≈sKeyGenσ.


## 3.1.2. PVW-OT Framework

Peikert proposeddmmode protocol in Figure 6, which applies any mode in the dual-mode encryption system under the ℱCRS-hybrid UC model [6]. The dmmode protocol achieves the function of ideal FOT in Figure 1.Figure 6
dmmode for oblivious transfer.To achieve the messy and decryption mode, defineℱCRSmode to produce common string, which corresponds to relevant setup algorithm.Lemma 3 (see [5]).
In static corruption model, the protocoldmmodesecurely emulates ideal functionFOTin the universal composableℱCRSmode-hybrid model.


## 3.2. Dual-Mode WQ-PKE and Related WQ-OT Protocol

UC-OT based on PVW’s framework [5] can provide sender’s statistical security and receiver’s computational security in the messy mode. In Dec mode, sender’s security is computational and receiver’s security is statistical. This construction can only provide receiver’s computational security in Messy mode and sender’s computational security in Dec Mode. In addition, it has bounded limitation about reusability of crs.Considering about these limitations, apply superpolynomial LWE modulus and single ‘short’crs and then achieve statistical security in both mode and unbounded crs’s reusability.Apply the WQ-OT scheme [10] for our CCOT’s construction. WQ-OT is a two-round UC-OT based on Common References String (crs), and it is based on LWE assumption with subexponential modulus-to-noise ratio.Considering noise flooding technique is applied to strengthen reusability and statistical security, we need superpolynomial modulusq of LWE. However, this operation has negative impact on the security proof. And, the simulator of PVW-OT operates in linear q time, not superpolynomial, due to negative impact on security proof. For resolving this difficulty, apply randomized rounding function to PKE-based OT framework. Benhamouda [15] et al. proposed a rounding function.Considering about security proof, we apply the hash proof system, which mainly refers to lattice-based SPHFs. In the following, we will introduce a rounding function, which is viewed as an approximate hash proof system. Givenc=As+e∈ℤqm, A∈ℤqm×n, s∈ℤqn, e∈ℤqm, and ‘c’ as a vector is close to ΛA, the prover knows s and e and the prover needs to prove ‘c’ is the corresponding ciphertext for the verifier. The verifier samples a uniformly random vector r⟵Dℤ,sm. Let r be a hash key, and compute p=ATr as a projection key. The verifier sends projection key p to the prover, and the prover computes projection hash value pH=Rp,s=RpTs=RrTAs. The verifier computes hash value H=Rr,c=RrTc. Then, the verifier sends H to the prover. The prover checks whether H=pH to ensure the verifier is honest; then, the verifier approves the prover’s proof. This progress is zero knowledge. The prover has not revealed secret information s and e.The high probability ofH=pH implies the property of approximate correctness, which needs vector ‘c’ close to lattice ΛA, with distance less than B. For applying the approximate hash proof system better, the property of smoothness needs point ‘c’ far from ΛA, with minimum distance qm/s.


### 3.2.1. Rounding Function

We describe a suitableq-periodic signal function, rounding function R, as follows. Given m=Θnlogq, define the rounding function R:ℤq⟶0,1 as follows:(1)Rx=2xqmod21,Pr=12+cos2πx/q2,0,Pr=12−cos2πx/q2.(i)
Smoothness: given full rank matrix A∈ℤqn×m, s≥ηεΛAε=negln, for all c∈ℤqm satisfying c,ΛA≥qm/s, achieve PrRrTc=1|rTA=pT≤1/2+neglnr∈Dℤ,smApproximatecorrectness: given s∈ℤqn,e∈ℤqm,B=Oq/ms, for all c=As+e, satisfying distc,ΛA≤B, achieve PrRrTAs=RrTc≥2/3r∈Dℤ,sm


### 3.2.2. Smooth Projective Hash Function Encryption System

Apply this rounding function on our encryption system, which is likely Regev’s Encryption. Define this modified encryption system as the smooth encryption system. For better understanding the process of the smooth encryption system, we introduce the encryption process of single-bit messageu∈0,1 in Figure 7.(i)
Parameters: denote n as the security parameter in the whole scheme. Let prime integers q≥2 be modulus. Let m≥2n+1logq and s≥4m. Distribution χ is a B-bounded distribution (B≥Ωn). Usually, set B=Ωn; the value of B is a security limitation value, which guarantees LWE’s assumption for schemes. B′ is a negligible value compared to B, satisfying q≤wB′+nm.(ii)
Correctness: given B+B′·s·m=Oq and s≥ωlogm, decryption algorithm Decsk,ct can correctly decrypt with nonnegligible probability.Security: given m≥2n+1logq and s≥4m, the smooth encryption scheme based on LWE’s assumption can achieve corresponding security.Figure 7
SPHF encryption algorithms based on the rounding function.


### 3.2.3. WQ-OT Framework

We give a brief introduction about dual-mode encryption based on the SPHF encryption system in Figure8, which is based on the hash key and projection key of SPHF-rounding function.(1)
Completeness: given s≥ωlogm and B+B′·s·m=Oq, then the scheme can correctly decrypt in the Dec mode.(2)
Indistinguishability between Messy mode and Dec mode: given string crs to any adversary, adversary cannot distinguish between the Messy mode with the Dec mode, implying SetupMessy∗1n≈cSetupDec∗1n. This indistinguishability implies the indistinguishability between LWE’s vector pairs with uniform vector pairs.(3)
Sufficient conditions for Messy key: given public key pk in the smooth encryption system, it satisfies SmoothEnc∗pk,0≈sSmoothEnc∗pk,1. Given full rank uniform matrix A⟵ℤqm×n and c∈ℤqm, when s≥ηϵΛA and dc,ΛA≥qm/s, then public key pk=A,c achieves the property of Messy key.(4)
RequirementsforMessykey: given parameter m≥2n+1logq, s≥4m, and sample A,c from ℤqm×n×ℤqm, satisfying dc,ΛA≥q/4, we obtain messy public key A,c with nonnegligible probability.(5)
VerificationofMessykey: given s≥6m and A,T generated by TrapGen∗1n,1m,q, which A is a full rank matrix, invoke IsMessy∗T,A,c algorithm, which inputs vector c to decide distance between c and lattice ΛA. When dc,ΛA≥qm/s, output Messy public key A,c with overwhelming probability.(6)
Messymode′s property: given s≥6m and m≥2n+1logq, then the scheme achieves security in the Messy mode, implying SmoothEnc∗crsM∗,pkM,0≈sSmoothEnc∗crsM∗,pkM,1.(7)
Dec: given B′, satisfying B/B′=negln, then the scheme achieve security in the Dec mode, implying the indistinguishability between pk0∗,skb∗ generated from KeyGen∗crsD∗,b and pk0,skb generated from TrapKeyGen∗tdD∗ in security proof.Figure 8
Dual-mode WQ-PKE algorithms.Lemma 4 (see [10]).
GivenLWEq,λ,n assumption with the corresponding parameter in WQ-OT’s construction, an dual-mode UC-secure oblivious transfer protocol under static corruption exists.


## 3.2.1. Rounding Function

We describe a suitableq-periodic signal function, rounding function R, as follows. Given m=Θnlogq, define the rounding function R:ℤq⟶0,1 as follows:(1)Rx=2xqmod21,Pr=12+cos2πx/q2,0,Pr=12−cos2πx/q2.(i)
Smoothness: given full rank matrix A∈ℤqn×m, s≥ηεΛAε=negln, for all c∈ℤqm satisfying c,ΛA≥qm/s, achieve PrRrTc=1|rTA=pT≤1/2+neglnr∈Dℤ,smApproximatecorrectness: given s∈ℤqn,e∈ℤqm,B=Oq/ms, for all c=As+e, satisfying distc,ΛA≤B, achieve PrRrTAs=RrTc≥2/3r∈Dℤ,sm


## 3.2.2. Smooth Projective Hash Function Encryption System

Apply this rounding function on our encryption system, which is likely Regev’s Encryption. Define this modified encryption system as the smooth encryption system. For better understanding the process of the smooth encryption system, we introduce the encryption process of single-bit messageu∈0,1 in Figure 7.(i)
Parameters: denote n as the security parameter in the whole scheme. Let prime integers q≥2 be modulus. Let m≥2n+1logq and s≥4m. Distribution χ is a B-bounded distribution (B≥Ωn). Usually, set B=Ωn; the value of B is a security limitation value, which guarantees LWE’s assumption for schemes. B′ is a negligible value compared to B, satisfying q≤wB′+nm.(ii)
Correctness: given B+B′·s·m=Oq and s≥ωlogm, decryption algorithm Decsk,ct can correctly decrypt with nonnegligible probability.Security: given m≥2n+1logq and s≥4m, the smooth encryption scheme based on LWE’s assumption can achieve corresponding security.Figure 7
SPHF encryption algorithms based on the rounding function.


## 3.2.3. WQ-OT Framework

We give a brief introduction about dual-mode encryption based on the SPHF encryption system in Figure8, which is based on the hash key and projection key of SPHF-rounding function.(1)
Completeness: given s≥ωlogm and B+B′·s·m=Oq, then the scheme can correctly decrypt in the Dec mode.(2)
Indistinguishability between Messy mode and Dec mode: given string crs to any adversary, adversary cannot distinguish between the Messy mode with the Dec mode, implying SetupMessy∗1n≈cSetupDec∗1n. This indistinguishability implies the indistinguishability between LWE’s vector pairs with uniform vector pairs.(3)
Sufficient conditions for Messy key: given public key pk in the smooth encryption system, it satisfies SmoothEnc∗pk,0≈sSmoothEnc∗pk,1. Given full rank uniform matrix A⟵ℤqm×n and c∈ℤqm, when s≥ηϵΛA and dc,ΛA≥qm/s, then public key pk=A,c achieves the property of Messy key.(4)
RequirementsforMessykey: given parameter m≥2n+1logq, s≥4m, and sample A,c from ℤqm×n×ℤqm, satisfying dc,ΛA≥q/4, we obtain messy public key A,c with nonnegligible probability.(5)
VerificationofMessykey: given s≥6m and A,T generated by TrapGen∗1n,1m,q, which A is a full rank matrix, invoke IsMessy∗T,A,c algorithm, which inputs vector c to decide distance between c and lattice ΛA. When dc,ΛA≥qm/s, output Messy public key A,c with overwhelming probability.(6)
Messymode′s property: given s≥6m and m≥2n+1logq, then the scheme achieves security in the Messy mode, implying SmoothEnc∗crsM∗,pkM,0≈sSmoothEnc∗crsM∗,pkM,1.(7)
Dec: given B′, satisfying B/B′=negln, then the scheme achieve security in the Dec mode, implying the indistinguishability between pk0∗,skb∗ generated from KeyGen∗crsD∗,b and pk0,skb generated from TrapKeyGen∗tdD∗ in security proof.Figure 8
Dual-mode WQ-PKE algorithms.Lemma 4 (see [10]).
GivenLWEq,λ,n assumption with the corresponding parameter in WQ-OT’s construction, an dual-mode UC-secure oblivious transfer protocol under static corruption exists.


## 4. Cut-and-Choose Oblivious Transfer

Cut-and-choose oblivious transfer (CCOT) protocol can be applied on secure two-party computation, which transfers circuit constructor’s garbled keys of wires to the circuit evaluator. Firstly, we introduce the ideal function of CCOT in secure two-party computation.


### 4.1. Ideal Function of CCOT

Lindell presented the concept ofCCOT, which is an oblivious transfer protocol combined with cut-and-choose index bit. We give a brief introduction about its ideal function FCCOT. Circuit constructor P1 constructs one garbled circuit; circuit evaluator P2 decides to obtain two key’s value of each wire or one key’s value of two wires, which is based on the index bit j∈0,1. When j=0, P2 wants to obtain both key’s value; when j=1, P2 wants to obtain one key’s value from two keys. We give a brief introduction about the ideal function in Figure 9.Figure 9
The ideal functionFCCOT.


### 4.2. Construction of CCOT Protocol

Cut−and−choose oblivioustransfer (CCOT) is a new primitive for secure two-party computation. For better understanding the role of CCOT protocol in secure two-party computation, we give a general introduction about CCOT protocol’s construction.Firstly, we give the construction of theCCOT protocol corresponding to a single garbled circuit in Figure 10.Figure 10
CCOT protocol in secure two-party computation.Given setup algorithm SetupMesssy and SetupDec algorithm,σ is selected bit from the receiver’s input.(1)
The receiverR is initialized with index bit j. When j=0, R invokes KeyGen∗crs,b algorithm to obtain pk0,skb, which is pk0=As+e+f−b·v, skb=s, pk1=pk0+v, and pkb=As+e+f.Whenj=1, R invokes KeyGen∗ algorithm to obtain pk0,skσ, which is pk0=As+e+f−σ·v, pk1=pk0+v, skσ=s, and pkσ=As+e+f.(2)
R sends relevant public key to sender S in corresponding index bit. When j=0, R sends A,pk0,pk1 to S. S encrypts message y0 and y1 under pk0 and pk1. S samples rb⟵Dℤ,rm and computes pbt=rbt·A; then, we obtain βi⟵Rrbt·pki⊕yi,i∈0,1. Finally, S sends cti=pb,βi to R.Whenj=1, R sends A,pk0,pk1 to S. S encrypts message y0 and y1 under pk0 and pk1. S samples rb⟵Dℤ,rm and computes pbt=rbt·A; then, we obtain βi⟵Rrbt·pki⊕yi,i∈0,1. Finally, S sends cti=pb,βi to R.(3)
Whenj=0, receiver R receives cti from sender S. R parses cti as pb,βi. R invokes Dec∗skb,cti to obtain yi by computing yi⟵Rpbt·skb⊕βi. Finally, R obtains y0 and y1.Whenj=1, R receives cti from S. R parses cti as pb,βi. R invokes Dec∗skσ,cti to obtain yσ by computing yi⟵Rpbt·skσ⊕βi.Lemma 5 (correctness [10]).
Givens≥ωlogmandB+B′·s·m=Oq, then the scheme can correctly decrypt in Dec branch.In the Dec mode, given the corresponding parameter, due to rounding function’s property, the receiver can correctly decrypt corresponding two ciphertext. In the Messy mode, whenσ=0, pk0=As+e+f, and secret key skσ=sk0=s can be used to decrypt ciphertext ct0. In the meantime, pk0=As+e+f+v and secret key skσ=sk0=s cannot be used to decrypt corresponding ciphertext ct1. When σ=1, pk1=As+e+f, and secret key skσ=sk1=s can be used to decrypt ciphertext ct1. However, pk0=As+e+f−v, and secret key skσ=sk0=s cannot be used to decrypt corresponding ciphertext ct0.The correctness of this protocol is shown in Table1, which is similar to the SmoothEnc System.Table 1
Protocol’s correctness.
(j,σ)InputOutput(0,σ)crs0,td0,crs0=A0,v0,v0=A0s0+e0,td0=s0y0⟵Rp0t·sk0⊕β0, y1⟵Rp1t·sk1⊕β1(1, 0)crs1,td1,crs1=A1,v1,v1=A1s1+e1,td1=s1y0⟵Rp0t·sk0⊕β0(1, 1)crs1,td1,crs1=A1,v1,v1=A1s1+e1,td1=s1y1⟵Rp1t·sk1⊕β1


#### 4.2.1. Security Proof

Theorem 1.
Givens≥6mandm≥2n+1logq, the above scheme is UC-secure CCOT protocol under static malicious adversary, assuming the hardness of learning with errors with the corresponding parameter.We mainly consider two corruption cases; the sender is corrupted; the receiver is corrupted.Sender is corrupted: firstly, we consider adversary A corrupt sender P1, and we need to construct a simulator S, who can invoke adversary A′s input copies and make some operations as follows.whenj=0, run Dec mode’s setup algorithm SetupDec∗ and obtain crs0,t0⟵SetupDec∗1n, which is well known to all parties. Honest receiver P2 runs KeyGen∗ algorithm to obtain pk0,pk1,skb and then P2 sends pk0 and pk1 to sender P1. Corresponding this situation, simulator S invokes TrapKeyGen∗crs0,t0 algorithm to obtain pk,sk0,sk1 and then S sends sid,pk to adversary A, which simulates a interactive scenario between receiver P2 and adversary A. Then, simulator S stores sk0,sk1. Adversary A invokes Enc∗pk,y0,y1 algorithm to obtain ciphertext ct0,ct1 and A sends ct0,ct1 to receiver P2. Simulator S simulates this process; Simulator S receives ct0,ct1 from adversary A; S checks corresponding secret key sk0 and sk1 and invokes Dec∗skb,ctb,b∈0,1 algorithm to obtain yb′, b∈0,1. Simulator S sends y0′,y1′ to ideal function Fccot. Receiver P2 obtains the corresponding message based on mode index j and selection bit index σ.Receiveriscorrupted: adversary A corrupts receiver P2, and we need to construct a simulator S, who simulates the process between adversary A and sender P1.Whenj=1, run Messy mode’s setup algorithm SetupMessy∗ to obtain crs1,t1⟵SetupMessy∗1n, where crs1 is well known to all parties. We should notice that the distribution of crs1 is uniformly sampled. Honest sender P1 interacts with P2 corrupted by adversary A. Adversary A chooses a selection bit σ and then invokes KeyGen∗crs1,σ algorithm to obtain sid,pkσ,skσ, which is public to sender P1. Simulator S invokes FindMessy∗crs1,t1,pkσ to obtain messy branch b. Then, simulator S sends sid,receiver,1−b to ideal function of FOT. Then, simulator S receives corresponding message y1−b. Simulator S simulates the process between P1 and A.Firstly,S computes ctb⟵Enc∗pkb,0n and ct1−b⟵Enc∗pk1−b,y1−b. Secondly, S sends ctb,ct1−b to adversary A, as if from sender P1’s value. Finally, adversary A decrypts ctb with corresponding secret key skσ. Considering LWE’s assumption and Messy mode’s property, adversary A cannot obtain the correct message.


### 4.3. Ideal Function of BCCOT

In secure two-party computation, Garbled circuits’ constructorP1 constructed many copies circuits, which can resist one situation about P1 constructing incorrect circuit. Let s be garbled circuits’ parameter. P1 constructs s copies circuits, half of these circuits are used for checking and another half are used for evaluation. After all check circuits pass detection, remaining half circuits are used for evaluating fx,y. Some garbled circuit maybe incorrectly constructed by P1, and we can adopt majority value of fx,y. Considering circuits’ parameter s, we introduce a ‘batch cut-and-choose’ oblivious transfer’s ideal function Fbccot in Figure 11. In a special case, when σ1=σ2=⋯=σs=σ, j∉J, the receiver obtains yσj, and this is single-choice CCOT function.Figure 11
The ideal functionFBCCOT.


### 4.4. Construction of BCCOT Protocol

Considering thats copies of garbled circuits used in secure two-party computation based on CCOT protocol, BCCOT can be regarded as a series of oblivious transfer protocol, which can be implemented by batch operation.Firstly, we give the construction ofBCCOT protocol corresponding to s copies’ garbled circuits in Figure 12. Sender P1 constructs s copies’ garbled circuits. Each circuit has 2n input wires, in which half of them are for P1’s input and the other half are for P2’s input wires. When all selection bit σi=σ and ji∉J, receiver P2 obtains yσ,i in every circuit.Figure 12
BCCOT protocol in secure two-party computation.


## 4.1. Ideal Function of CCOT

Lindell presented the concept ofCCOT, which is an oblivious transfer protocol combined with cut-and-choose index bit. We give a brief introduction about its ideal function FCCOT. Circuit constructor P1 constructs one garbled circuit; circuit evaluator P2 decides to obtain two key’s value of each wire or one key’s value of two wires, which is based on the index bit j∈0,1. When j=0, P2 wants to obtain both key’s value; when j=1, P2 wants to obtain one key’s value from two keys. We give a brief introduction about the ideal function in Figure 9.Figure 9
The ideal functionFCCOT.


## 4.2. Construction of CCOT Protocol

Cut−and−choose oblivioustransfer (CCOT) is a new primitive for secure two-party computation. For better understanding the role of CCOT protocol in secure two-party computation, we give a general introduction about CCOT protocol’s construction.Firstly, we give the construction of theCCOT protocol corresponding to a single garbled circuit in Figure 10.Figure 10
CCOT protocol in secure two-party computation.Given setup algorithm SetupMesssy and SetupDec algorithm,σ is selected bit from the receiver’s input.(1)
The receiverR is initialized with index bit j. When j=0, R invokes KeyGen∗crs,b algorithm to obtain pk0,skb, which is pk0=As+e+f−b·v, skb=s, pk1=pk0+v, and pkb=As+e+f.Whenj=1, R invokes KeyGen∗ algorithm to obtain pk0,skσ, which is pk0=As+e+f−σ·v, pk1=pk0+v, skσ=s, and pkσ=As+e+f.(2)
R sends relevant public key to sender S in corresponding index bit. When j=0, R sends A,pk0,pk1 to S. S encrypts message y0 and y1 under pk0 and pk1. S samples rb⟵Dℤ,rm and computes pbt=rbt·A; then, we obtain βi⟵Rrbt·pki⊕yi,i∈0,1. Finally, S sends cti=pb,βi to R.Whenj=1, R sends A,pk0,pk1 to S. S encrypts message y0 and y1 under pk0 and pk1. S samples rb⟵Dℤ,rm and computes pbt=rbt·A; then, we obtain βi⟵Rrbt·pki⊕yi,i∈0,1. Finally, S sends cti=pb,βi to R.(3)
Whenj=0, receiver R receives cti from sender S. R parses cti as pb,βi. R invokes Dec∗skb,cti to obtain yi by computing yi⟵Rpbt·skb⊕βi. Finally, R obtains y0 and y1.Whenj=1, R receives cti from S. R parses cti as pb,βi. R invokes Dec∗skσ,cti to obtain yσ by computing yi⟵Rpbt·skσ⊕βi.Lemma 5 (correctness [10]).
Givens≥ωlogmandB+B′·s·m=Oq, then the scheme can correctly decrypt in Dec branch.In the Dec mode, given the corresponding parameter, due to rounding function’s property, the receiver can correctly decrypt corresponding two ciphertext. In the Messy mode, whenσ=0, pk0=As+e+f, and secret key skσ=sk0=s can be used to decrypt ciphertext ct0. In the meantime, pk0=As+e+f+v and secret key skσ=sk0=s cannot be used to decrypt corresponding ciphertext ct1. When σ=1, pk1=As+e+f, and secret key skσ=sk1=s can be used to decrypt ciphertext ct1. However, pk0=As+e+f−v, and secret key skσ=sk0=s cannot be used to decrypt corresponding ciphertext ct0.The correctness of this protocol is shown in Table1, which is similar to the SmoothEnc System.Table 1
Protocol’s correctness.
(j,σ)InputOutput(0,σ)crs0,td0,crs0=A0,v0,v0=A0s0+e0,td0=s0y0⟵Rp0t·sk0⊕β0, y1⟵Rp1t·sk1⊕β1(1, 0)crs1,td1,crs1=A1,v1,v1=A1s1+e1,td1=s1y0⟵Rp0t·sk0⊕β0(1, 1)crs1,td1,crs1=A1,v1,v1=A1s1+e1,td1=s1y1⟵Rp1t·sk1⊕β1


### 4.2.1. Security Proof

Theorem 1.
Givens≥6mandm≥2n+1logq, the above scheme is UC-secure CCOT protocol under static malicious adversary, assuming the hardness of learning with errors with the corresponding parameter.We mainly consider two corruption cases; the sender is corrupted; the receiver is corrupted.Sender is corrupted: firstly, we consider adversary A corrupt sender P1, and we need to construct a simulator S, who can invoke adversary A′s input copies and make some operations as follows.whenj=0, run Dec mode’s setup algorithm SetupDec∗ and obtain crs0,t0⟵SetupDec∗1n, which is well known to all parties. Honest receiver P2 runs KeyGen∗ algorithm to obtain pk0,pk1,skb and then P2 sends pk0 and pk1 to sender P1. Corresponding this situation, simulator S invokes TrapKeyGen∗crs0,t0 algorithm to obtain pk,sk0,sk1 and then S sends sid,pk to adversary A, which simulates a interactive scenario between receiver P2 and adversary A. Then, simulator S stores sk0,sk1. Adversary A invokes Enc∗pk,y0,y1 algorithm to obtain ciphertext ct0,ct1 and A sends ct0,ct1 to receiver P2. Simulator S simulates this process; Simulator S receives ct0,ct1 from adversary A; S checks corresponding secret key sk0 and sk1 and invokes Dec∗skb,ctb,b∈0,1 algorithm to obtain yb′, b∈0,1. Simulator S sends y0′,y1′ to ideal function Fccot. Receiver P2 obtains the corresponding message based on mode index j and selection bit index σ.Receiveriscorrupted: adversary A corrupts receiver P2, and we need to construct a simulator S, who simulates the process between adversary A and sender P1.Whenj=1, run Messy mode’s setup algorithm SetupMessy∗ to obtain crs1,t1⟵SetupMessy∗1n, where crs1 is well known to all parties. We should notice that the distribution of crs1 is uniformly sampled. Honest sender P1 interacts with P2 corrupted by adversary A. Adversary A chooses a selection bit σ and then invokes KeyGen∗crs1,σ algorithm to obtain sid,pkσ,skσ, which is public to sender P1. Simulator S invokes FindMessy∗crs1,t1,pkσ to obtain messy branch b. Then, simulator S sends sid,receiver,1−b to ideal function of FOT. Then, simulator S receives corresponding message y1−b. Simulator S simulates the process between P1 and A.Firstly,S computes ctb⟵Enc∗pkb,0n and ct1−b⟵Enc∗pk1−b,y1−b. Secondly, S sends ctb,ct1−b to adversary A, as if from sender P1’s value. Finally, adversary A decrypts ctb with corresponding secret key skσ. Considering LWE’s assumption and Messy mode’s property, adversary A cannot obtain the correct message.


## 4.2.1. Security Proof

Theorem 1.
Givens≥6mandm≥2n+1logq, the above scheme is UC-secure CCOT protocol under static malicious adversary, assuming the hardness of learning with errors with the corresponding parameter.We mainly consider two corruption cases; the sender is corrupted; the receiver is corrupted.Sender is corrupted: firstly, we consider adversary A corrupt sender P1, and we need to construct a simulator S, who can invoke adversary A′s input copies and make some operations as follows.whenj=0, run Dec mode’s setup algorithm SetupDec∗ and obtain crs0,t0⟵SetupDec∗1n, which is well known to all parties. Honest receiver P2 runs KeyGen∗ algorithm to obtain pk0,pk1,skb and then P2 sends pk0 and pk1 to sender P1. Corresponding this situation, simulator S invokes TrapKeyGen∗crs0,t0 algorithm to obtain pk,sk0,sk1 and then S sends sid,pk to adversary A, which simulates a interactive scenario between receiver P2 and adversary A. Then, simulator S stores sk0,sk1. Adversary A invokes Enc∗pk,y0,y1 algorithm to obtain ciphertext ct0,ct1 and A sends ct0,ct1 to receiver P2. Simulator S simulates this process; Simulator S receives ct0,ct1 from adversary A; S checks corresponding secret key sk0 and sk1 and invokes Dec∗skb,ctb,b∈0,1 algorithm to obtain yb′, b∈0,1. Simulator S sends y0′,y1′ to ideal function Fccot. Receiver P2 obtains the corresponding message based on mode index j and selection bit index σ.Receiveriscorrupted: adversary A corrupts receiver P2, and we need to construct a simulator S, who simulates the process between adversary A and sender P1.Whenj=1, run Messy mode’s setup algorithm SetupMessy∗ to obtain crs1,t1⟵SetupMessy∗1n, where crs1 is well known to all parties. We should notice that the distribution of crs1 is uniformly sampled. Honest sender P1 interacts with P2 corrupted by adversary A. Adversary A chooses a selection bit σ and then invokes KeyGen∗crs1,σ algorithm to obtain sid,pkσ,skσ, which is public to sender P1. Simulator S invokes FindMessy∗crs1,t1,pkσ to obtain messy branch b. Then, simulator S sends sid,receiver,1−b to ideal function of FOT. Then, simulator S receives corresponding message y1−b. Simulator S simulates the process between P1 and A.Firstly,S computes ctb⟵Enc∗pkb,0n and ct1−b⟵Enc∗pk1−b,y1−b. Secondly, S sends ctb,ct1−b to adversary A, as if from sender P1’s value. Finally, adversary A decrypts ctb with corresponding secret key skσ. Considering LWE’s assumption and Messy mode’s property, adversary A cannot obtain the correct message.


## 4.3. Ideal Function of BCCOT

In secure two-party computation, Garbled circuits’ constructorP1 constructed many copies circuits, which can resist one situation about P1 constructing incorrect circuit. Let s be garbled circuits’ parameter. P1 constructs s copies circuits, half of these circuits are used for checking and another half are used for evaluation. After all check circuits pass detection, remaining half circuits are used for evaluating fx,y. Some garbled circuit maybe incorrectly constructed by P1, and we can adopt majority value of fx,y. Considering circuits’ parameter s, we introduce a ‘batch cut-and-choose’ oblivious transfer’s ideal function Fbccot in Figure 11. In a special case, when σ1=σ2=⋯=σs=σ, j∉J, the receiver obtains yσj, and this is single-choice CCOT function.Figure 11
The ideal functionFBCCOT.


## 4.4. Construction of BCCOT Protocol

Considering thats copies of garbled circuits used in secure two-party computation based on CCOT protocol, BCCOT can be regarded as a series of oblivious transfer protocol, which can be implemented by batch operation.Firstly, we give the construction ofBCCOT protocol corresponding to s copies’ garbled circuits in Figure 12. Sender P1 constructs s copies’ garbled circuits. Each circuit has 2n input wires, in which half of them are for P1’s input and the other half are for P2’s input wires. When all selection bit σi=σ and ji∉J, receiver P2 obtains yσ,i in every circuit.Figure 12
BCCOT protocol in secure two-party computation.



---

*Source: 9974604-2021-09-10.xml*