# An Efficient Outsourced Oblivious Transfer Extension Protocol and Its Applications

Authors: Shengnan Zhao; Xiangfu Song; Han Jiang; Ming Ma; Zhihua Zheng; Qiuliang Xu
Journal: Security and Communication Networks
 (2020)

---

## Abstract

Oblivious transfer (OT) is a cryptographic primitive originally used to transfer a collection of messages from the sender to the receiver in an oblivious manner. OT extension protocol reduces expensive asymmetric operations by running a small number of OT instances first and then cheap symmetric operations. While most earlier works discussed security model or communication and computation complexity of OT in general case, we focus on concrete application scenarios, especially where the sender in the OT protocol is a database with less computation and limited interaction capability. In this paper, we propose a generic outsourced OT extension protocol (OTex) that outsources all the asymmetric operations of the sender to a semihonest server so as to adapt to specific scenarios above. We give OTex a standard security definition, and the proposed protocol is proven secure in the semihonest model. In OTex, the sender works on the fly and performs only symmetric operations locally. Whatever the number of rounds OT to be executed and the length of messages in OT to be sent, our protocol realizes optimal complexity. Besides, OTex can be used to construct high-level protocols, such as private membership test (PMT) and private set intersection (PSI). We believe our OTex construction may be a building block in other applications as well.


---

## Body

## 1. Introduction

Oblivious transfer (OT) is one of the most important primitives in secure computation. It is wildly used in Yao’s protocol [1], GMW construction [2], and preprocessing phase of SPDZ-like [3] protocols. With the development of big data, cloud computing, and mobile computing, the demand for joint computation grows rapidly between different organizations and individuals. In order to ensure the security of such computing tasks against complicated external environment, cryptographic components have to be used to design protocols, in which OT plays a pivotal role together with homomorphic encryption, secret sharing, and garbled circuit.However, OT is public-key primitive centered, which makes it computational expensive for secure computation. Many privacy-preserving protocols, such as private membership test (PMT) and private set intersection (PSI), rely heavily on huge number of OT instances for secure computation to get the trade-off between computation and communication. The most efficient way to produce many OT instances is through OT extension protocol [4, 5]. In such protocol, two participants collectively run few “base” OT instances and then perform some cheap symmetric operations to produce many OT instances.


### 1.1. Motivation

In an OT extension protocol, the senderS needs to interact with the receiver ℛ for each step during the protocol, which involves exponential calculation and intensive interaction. In some application scenarios, however, S could be a mobile device with less computation power or a database holder with limited interaction capability. When invoking OT extension as a subprotocol in some more complex computation tasks, S needs to respond requests from ℛ as fast as possible.Nowadays, many applications are rapidly transferred to cloud-based service, and it would be desired to seek some server-aided OT extension protocol to relief the burden ofS under reasonable security assumption. A considerable literature [6–12] has grown up around the theme of fertilizing functionality of OT or optimizing communication cost of the receiver ℛ. However, far too little attention has been paid to investigate sender side of OT adapting to specific scenarios.To this end, we propose a generic outsourced oblivious transfer extension protocolOTex in the semihonest model. In OTex, the sender S first outsources all expensive asymmetric operations to a third party who runs a subprotocol called “base” OT instances with the receiver ℛ. Based on the corresponding outputs of the subprotocol and other auxiliary information, S generates symmetric keys used to encrypt sending messages in OT. As a result, the sender S works on the fly and sends its inputs encrypted by symmetric key generated from OTex to the receiver ℛ, and thus, it enables two parties to complete the whole OT extension protocol.Recent trends in OT extension have led to a proliferation of studies showing how to design an efficient PSI [13–17] or PSI-based protocols [18–21] in different secure models since OT extension protocol is an important component in secure computation and plays a key role in set operations. Take PSI as an example, without violating individuals’ privacy, and the use of PSI in contact tracing [21] can help prevent the further spread of COVID-19. Therefore, OTex framework has a wide range of applications in outsourced scenarios, and as a building block, we think OTex can be applied conveniently to high-level protocols.


### 1.2. Related Work

Rabin [22] first introduced the notion of OT that the receiver receives a message sent from the sender with probability 1/2 and the sender does not know whether the receiver has received the message or not. Then, a line of works seek to enrich functionality of OT, and they mainly consist of 1-out-of-2 OT [6], 1-out-of-n OT [7, 8], and k-out-of-n OT [9, 10], in which the first two functionalities are considered in this paper. Some researchers [23–25] proposed OT protocols in different security models although we focus on semihonest model that is sufficient enough to deploy our framework in future among including malicious model, covert adversary model, and universally composable model.Because OT is public-key primitive centered, the issue of efficiency has received considerable critical attention after Rabin’s work [22]. Beaver [26] showed that OT can be precomputed using only prior transfers. Studies over the past two decades have proved that extending a small number of OT to huge number of OT instances can be achieved by one-way function [27–29]. Until 2003, Ishai et al. [4] proposed an efficient method to extend 1-out-of-2 OTs by running few “base” OT instances, which is also known as the IKNP OT extension protocol. Kolesnikov and Kumaresan [5] generalized IKNP from a coding understanding and proposed an improved OT extension protocol allowing to do 1-of-out-n OTs with less communication and computation cost. Lindell et al. [11] studied input-size hiding two-party computation based on fully homomorphic encryption (FHE) and proposed a secure OT extension protocol to reduce the communication cost of both the sender and receiver. Cho et al. [12] focused on the receivers’ communication cost in OT and proposed laconic OT protocol based on the decisional Diffie–Hellman (DDH) assumption. Carter et al. [30] proposed outsourced OT protocol specifically for the mobile use-case where the cloud receives outputs of OT. Recently, Mansy and Rindal proposed [31] noninteractive OTs from noninteractive key exchange. However, the resulting OT extension would require 3 rounds.The research to date has tended to focus more on the cost of the receiver and less on the sender in OT, and there are few studies that have investigated computation and communication complexity on sender side. The aim of this work is to explore the cost of sender in OT and construct efficient OT extension framework assisted by a third party. In addition, OT extension provides a brief but useful account of the construction of oblivious pseudorandom function (PRF). Also, oblivious PRF has been attracting a lot of interest in very recent years, such as multiparty PSI [14], PSI cardinality [21], and private set union [32]. This indicates a need to adapt OT extension to outsourcing scenarios due to practical constraints.


### 1.3. Our Contribution

In this paper, we focus on server-aided OT to reduce the sender’s public-key computation and rounds of interaction with the receiver. Main contributions of our work go as follows:(i)
We propose a generic outsourced OT extension protocolOTex. In OTex, the server and the receiver cooperatively run a small number of OT instances, and at this moment, the sender can be off-line. After the first phase, the sender can fetch necessary corelated randomness from the server whenever needed; then, the sender can send their inputs encrypted only by a symmetric key to the receiver, which completes an OT instance. We design a novel mechanism for this purpose and formally prove its security under semihonest model.(ii)
We analyze the complexity of our construction and perform implementation, and the experiment shows that our construction is practical and efficient.(iii)
OurOTex construction can be applied to improve the efficiency of OT-based privacy-preserving primitives in server-aided setting, such as oblivious pseudorandom function, and high-level protocols, such as PMT and PSI, which is of independent interest.


## 1.1. Motivation

In an OT extension protocol, the senderS needs to interact with the receiver ℛ for each step during the protocol, which involves exponential calculation and intensive interaction. In some application scenarios, however, S could be a mobile device with less computation power or a database holder with limited interaction capability. When invoking OT extension as a subprotocol in some more complex computation tasks, S needs to respond requests from ℛ as fast as possible.Nowadays, many applications are rapidly transferred to cloud-based service, and it would be desired to seek some server-aided OT extension protocol to relief the burden ofS under reasonable security assumption. A considerable literature [6–12] has grown up around the theme of fertilizing functionality of OT or optimizing communication cost of the receiver ℛ. However, far too little attention has been paid to investigate sender side of OT adapting to specific scenarios.To this end, we propose a generic outsourced oblivious transfer extension protocolOTex in the semihonest model. In OTex, the sender S first outsources all expensive asymmetric operations to a third party who runs a subprotocol called “base” OT instances with the receiver ℛ. Based on the corresponding outputs of the subprotocol and other auxiliary information, S generates symmetric keys used to encrypt sending messages in OT. As a result, the sender S works on the fly and sends its inputs encrypted by symmetric key generated from OTex to the receiver ℛ, and thus, it enables two parties to complete the whole OT extension protocol.Recent trends in OT extension have led to a proliferation of studies showing how to design an efficient PSI [13–17] or PSI-based protocols [18–21] in different secure models since OT extension protocol is an important component in secure computation and plays a key role in set operations. Take PSI as an example, without violating individuals’ privacy, and the use of PSI in contact tracing [21] can help prevent the further spread of COVID-19. Therefore, OTex framework has a wide range of applications in outsourced scenarios, and as a building block, we think OTex can be applied conveniently to high-level protocols.


## 1.2. Related Work

Rabin [22] first introduced the notion of OT that the receiver receives a message sent from the sender with probability 1/2 and the sender does not know whether the receiver has received the message or not. Then, a line of works seek to enrich functionality of OT, and they mainly consist of 1-out-of-2 OT [6], 1-out-of-n OT [7, 8], and k-out-of-n OT [9, 10], in which the first two functionalities are considered in this paper. Some researchers [23–25] proposed OT protocols in different security models although we focus on semihonest model that is sufficient enough to deploy our framework in future among including malicious model, covert adversary model, and universally composable model.Because OT is public-key primitive centered, the issue of efficiency has received considerable critical attention after Rabin’s work [22]. Beaver [26] showed that OT can be precomputed using only prior transfers. Studies over the past two decades have proved that extending a small number of OT to huge number of OT instances can be achieved by one-way function [27–29]. Until 2003, Ishai et al. [4] proposed an efficient method to extend 1-out-of-2 OTs by running few “base” OT instances, which is also known as the IKNP OT extension protocol. Kolesnikov and Kumaresan [5] generalized IKNP from a coding understanding and proposed an improved OT extension protocol allowing to do 1-of-out-n OTs with less communication and computation cost. Lindell et al. [11] studied input-size hiding two-party computation based on fully homomorphic encryption (FHE) and proposed a secure OT extension protocol to reduce the communication cost of both the sender and receiver. Cho et al. [12] focused on the receivers’ communication cost in OT and proposed laconic OT protocol based on the decisional Diffie–Hellman (DDH) assumption. Carter et al. [30] proposed outsourced OT protocol specifically for the mobile use-case where the cloud receives outputs of OT. Recently, Mansy and Rindal proposed [31] noninteractive OTs from noninteractive key exchange. However, the resulting OT extension would require 3 rounds.The research to date has tended to focus more on the cost of the receiver and less on the sender in OT, and there are few studies that have investigated computation and communication complexity on sender side. The aim of this work is to explore the cost of sender in OT and construct efficient OT extension framework assisted by a third party. In addition, OT extension provides a brief but useful account of the construction of oblivious pseudorandom function (PRF). Also, oblivious PRF has been attracting a lot of interest in very recent years, such as multiparty PSI [14], PSI cardinality [21], and private set union [32]. This indicates a need to adapt OT extension to outsourcing scenarios due to practical constraints.


## 1.3. Our Contribution

In this paper, we focus on server-aided OT to reduce the sender’s public-key computation and rounds of interaction with the receiver. Main contributions of our work go as follows:(i)
We propose a generic outsourced OT extension protocolOTex. In OTex, the server and the receiver cooperatively run a small number of OT instances, and at this moment, the sender can be off-line. After the first phase, the sender can fetch necessary corelated randomness from the server whenever needed; then, the sender can send their inputs encrypted only by a symmetric key to the receiver, which completes an OT instance. We design a novel mechanism for this purpose and formally prove its security under semihonest model.(ii)
We analyze the complexity of our construction and perform implementation, and the experiment shows that our construction is practical and efficient.(iii)
OurOTex construction can be applied to improve the efficiency of OT-based privacy-preserving primitives in server-aided setting, such as oblivious pseudorandom function, and high-level protocols, such as PMT and PSI, which is of independent interest.


## 2. Preliminaries

### 2.1. Notation

Unless otherwise stated, we use OT to denote 1-out-of-2 OT andOTlk to denote k instances of 1-out-of-2 OT of l-bit strings. For simplicity, let H· denote random oracles with a suitable secure output length, which will be well defined in an actual protocol. Matrices are denoted by capital letters, and vectors are denoted by small bold letters; that is, ti denotes the i-th row of a matrix T, and tj denotes the j-th column of T. Small light front with subscript si denotes the i-th bit of a string s. Notably, we regard strings as vectors and do not distinguish the difference between strings and vectors. If s=s1⋯sn and t=t1⋯tn are two strings, then the notation s⊕t denotes s1⊕t1⋯sn⊕tn. Similarly, the notation s⊙t denotes the vector s1·t1⋯sn·tn. Specially, when c∈0,1, c·s denotes the vector c·s1⋯c·sn.


### 2.2. Secure Computation and Security Model

The formal definition of security of a secure multiparty protocol [33] is based on comparing two output distributions coming from an ideal world and a real world, respectively. The functionality of three parties P1,P2,P3 is denoted as f:0,1∗×0,1∗×0,1∗↦0,1∗×0,1∗×0,1∗, where f=f1,f2,f3 and Pi gets fi as output.Ideal/reality Simulation Paradigm. In an ideal world, participants send the input to an external trusted party who computes the functionality and sends each participant the corresponding output. Suppose there exists an adversary who has the inputs and outputs of a protocol in the ideal world and executes attack against a real protocol, then there always be an adversary executing the same attack in the ideal world. In a real protocol, if no adversary can do more harm than the execution of the protocol in the ideal world, the protocol in the real world is said to secure.Computationally Indistinguishability. Two distribution probability ensembles X=Xa,na∈0,1∗;n∈ℕ and Y=Ya,na∈0,1∗;n∈ℕ are said to be computationally indistinguishable, denoted by X≡cY, if for every nonuniform polynomial-time algorithm D, there exists a negligible function μ· such that for every a∈0,1∗ and every n∈ℕ:(1)PrDXa,n=1−PrDYa,n=1≤μn.Semihonest Adversary Model. In the semihonest adversary model, corrupted participant must execute the protocol correctly. However, the adversary can comprehensively obtain the internal status of the corrupted party, e.g., the transcripts of all received messages, and then tries to obtain additional information that should be kept confidential. Semihonest model is sufficient and captures many scenarios in practice although it is a very weak adversary model.In this paper, we focus on semihonest model and honest majority case where an adversary can corrupt at most one participant and any two participants will not get colluded. In the following, the formal security definition is proposed.Definition 1.
Letf=f1,f2,f3 be a deterministic functionality and π be a three-party protocol for computing f. Given the security parameter κ and triple inputs x,y,z, where x is from P1, y is from P2, and z is from P3, the view of Pii=1,2,3 in the protocol π is denoted as viewiπx,y,z,κ=w,ri,mi1,…,mit, where w∈x,y,z, ri is the randomness used by Pi, and mij is the j-th message received by Pi; the output of Pi is denoted as outputiπx,y,z,κ, and the joint output of the parties is outputπx,y,z,κ=output1πx,y,z,κ,output2πx,y,z,κ,output3πx,y,z,κ. We say that π securely computes f in the semihonest model if the following holds:(i)
The correctness holds:(2)outputπx,y,z,κ≡cfx,y,zx,y,z,κ.(ii)
There exist probabilistic polynomial-time simulatorsS1, S2, and S3 such that(3)S11κ,x,f1x,y,zx,y,z,κ≡cview1πx,y,z,κx,y,z,κ,S21κ,y,f2x,y,zx,y,z,κ≡cview2πx,y,z,κx,y,z,κ,S31κ,z,f3x,y,zx,y,z,κ≡cview3πx,y,z,κx,y,z,κ.


#### 2.2.1.OTex Security Model

InOTex, a simpler definition can be used since two of three parties output nothing (see ℱOTex in Figure 1). Specifically, three parties P1,P2,P3 stand for server S, sender S, and receiver ℛ, respectively. The functionality of OTex can be given by simply writing f:0,1∗,xi0,xi1,c↦λ,λ,xici, where λ denotes the empty string. We still require correctness described above, and security meaning that there exist three simulators SimS, SimS, and Simℛ such that(4)SimS1κ,s,⊥x,s,c,κ≡cviewSπx,s,c,κx,s,c,κ,SimS1κ,x,⊥x,s,c,κ≡cviewSπx,s,c,κx,s,c,κ,Simℛ1κ,c,x˜x,s,c,κ≡cviewℛπx,s,c,κx,s,c,κ,where x denotes input set xi0,xi1 from S, x˜ denotes output xici of ℛ, and ⊥ denotes null value.Figure 1
Outsourced oblivious transfer functionalityℱOTex.


### 2.3. OT Extension

We start by introducing the definition of standard 1-out-of-2 OT, where a sender holding two messagesm0,m1 interacts with a receiver holding a choice bit b. The 1-out-of-2 OT protocol guarantees that the receiver obtains mb without knowing anything about m1−b, while the sender knows nothing about b. The ideal functionality for 1-out-of-2 OT, denoted as ℱOT, is described in Figure 2.Figure 2
1-out-of-2 oblivious transfer functionalityℱOT.In most settings, it is necessary to run a large number of OT instances at the same time. The multiexecution of OT is called batch OT (see Figure3) denoted as ℱOTlm. The IKNP OT extension protocol [4] is a real milestone in the development of OT research computing ℱOTlm efficiently. It is trivial to compute ℱOTlm by simultaneously running ℱOTm times although it leads to large costs on computation and communication. Therefore, OT extension is the most efficient way for executing ℱOTlm instead of running m instances of OT in parallel.Figure 3
Batch oblivious transfer functionalityℱOTlm.As shown in Figure3, the functionality of IKNP is that ℛ receives messages xici|i∈m without knowing anything about xi1−ci|i∈m, while S knows nothing about c, where ci denotes the i-th bit of c. In the IKNP protocol, after acting as the receiver in ℱOT and running it k times, S computes m pairs of symmetric keys denoted as K10,K11,…,Km0,Km1, which are used to encrypt each pair of messages xi0,xi1, where i∈m. For each pair of symmetric keys Ki0,Ki1, ℛ only knows the exact one according to his selection string, i.e.,Kici|ci∈c,i∈m. The key insight of IKNP OT extension is to execute such an OT-based key agreement between S and ℛ in the following way:ℛ forms m×k matrix T at random and then computes matrix U such that ti⊕ui=ci⋯ci. S chooses s←0,1k at random. For each j∈k, ℛ invokes ℱOT with input tj,uj, and S acts as the receiver with selection bit sj. S receives qj after each computation of ℱOT and then forms matrix Q. For each column of matrix Q, it implies qj=sj⊕1·tj⊕sj·uj=tj⊕sj·c. The essential observation is that, for each row of matrix Q, it holds(5)qi=ti⊕ci·s.S prepares key pairs by Ki0=Hqi and Ki1=Hqi⊕s and ℛ exactly knows Kici=Hti, where ti is generated by ℛ locally. In addition, due to the randomness of s chosen by S, ℛ learns Ki1−ci=Hti⊕s with no more than a negligible probability 1/2k. Then, S can execute just symmetric operations so as to encrypt each pair of messages using key pairs Ki0,Ki1 and sends m pairs of encrypted messages to ℛ. Finally, ℛ can decrypt the corresponding message for each message pairs under Kici=Hti.As described above, the IKNP protocol begins with runningℱOTk times and then executes lots of symmetric operations to “extend” these OT instances, which are also called as “base” OTs.


### 2.4. Oblivious PRF

Freedman et al. [34] proposed oblivious evaluation of pseudorandom function (OPRF) and gave a general construction of OPRF from OT. An OPRF is a two-party protocol where a senderP1 inputting a random seed s obtains nothing while a receiverP2 inputting an evaluation point x obtains fsx for some pseudorandom function family fs. The functionality of OPRF (see Figure 4) can be defined by s,x↦λ,fsx.Figure 4
Oblivious PRF functionalityℱOPRF.A general definition of OPRF is that the receiverP2 inputs an evaluation set X=xi and obtains the evaluations on a PRF in an oblivious manner, i.e.,fsxi. The functionality in Figure 4 can be regarded as a special and simplified case although it is sufficient to construct such an efficient OPRF for some scenarios. In this paper, we consider only the definition where receiverP2 evaluates the PRF on a single point x, which can be constructed massively in an efficient manner.


#### 2.4.1. Batched OPRF Based on OT Extension

Kolesnikov and Kumaresan [5] generalized IKNP and proposed KK protocol realizing 1−out−of−2l OTs in an efficient way. In IKNP, the equation ti⊕ui=ci⋯ci means that each row of matrix T⊕U is either all zeros or all ones. This feature was interpreted as a repetition code in KK, and they improved it using a linear error correcting code denoted by C. Now for each row in T and U, it holds that ti⊕ui=Cci, where C is a public linear error correcting code of dimension l and codeword length k. Therefore, in KK, equation (5) becomes(6)qi=ti⊕Cci⊙s.Notably,ci stands for the i-th element in vector c, and now, it is no longer a binary bit in equation (5) but an l-bit string. The codeword length of Cci determines the length of s and the number of columns of matrices T and U, instead in IKNP of k (k is relative to a security parameter κ). In KK, to reach the same security requirement, the codeword length k′ is about twice as much as k. That is to say, kKK≈2.5kIKNP. As a consequence, the number of “base” OT in KK is doubled than that in IKNP.Based on 1-out-of-n OT extension, Kolesnikov et al. [13] proposed a variant of OPRF and described an efficient protocol to generate batched OPRF instances (known as BaRK-OPRF). From the point of adaption of OT extension, the variant OPRF functionality based on equation (6) is that(7)qi,s,ci⟼λ,Hi,qi⊕Cci⊙s,where C now is a pseudorandom code instead of a linear error correcting code.Notably, the random seeds consists of qi,s in BaRK-OPRF and i∈m, indicating that equation (6) essentially instantiates m different OPRFs in total, and this is why BaRK-OPRF is called bathed and key-related OPRF. In addition, the codeword length of pseudorandom code in BaRK-OPRF is approximately 2 times longer than the output length of linear error correcting code in KK, which is necessary to reach security requirement. Based on OPRF, it is trivial to construct the private membership test, which will be illustrated later.


## 2.1. Notation

Unless otherwise stated, we use OT to denote 1-out-of-2 OT andOTlk to denote k instances of 1-out-of-2 OT of l-bit strings. For simplicity, let H· denote random oracles with a suitable secure output length, which will be well defined in an actual protocol. Matrices are denoted by capital letters, and vectors are denoted by small bold letters; that is, ti denotes the i-th row of a matrix T, and tj denotes the j-th column of T. Small light front with subscript si denotes the i-th bit of a string s. Notably, we regard strings as vectors and do not distinguish the difference between strings and vectors. If s=s1⋯sn and t=t1⋯tn are two strings, then the notation s⊕t denotes s1⊕t1⋯sn⊕tn. Similarly, the notation s⊙t denotes the vector s1·t1⋯sn·tn. Specially, when c∈0,1, c·s denotes the vector c·s1⋯c·sn.


## 2.2. Secure Computation and Security Model

The formal definition of security of a secure multiparty protocol [33] is based on comparing two output distributions coming from an ideal world and a real world, respectively. The functionality of three parties P1,P2,P3 is denoted as f:0,1∗×0,1∗×0,1∗↦0,1∗×0,1∗×0,1∗, where f=f1,f2,f3 and Pi gets fi as output.Ideal/reality Simulation Paradigm. In an ideal world, participants send the input to an external trusted party who computes the functionality and sends each participant the corresponding output. Suppose there exists an adversary who has the inputs and outputs of a protocol in the ideal world and executes attack against a real protocol, then there always be an adversary executing the same attack in the ideal world. In a real protocol, if no adversary can do more harm than the execution of the protocol in the ideal world, the protocol in the real world is said to secure.Computationally Indistinguishability. Two distribution probability ensembles X=Xa,na∈0,1∗;n∈ℕ and Y=Ya,na∈0,1∗;n∈ℕ are said to be computationally indistinguishable, denoted by X≡cY, if for every nonuniform polynomial-time algorithm D, there exists a negligible function μ· such that for every a∈0,1∗ and every n∈ℕ:(1)PrDXa,n=1−PrDYa,n=1≤μn.Semihonest Adversary Model. In the semihonest adversary model, corrupted participant must execute the protocol correctly. However, the adversary can comprehensively obtain the internal status of the corrupted party, e.g., the transcripts of all received messages, and then tries to obtain additional information that should be kept confidential. Semihonest model is sufficient and captures many scenarios in practice although it is a very weak adversary model.In this paper, we focus on semihonest model and honest majority case where an adversary can corrupt at most one participant and any two participants will not get colluded. In the following, the formal security definition is proposed.Definition 1.
Letf=f1,f2,f3 be a deterministic functionality and π be a three-party protocol for computing f. Given the security parameter κ and triple inputs x,y,z, where x is from P1, y is from P2, and z is from P3, the view of Pii=1,2,3 in the protocol π is denoted as viewiπx,y,z,κ=w,ri,mi1,…,mit, where w∈x,y,z, ri is the randomness used by Pi, and mij is the j-th message received by Pi; the output of Pi is denoted as outputiπx,y,z,κ, and the joint output of the parties is outputπx,y,z,κ=output1πx,y,z,κ,output2πx,y,z,κ,output3πx,y,z,κ. We say that π securely computes f in the semihonest model if the following holds:(i)
The correctness holds:(2)outputπx,y,z,κ≡cfx,y,zx,y,z,κ.(ii)
There exist probabilistic polynomial-time simulatorsS1, S2, and S3 such that(3)S11κ,x,f1x,y,zx,y,z,κ≡cview1πx,y,z,κx,y,z,κ,S21κ,y,f2x,y,zx,y,z,κ≡cview2πx,y,z,κx,y,z,κ,S31κ,z,f3x,y,zx,y,z,κ≡cview3πx,y,z,κx,y,z,κ.


### 2.2.1.OTex Security Model

InOTex, a simpler definition can be used since two of three parties output nothing (see ℱOTex in Figure 1). Specifically, three parties P1,P2,P3 stand for server S, sender S, and receiver ℛ, respectively. The functionality of OTex can be given by simply writing f:0,1∗,xi0,xi1,c↦λ,λ,xici, where λ denotes the empty string. We still require correctness described above, and security meaning that there exist three simulators SimS, SimS, and Simℛ such that(4)SimS1κ,s,⊥x,s,c,κ≡cviewSπx,s,c,κx,s,c,κ,SimS1κ,x,⊥x,s,c,κ≡cviewSπx,s,c,κx,s,c,κ,Simℛ1κ,c,x˜x,s,c,κ≡cviewℛπx,s,c,κx,s,c,κ,where x denotes input set xi0,xi1 from S, x˜ denotes output xici of ℛ, and ⊥ denotes null value.Figure 1
Outsourced oblivious transfer functionalityℱOTex.


## 2.2.1.OTex Security Model

InOTex, a simpler definition can be used since two of three parties output nothing (see ℱOTex in Figure 1). Specifically, three parties P1,P2,P3 stand for server S, sender S, and receiver ℛ, respectively. The functionality of OTex can be given by simply writing f:0,1∗,xi0,xi1,c↦λ,λ,xici, where λ denotes the empty string. We still require correctness described above, and security meaning that there exist three simulators SimS, SimS, and Simℛ such that(4)SimS1κ,s,⊥x,s,c,κ≡cviewSπx,s,c,κx,s,c,κ,SimS1κ,x,⊥x,s,c,κ≡cviewSπx,s,c,κx,s,c,κ,Simℛ1κ,c,x˜x,s,c,κ≡cviewℛπx,s,c,κx,s,c,κ,where x denotes input set xi0,xi1 from S, x˜ denotes output xici of ℛ, and ⊥ denotes null value.Figure 1
Outsourced oblivious transfer functionalityℱOTex.


## 2.3. OT Extension

We start by introducing the definition of standard 1-out-of-2 OT, where a sender holding two messagesm0,m1 interacts with a receiver holding a choice bit b. The 1-out-of-2 OT protocol guarantees that the receiver obtains mb without knowing anything about m1−b, while the sender knows nothing about b. The ideal functionality for 1-out-of-2 OT, denoted as ℱOT, is described in Figure 2.Figure 2
1-out-of-2 oblivious transfer functionalityℱOT.In most settings, it is necessary to run a large number of OT instances at the same time. The multiexecution of OT is called batch OT (see Figure3) denoted as ℱOTlm. The IKNP OT extension protocol [4] is a real milestone in the development of OT research computing ℱOTlm efficiently. It is trivial to compute ℱOTlm by simultaneously running ℱOTm times although it leads to large costs on computation and communication. Therefore, OT extension is the most efficient way for executing ℱOTlm instead of running m instances of OT in parallel.Figure 3
Batch oblivious transfer functionalityℱOTlm.As shown in Figure3, the functionality of IKNP is that ℛ receives messages xici|i∈m without knowing anything about xi1−ci|i∈m, while S knows nothing about c, where ci denotes the i-th bit of c. In the IKNP protocol, after acting as the receiver in ℱOT and running it k times, S computes m pairs of symmetric keys denoted as K10,K11,…,Km0,Km1, which are used to encrypt each pair of messages xi0,xi1, where i∈m. For each pair of symmetric keys Ki0,Ki1, ℛ only knows the exact one according to his selection string, i.e.,Kici|ci∈c,i∈m. The key insight of IKNP OT extension is to execute such an OT-based key agreement between S and ℛ in the following way:ℛ forms m×k matrix T at random and then computes matrix U such that ti⊕ui=ci⋯ci. S chooses s←0,1k at random. For each j∈k, ℛ invokes ℱOT with input tj,uj, and S acts as the receiver with selection bit sj. S receives qj after each computation of ℱOT and then forms matrix Q. For each column of matrix Q, it implies qj=sj⊕1·tj⊕sj·uj=tj⊕sj·c. The essential observation is that, for each row of matrix Q, it holds(5)qi=ti⊕ci·s.S prepares key pairs by Ki0=Hqi and Ki1=Hqi⊕s and ℛ exactly knows Kici=Hti, where ti is generated by ℛ locally. In addition, due to the randomness of s chosen by S, ℛ learns Ki1−ci=Hti⊕s with no more than a negligible probability 1/2k. Then, S can execute just symmetric operations so as to encrypt each pair of messages using key pairs Ki0,Ki1 and sends m pairs of encrypted messages to ℛ. Finally, ℛ can decrypt the corresponding message for each message pairs under Kici=Hti.As described above, the IKNP protocol begins with runningℱOTk times and then executes lots of symmetric operations to “extend” these OT instances, which are also called as “base” OTs.


## 2.4. Oblivious PRF

Freedman et al. [34] proposed oblivious evaluation of pseudorandom function (OPRF) and gave a general construction of OPRF from OT. An OPRF is a two-party protocol where a senderP1 inputting a random seed s obtains nothing while a receiverP2 inputting an evaluation point x obtains fsx for some pseudorandom function family fs. The functionality of OPRF (see Figure 4) can be defined by s,x↦λ,fsx.Figure 4
Oblivious PRF functionalityℱOPRF.A general definition of OPRF is that the receiverP2 inputs an evaluation set X=xi and obtains the evaluations on a PRF in an oblivious manner, i.e.,fsxi. The functionality in Figure 4 can be regarded as a special and simplified case although it is sufficient to construct such an efficient OPRF for some scenarios. In this paper, we consider only the definition where receiverP2 evaluates the PRF on a single point x, which can be constructed massively in an efficient manner.


### 2.4.1. Batched OPRF Based on OT Extension

Kolesnikov and Kumaresan [5] generalized IKNP and proposed KK protocol realizing 1−out−of−2l OTs in an efficient way. In IKNP, the equation ti⊕ui=ci⋯ci means that each row of matrix T⊕U is either all zeros or all ones. This feature was interpreted as a repetition code in KK, and they improved it using a linear error correcting code denoted by C. Now for each row in T and U, it holds that ti⊕ui=Cci, where C is a public linear error correcting code of dimension l and codeword length k. Therefore, in KK, equation (5) becomes(6)qi=ti⊕Cci⊙s.Notably,ci stands for the i-th element in vector c, and now, it is no longer a binary bit in equation (5) but an l-bit string. The codeword length of Cci determines the length of s and the number of columns of matrices T and U, instead in IKNP of k (k is relative to a security parameter κ). In KK, to reach the same security requirement, the codeword length k′ is about twice as much as k. That is to say, kKK≈2.5kIKNP. As a consequence, the number of “base” OT in KK is doubled than that in IKNP.Based on 1-out-of-n OT extension, Kolesnikov et al. [13] proposed a variant of OPRF and described an efficient protocol to generate batched OPRF instances (known as BaRK-OPRF). From the point of adaption of OT extension, the variant OPRF functionality based on equation (6) is that(7)qi,s,ci⟼λ,Hi,qi⊕Cci⊙s,where C now is a pseudorandom code instead of a linear error correcting code.Notably, the random seeds consists of qi,s in BaRK-OPRF and i∈m, indicating that equation (6) essentially instantiates m different OPRFs in total, and this is why BaRK-OPRF is called bathed and key-related OPRF. In addition, the codeword length of pseudorandom code in BaRK-OPRF is approximately 2 times longer than the output length of linear error correcting code in KK, which is necessary to reach security requirement. Based on OPRF, it is trivial to construct the private membership test, which will be illustrated later.


## 2.4.1. Batched OPRF Based on OT Extension

Kolesnikov and Kumaresan [5] generalized IKNP and proposed KK protocol realizing 1−out−of−2l OTs in an efficient way. In IKNP, the equation ti⊕ui=ci⋯ci means that each row of matrix T⊕U is either all zeros or all ones. This feature was interpreted as a repetition code in KK, and they improved it using a linear error correcting code denoted by C. Now for each row in T and U, it holds that ti⊕ui=Cci, where C is a public linear error correcting code of dimension l and codeword length k. Therefore, in KK, equation (5) becomes(6)qi=ti⊕Cci⊙s.Notably,ci stands for the i-th element in vector c, and now, it is no longer a binary bit in equation (5) but an l-bit string. The codeword length of Cci determines the length of s and the number of columns of matrices T and U, instead in IKNP of k (k is relative to a security parameter κ). In KK, to reach the same security requirement, the codeword length k′ is about twice as much as k. That is to say, kKK≈2.5kIKNP. As a consequence, the number of “base” OT in KK is doubled than that in IKNP.Based on 1-out-of-n OT extension, Kolesnikov et al. [13] proposed a variant of OPRF and described an efficient protocol to generate batched OPRF instances (known as BaRK-OPRF). From the point of adaption of OT extension, the variant OPRF functionality based on equation (6) is that(7)qi,s,ci⟼λ,Hi,qi⊕Cci⊙s,where C now is a pseudorandom code instead of a linear error correcting code.Notably, the random seeds consists of qi,s in BaRK-OPRF and i∈m, indicating that equation (6) essentially instantiates m different OPRFs in total, and this is why BaRK-OPRF is called bathed and key-related OPRF. In addition, the codeword length of pseudorandom code in BaRK-OPRF is approximately 2 times longer than the output length of linear error correcting code in KK, which is necessary to reach security requirement. Based on OPRF, it is trivial to construct the private membership test, which will be illustrated later.


## 3. Overview of Our Construction

The functionality ofOTex is described in Figure 1. While the essential difference between ℱOTlm in Figure 3 and ℱOTex in Figure 1 may appear to be unimpressive and unnecessary, the distinction becomes more pronounced in the case of practical OT extension applications and even more so in outsourced OT scenarios.The codeword length of code schemes in equations (6) and (7), i.e., pseudorandom code and linear error correcting code, determines the number of “base” OT instances to be evaluated. This gives us the intuition that we could use a specific number of OTs to extend any large amount of OT instances we need. Both Ishai et al. [4] and Kolesnikov et al. [5, 13] show n OTs of long strings that can be reduced to k “base” OTs of shorter strings. That is, given pseudo-random generator and a small number of OTs, we can implement any ℱOTl′m′ we want. Therefore, we make OT execute in a program-iteration-like way (see Figure 5) to reach the final functionality ℱOTlm. Here, for clarity, we denote selection string in ℱOTki+1ki by bold letter ri instead of c, and j-th element of ri is denoted by rij.Figure 5
Overview of OT iteration.To better understand our work, let us review IKNP OT extension whereS holds m pairs of l-length messages x10,x11,…,xm0,xm1, and the receiver ℛ holds m-bit selection vector c. According to Figure 5, we now focus on OTk2k1 and OTk3k2 only. For i∈m, each row of matrices T2 and T2′ consists of xi0 and xi1, respectively; that is, both T2 and T2′ are m×l matrices and r2=c. Now, OTk2k1 serves as “base” OT in IKNP, while the final functionality is to realize OTk3k2, where k1 is the security parameter, k2=m, and k3=l. After OTk2k1, S computes equation (5) and sends encrypted T2 and T2′ to ℛ. Using symmetric-key operations only, ℛ receives V2 from T2 and T2′ in an oblivious way. For i∈m, each row of matrix V2 is xici. We have reviewed the whole framework of IKNP protocol so far, and it does matter the relationships among T1, T1′, and r2. If we write the algorithm implementing OTki+1ki as recursive function FOTki,ki+1 in programming language, then the key step in IKNP is that FOTm,l invokes FOTκ,m; i.e.,OTlm is reduced to OTmκ, where κ is the security parameter in IKNP. Thus, we implement FOTm,l by invoking FOTκ,m first and then executing some symmetric-key encryption operations.In more general case, two partiesP1 and P2 prepare to run protocol OTki+1ki, where P1 acts as sender S holding messages matrices Ti and Ti′ while P2 holds chosen vector ri. After OTki+1ki, P2 gets outputs Vi consisting of those messages he/she chooses to receive. According to OT extension protocol, P1 and P2 first run OTkiki−1, where P1 acts as a receiver and P2 acts as a sender. For each OTki+1ki and OTkiki−1, it holds(8)Ti−1j⊕Ti−1′j=frij.Ti−1j denotes the j-th row of matrix Ti−1j, rij denotes j-th element of ri, and f· for some encoding scheme, such as repetition code in equation (5) and linear error correcting code in equation (6). We present detailed f· in concrete protocol and just emphasize the connections between Ti−1 and ri here.OTki+1ki and OTkiki−1 are named as outer and inner OT, respectively. Specially, OTk2k1 is the innermost one. Then, we find that the two input vectors Ti−1 and Ti−1′ of the inner OTkiki−1 are determined by the input ri of the outer OTki+1ki. The role of P1 and P2 get reversed each time FOTki,ki+1 invokes FOTki−1,ki; that is to say, S in outer OT becomes the receiver in inner OT, so as to ℛ. Furthermore, OTkiki+1 (if exists) is the outer OT related to OTki−1ki; therefore, the input vectors of Ti and Ti′ are determined by ri+1.The transformation amongOTki+2ki+1, OTki+1ki, and OTkiki−1 is the main part of our work. The key observation is that the inputs of both two parties in OTkiki−1 and OTki+2ki+1 are independent. That is, Ti+1 and Ti−1, Ti+1′ and Ti−1′, and ri+1 and ri−1 are independent. If OTki+2ki+1 is a necessary component in protocol, we can precompute OTkiki−1 assisted with a semihonest server. We focus on a special-but-sufficient case where S and ℛ prepare to execute OTk3k2; notably, the innermost is OTk1k1 (see Figure 6) instead of OTk2k1. In such a scenario, k1 should not be less than security parameter. If ℛ is a normal user acting as the receiver in OTk3k2 and S is a database with limited computation power and interaction capability, the framework becomes more useful and efficient. Therefore, we consider a server-aided oblivious transfer reducing the sender’s all public-key computation and numbers of interaction with other parties. As shown in Figure 6, S outsources the computation marked with blue rectangle to a server.Figure 6
Construction ofOTex.OurOTex protocol consists of two major phases. First, in the outsourced phase, ℛ and serverS run OTk1k1 as follows. ℛ inputs random selection string r1, while S inputs two random k1×k1 matrices T1 and T1′. After OTk1k1, ℛ gets output V1 and prepares T2 (and T2′) for OTk2k1. In the second phase, S aims to respond to the request for OTlk2. This phase can be concluded as FOTk1,k2 invoking FOTk1,k1 and S sending pairs of messages (T3 and T3′ encrypted by V2) to ℛ. In the last phase, ℛ gets outputs from OTlk2, which can be seen as FOTk2,l invoking FOTk1,k2.


## 4. Outsourced Oblivious Transfer Extension

In this section, we show how to construct an outsourced oblivious transfer extension protocolOTex, where three-party functionality ℱOTex can be securely computed in the presence of semihonest adversaries.OurOTex protocol consists of two major phases among three parties, senderS, receiverℛ, and serverS. Figure 6 shows OTex construction in a program-iteration-like way, where a small number of OT instances, the innermost OTk1k1, are first to be executed cooperatively. In fact, we let k1=κ, and it becomes OTκκ, where κ is the security parameter in real protocol. From the global perspective, we give procedure of OTex in Figure 7 so as to have a better understanding of roles three parties play in every phase.Figure 7
Procedure of outsourced oblivious transfer.First, in theoutsourced phase, ℛ and S run OTκκ as follows. ℛ inputs random selection string r, while S inputs two random κ×κ matrices T and T′. After OTκκ, ℛ gets outputs D and prepares V (and V′) for OTmκ. In the second phase, S aims to respond to the request for OTlm. This phase can be concluded as FOTκ,m invoking FOTκ,κ and S sending pairs of messages (T and T′ encrypted by E) to ℛ. In the last phase, ℛ gets outputs from OTlm, which can be seen as FOTm,l invoking FOTκ,m.We describeOTex in Figure 8 which realizes functionality FOTex in Figure 4. The invoking procedure in OTex can be written as FOTm,l≫FOTκ,m≫FOTκ,κ.Figure 8
Outsourced oblivious transfer extension protocol.According to equation (8), each time FOTki,ki+1 invokes FOTki−1,ki, and it holds Ti−1j⊕Ti−1′j=frij. Let f· represent different encoding schemes each time iteration occurs. In OTex, we have Ti⊕T′i=f1s and Vj⊕V′j=f2c, where both f1· and f2· are repetition code with output length κ, i.e.,(9)f1s=si⋯si,f2c=ci⋯ci.Notably, in more general case, the outputs off1rij and f1ri+1j may be not equal length, which is determined by OTkiki−1 and OTki+1ki, respectively. Figures 7 and 8 illustrate OTex framework and procedure, where the symbols are consistent and the output length of repetition code is embodied in the number of columns in the matrices T and V.Theorem 1.
TheOTex protocol in Figure 8 securely computes the functionality FOTex (Figure 4) in semihonest setting, as described in Definition 1, given random oracle and functionality ℱOT(Figure 1).Proof.
We begin by proving the correctness. AfterOTex, we prove that ℛ only receives xici and knows nothing about xi1−ci when computing x˜i=z˜ici⊕Hi,vi. In the outsourced phase, it holds that(10)dj=tj⊕rj·s,di=ti⊕si·r,wherei,j∈κ.
Then, in the responding phase, Step 5,ℛ essentially computes(11)yj0=vj⊕H1j,tj⊕sj·r,yj1=v′j⊕H1j,tj⊕sj⊕1·r,wherej∈κ.
Therefore, in Step 6, forj∈κ, by computing ej=yjsj⊕H1j,tj, S gets ej=vj when sj=0 and gets ej=v′j when sj=1. Due to vi⊕vi′=ci⋯ci, we have ej=vj⊕sj·c and(12)ei=vi⊕ci·s,wherei∈m,j∈κ.
Forσ∈0,1, S computes ziσ=xiσ⊕Hi,ei⊕σ·s and essentially sends to S the following messages:(13)ziσ=xiσ⊕Hi,vi⊕ci⊕σ·s.
It holds thatHi,vi⊕ci⊕σ·s=Hi,vi if and only if ci=σ. Concretely, when ci=0, ℛ computes(14)x˜i=z˜i0⊕Hi,vi=xi0⊕Hi,vi⊕0⊕0·s⊕Hi,vi=xi0.
Whenci=1, ℛ computes(15)x˜i=z˜i1⊕Hi,vi=xi1⊕Hi,vi⊕1⊕1·s⊕Hi,vi=xi1.
In summary,ℛ only receives xici in OTex and cannot recover xi1−ci by computing z˜i1−ci⊕Hi,vi because ℛ knows nothing about Hi,vi⊕0⊕1·s, i.e.,Hi,vi⊕ci⊕1−ci·s.
This concludes the correctness ofOTex.
We now construct three simulatorsSimS, Simℛ, and Simℛ for simulating corrupt S, S, and ℛ such that the produced transcript and the view of real execution are computationally indistinguishable. That is,(16)SimS1κ,s,⊥x,s,c,κ≡cviewSπx,s,c,κx,s,c,κ,SimS1κ,x,⊥x,s,c,κ≡cviewSπx,s,c,κx,s,c,κ,Simℛ1κ,c,x˜x,s,c,κ≡cviewℛπx,s,c,κx,s,c,κ,where x denotes input set xi0,xi1 from S, x˜ denotes output x˜i of ℛ, and ⊥ denotes the null value.CorruptS. Given ℱOT, it is easy to perfectly simulate the view of the ServerS because S only has input, neither receives messages nor outputs during the execution of the protocol. That is, SimS1κ,s,⊥x,s,c,κ is computationally indistinguishable with viewSπx,s,c,κx,s,c,κ.CorruptS. In protocol, SenderS works only in the responding phase, when S receives messages from S and ℛ then sends encrypted inputs to ℛ. The messages obtained by S are s,T,yj0,yj1. That is to say, viewSπx,s,c,κ consists of input x and messages s,T,yj0,yj1, where j∈κ. It is trivial for SimS to generate a simulation of s,T since both are random values from the point of view of S.Now,SimS simulates a simulation of yj0,yj1|j∈κ by choosing a κ-length string s^, m-length strings r^j, κ×κ matrix T^, and m×κ matrix E^ at random and computing(17)y^js^j=e^j⊕H1j,t^j,y^j1−s^j=r^j.Lets^,T^,y^j0,y^j1 be the output of SimS1κ,x,⊥. Therefore, we claim that the view generated by SimS and the view of corrupt S in a real protocol are computationally indistinguishable.Corruptℛ. We construct a simulator Simℛ that simulates the view of corrupt ℛ in the real protocol execution. We first analyze ℛ’s view viewℛπx,s,c,κ in OTex. ℛ obtains matrix D in the outsourced phase and z˜i0,z˜i1 in the outputting phase. Therefore, viewℛπx,s,c,κ consists of ℛ’s input c and messages D,z˜i0,z˜i1. To construct the simulation of the view, Simℛ works as follows.(i)
In the outsourced phase, given the security parameterκ, ℛ’s input c, and the randomness r, Simℛ calls simulation SimOTκκ with input T^,T^′,r and gets output D^. Then, Simℛ appends the output of SimOTκκ, i.e., matrix D^, to its own output.(ii)
In the outputting phase, given the security parameterκ, ℛ’s input c, the randomness V, and output x˜, Simℛ simulates a simulation of z˜i0,z˜i1|i∈m by choosing m-length strings r^j and computing(18)z^ici=x˜i⊕Hi,vi,z^i1−ci=r^j.
Then,Simℛ appends z^i0,z^i1|i∈m to its output.
Combining two phases described above in sequence, we finally claim that the output ofSimℛ is computationally indistinguishable from the real execution, i.e.,Simℛ1κ,c,x˜x,s,c,κ≡cviewℛπx,s,c,κx,s,c,κ.
This completes the construction of three simulators:SimS, Simℛ, and Simℛ. In summary, OTex is secure under semihonest model.


### 4.1. Performance Analysis

We now analyze the performance ofOTex in semihonest model. The complexities of OTex are presented in Table 1.(i)
Computation complexity. The number of symmetric and asymmetric operation to be executed in OTex essentially depends on the size of matrices T, V, and E, respectively. In the outsourced phase, ℱOTκκ consists of Oκ public-key and Oκ private-key operations, for both S (acting as sender) and ℛ (acting as receiver). In the responding phase, ℛ invokes random oracle and performs XOR operation for Oκ times. Then, S recovers matrix E and encrypts messages xi0,xi1, which only consists of Om+κ symmetric operations. In the outputting phase, ℛ performs symmetric operations Om times to compute its outputs.(ii)
Communication complexity. In the outsourced phase, the number of bits transferred between S and ℛ is bounded by Oκ2. In the responding phase, S receives messages from S and ℛ and sends encrypted messages to ℛ, which consist of Oml+κ2. In the outputting phase, ℛ receives 2ml-bit messages in total from S.(iii)
Round complexity. The only interaction in OTex exists in the outsourced phase between S and ℛ, i.e.,ℱOTκκ. The number of interaction round in ℱOTκκ is bounded by 1.Table 1
Complexity ofOTex.
PartyComputationCommunicationRoundAsymmetricSymmetricServerSOκOκOκ21SenderS–Om+κOml+κ2–ReceiverℛOκOm+κOml+κ21


### 4.2. Efficiency Comparison

Since we focus on the efficiency of the senderS in OT, we provide comparisons to prior classical protocols from the S’s point of view in Table 2. In OTex, all asymmetric operations are operated between the receiver ℛ and the cloud server S, and S works on the fly and conducts symmetric computations locally.Table 2
Efficiency comparison.
ProtocolRoundCommunicationAsymmetric computationSecurity model[4]2Oml+mκOκSemihonest and malicious[5]2Omk/logn+lnlognOkSemihonest[16]2Oml+κ2Oκ+lnSemihonest and one-sided malicious[30]2Oml+mκOκSemihonest[31]3Oml+logG+κOκMaliciousOurs–Oml+κ2–SemihonestNote: the efficiency ofsender in OT is presented here, who inputs m pairs of l-bit length messages in protocol. Specially, κ is security parameter, G denotes a group, and k≈2.5κ in 1-out-of-n OT.


## 4.1. Performance Analysis

We now analyze the performance ofOTex in semihonest model. The complexities of OTex are presented in Table 1.(i)
Computation complexity. The number of symmetric and asymmetric operation to be executed in OTex essentially depends on the size of matrices T, V, and E, respectively. In the outsourced phase, ℱOTκκ consists of Oκ public-key and Oκ private-key operations, for both S (acting as sender) and ℛ (acting as receiver). In the responding phase, ℛ invokes random oracle and performs XOR operation for Oκ times. Then, S recovers matrix E and encrypts messages xi0,xi1, which only consists of Om+κ symmetric operations. In the outputting phase, ℛ performs symmetric operations Om times to compute its outputs.(ii)
Communication complexity. In the outsourced phase, the number of bits transferred between S and ℛ is bounded by Oκ2. In the responding phase, S receives messages from S and ℛ and sends encrypted messages to ℛ, which consist of Oml+κ2. In the outputting phase, ℛ receives 2ml-bit messages in total from S.(iii)
Round complexity. The only interaction in OTex exists in the outsourced phase between S and ℛ, i.e.,ℱOTκκ. The number of interaction round in ℱOTκκ is bounded by 1.Table 1
Complexity ofOTex.
PartyComputationCommunicationRoundAsymmetricSymmetricServerSOκOκOκ21SenderS–Om+κOml+κ2–ReceiverℛOκOm+κOml+κ21


## 4.2. Efficiency Comparison

Since we focus on the efficiency of the senderS in OT, we provide comparisons to prior classical protocols from the S’s point of view in Table 2. In OTex, all asymmetric operations are operated between the receiver ℛ and the cloud server S, and S works on the fly and conducts symmetric computations locally.Table 2
Efficiency comparison.
ProtocolRoundCommunicationAsymmetric computationSecurity model[4]2Oml+mκOκSemihonest and malicious[5]2Omk/logn+lnlognOkSemihonest[16]2Oml+κ2Oκ+lnSemihonest and one-sided malicious[30]2Oml+mκOκSemihonest[31]3Oml+logG+κOκMaliciousOurs–Oml+κ2–SemihonestNote: the efficiency ofsender in OT is presented here, who inputs m pairs of l-bit length messages in protocol. Specially, κ is security parameter, G denotes a group, and k≈2.5κ in 1-out-of-n OT.


## 5. Performance

In this section, we test the performance ofOTex. The experiments were performed on a Linux machine equipped with 4 cores 3.40 GHz Intel Core i5-7500 CPU and 8 GB RAM.Our tests refer to the implement on GitHub:https://github.com/emp-toolkit/emp-ot. We simulated main asymmetric operations in OTex on a single machine. We compared OTex with the OT protocol used in recent work [32], where they compute at least 450 OT instances locally from 128 “base” OTs. Therefore, we regarded n=28 as a reference and simulated the outsourced phase. After setting the length of security parameter equal to 128, we simulated OTex for n=27, 29, and 210, respectively. We repeated each simulation 20 times, and the result is shown in Figure 9. Although OTex shows an almost identical performance to Vladimir’s, the running time tends to be steady sooner when n=29. In addition, in Figure 9, the sender S of OTex works offline for most of the time during simulation, and this is one of the advantages of OTex.Figure 9
Comparison of running time.The other advantage ofOTex found in performance tests is the reduction of communication bottleneck caused by the sender S. The main idea of OT extension protocol is to extend a small number of base OTs to perform many OTs. As a consequence, we summed from the time of base OTon setup to the time of protocol finish and then computed average time for each original OT. The averaged time is illustrated in Figure 10. We tested n′=28+x OT instances for different x values and computed the average running time for one single OT, i.e.,OTn1. From Figure 10, we can see that the average time keeps steady when x is less than 8. If we extend base OT to an adequate number of OTs, for example, n′=218, the average time has a sharp increase. It does not matter in OTex, however, since the extension process is conducted between ℛ and S in the outsourced phase.Figure 10
Average time for OT instances inOTex.


## 6. Applications ofOTex

TheOTex framework has a wide range of applications in outsourced scenarios. In this section, we take private set intersection (PSI) as a case study and demonstrate that, as a building block, OTex can be applied conveniently to high-level protocol.We first introduce a private membership test (PMT) protocol to estimate whether an elementx belongs to a set Y=y1,…,ym or not and then describe how to efficiently implement it via OTex. The resulting protocol can then be simply extended to compute functionality ℱPSI in Figure 11 by applying the OTex-based PMT protocol.Figure 11
Private set intersection functionalityℱPSI.


### 6.1. OPRF-Based PMT Protocol

PMT protocol involves two parties:Alice who holds an element x and Bob who holds a set Y. After PMT, Bob knows nothing about x, and Alice only knows whether her element x belongs to the set Y or not.Based on OPRF, we can construct PMT protocol as follows. First, during the OPRF phase,Bob acts as sender with a random seed s. And Alice, acting as receiver, inputs her element x. After OPRF, Alice obtains fsx and Bob has fs·. Then, Bob sends all fsyi to Alice who compares fsx with fsyi one by one. In conclusion, Alice outputs 1 if and only if there exits an i such that fsyi=fsx and else outputs 0.The security of PMT via OPRF relies on the fact that an OPRF protocol is secure. In a secure OPRF, it guarantees thatfs· is a one-way pseudorandom function and the length of s equals to secure parameter. Therefore, Alice receives fsyi and then learns whether there exists an i such that fsyi=fsx, but she will not learn the exact values yi|yi∈Y,fsyi≠fsx with nonnegligible probability. We omit concrete security proof here.


### 6.2.OTex-Based PMT Protocol

Given functionalityℱOPRF, we can construct PMT protocol in a simple manner. In this section, we introduce how to design OPRF protocol based on OTex. Equation (7) indicates that 1-out-of-n OT extension implies BaRK-OPRF; therefore, we focus on the transformation from 1-out-of-n OT extension to OTex. As a result, OTex can be easily used to construct PMT protocol.We can apply pseudorandom code to equation (8) for defining new relationship among T2 and T2′ in Figure 6, which implements functionality ℱOPRF in Figure 3. In OTex, however, we stress that it always holds T1i⊕T1′i=f1r2i and T2j⊕T2′j=f1r3j, where f1· is the repetition code. This means that we implement INKP protocol in an outsourced manner since we use the same repetition code f1· in FOTk1,k2 and FOTk2,k3. That is to say, three parties, S, S, and ℛ, evaluate corporately m instances of 1-out-of-2 OT of l-bit messages where repetition code is used twice in total, each by S and ℛ, respectively. Now, suppose Alice and Bob would like to execute m instances of 1-out-of-n OT where Bob inputs y1j,y2j,…,ynj|j∈m,yij=l and Alice inputs her selection vector r3, and they need make the following adjustments:(i)
Bob organizes the inputs in OTex with m×l matrices T31,T32,…,T3n, where the j-th row of matrix T3i is yij.(ii)
Alice makes her selection vector in OTex be r3|j∈m,r3j∈n.Then, the only adaption they need take inOTex is that T2j⊕T2′j=f2r3j, where f2· is the linear error correcting code C. To reach the security requirement defined in [13], in OTex, we need to reset security parameter k rather than κ—concretely 3κ<k<4κ.Given 1-out-of-n OT protocol designed from OTex, it is trivial to design OTex-based OPRF so is to OTex-based PMT. Again, Alice prepares her element x=r31, while Bob holds set Y=y11,y21,…,yn1. In brief, if it holds in OTex that(19)T1i⊕T1′i=f1r2i,T2j⊕T2′j=Cr3j,where f1· is the repetition code and C is the pseudorandom code; OTex implies the functionality ℱOPRF where the seed s consists of V2,r2 generated by Bob and Alice gets fsx. Meanwhile, this essentially completes the main construction of OTex-based PMT protocol. All needed to do next is that Bob sends fsyi1|i∈n to Alice who compares fsx with fsyi1|i∈n locally.


### 6.3.OTex-Based PSI Protocol

To obtain the final PSI protocol that computesX∩Y, Alice simply invokes the PMT protocol for each xi∈X. The protocol in Figure 12 computes X∩Y in an outsourced manner. The intuition is that Alice holds a set X, while Bob holds Y, and after PMT, Alice knows whether her element xi belongs to Y or not, i.e., the intersection of two sets.Figure 12
Outsourced private set intersection protocol.Some details on method of preprocessing items in set are simply omitted in Figure12. We can hash the item to bins and then operate the OTex-based PSI protocol on each bin separately. Specifically, we use Cuckoo hashing [35] for PSI in the following way. First, Alice and Bob agree on 3 random hash functions h1,h2,h3:0,1∗⟶m′ suitable for 3-way Cuckoo hashing. Alice places her items into m in either h1x, h2x, or h3x, and each bin contains at most one item. Bob places each of his items y in locations h1y, h2y, and h3y. At this point, Alice pads her input with dummy items so that each bin contains exactly 1 item. Note that when we use cuckoo hashing, then there will be some items which cannot be placed into the table and have to be moved to a stash, which does not matter because of the usage of stash-less cuckoo hashing [20]. Finally, Alice and Bob perform a PSI in each bin.


## 6.1. OPRF-Based PMT Protocol

PMT protocol involves two parties:Alice who holds an element x and Bob who holds a set Y. After PMT, Bob knows nothing about x, and Alice only knows whether her element x belongs to the set Y or not.Based on OPRF, we can construct PMT protocol as follows. First, during the OPRF phase,Bob acts as sender with a random seed s. And Alice, acting as receiver, inputs her element x. After OPRF, Alice obtains fsx and Bob has fs·. Then, Bob sends all fsyi to Alice who compares fsx with fsyi one by one. In conclusion, Alice outputs 1 if and only if there exits an i such that fsyi=fsx and else outputs 0.The security of PMT via OPRF relies on the fact that an OPRF protocol is secure. In a secure OPRF, it guarantees thatfs· is a one-way pseudorandom function and the length of s equals to secure parameter. Therefore, Alice receives fsyi and then learns whether there exists an i such that fsyi=fsx, but she will not learn the exact values yi|yi∈Y,fsyi≠fsx with nonnegligible probability. We omit concrete security proof here.


## 6.2.OTex-Based PMT Protocol

Given functionalityℱOPRF, we can construct PMT protocol in a simple manner. In this section, we introduce how to design OPRF protocol based on OTex. Equation (7) indicates that 1-out-of-n OT extension implies BaRK-OPRF; therefore, we focus on the transformation from 1-out-of-n OT extension to OTex. As a result, OTex can be easily used to construct PMT protocol.We can apply pseudorandom code to equation (8) for defining new relationship among T2 and T2′ in Figure 6, which implements functionality ℱOPRF in Figure 3. In OTex, however, we stress that it always holds T1i⊕T1′i=f1r2i and T2j⊕T2′j=f1r3j, where f1· is the repetition code. This means that we implement INKP protocol in an outsourced manner since we use the same repetition code f1· in FOTk1,k2 and FOTk2,k3. That is to say, three parties, S, S, and ℛ, evaluate corporately m instances of 1-out-of-2 OT of l-bit messages where repetition code is used twice in total, each by S and ℛ, respectively. Now, suppose Alice and Bob would like to execute m instances of 1-out-of-n OT where Bob inputs y1j,y2j,…,ynj|j∈m,yij=l and Alice inputs her selection vector r3, and they need make the following adjustments:(i)
Bob organizes the inputs in OTex with m×l matrices T31,T32,…,T3n, where the j-th row of matrix T3i is yij.(ii)
Alice makes her selection vector in OTex be r3|j∈m,r3j∈n.Then, the only adaption they need take inOTex is that T2j⊕T2′j=f2r3j, where f2· is the linear error correcting code C. To reach the security requirement defined in [13], in OTex, we need to reset security parameter k rather than κ—concretely 3κ<k<4κ.Given 1-out-of-n OT protocol designed from OTex, it is trivial to design OTex-based OPRF so is to OTex-based PMT. Again, Alice prepares her element x=r31, while Bob holds set Y=y11,y21,…,yn1. In brief, if it holds in OTex that(19)T1i⊕T1′i=f1r2i,T2j⊕T2′j=Cr3j,where f1· is the repetition code and C is the pseudorandom code; OTex implies the functionality ℱOPRF where the seed s consists of V2,r2 generated by Bob and Alice gets fsx. Meanwhile, this essentially completes the main construction of OTex-based PMT protocol. All needed to do next is that Bob sends fsyi1|i∈n to Alice who compares fsx with fsyi1|i∈n locally.


## 6.3.OTex-Based PSI Protocol

To obtain the final PSI protocol that computesX∩Y, Alice simply invokes the PMT protocol for each xi∈X. The protocol in Figure 12 computes X∩Y in an outsourced manner. The intuition is that Alice holds a set X, while Bob holds Y, and after PMT, Alice knows whether her element xi belongs to Y or not, i.e., the intersection of two sets.Figure 12
Outsourced private set intersection protocol.Some details on method of preprocessing items in set are simply omitted in Figure12. We can hash the item to bins and then operate the OTex-based PSI protocol on each bin separately. Specifically, we use Cuckoo hashing [35] for PSI in the following way. First, Alice and Bob agree on 3 random hash functions h1,h2,h3:0,1∗⟶m′ suitable for 3-way Cuckoo hashing. Alice places her items into m in either h1x, h2x, or h3x, and each bin contains at most one item. Bob places each of his items y in locations h1y, h2y, and h3y. At this point, Alice pads her input with dummy items so that each bin contains exactly 1 item. Note that when we use cuckoo hashing, then there will be some items which cannot be placed into the table and have to be moved to a stash, which does not matter because of the usage of stash-less cuckoo hashing [20]. Finally, Alice and Bob perform a PSI in each bin.


## 7. Conclusions and Future Work

In this paper, we proposed a generic outsourced OT extension protocol (OTex) which can outsource all the “base” OT from the sender to a semihonest server. The proposed protocol realizes optimal computational and communication complexity relative to security parameter. In addition, we showed that OTex can be efficiently used in private membership test and private set intersection. In the future, we will consider malicious model and construct efficient outsourced OT extension protocols secure against malicious adversary.



---

*Source: 8847487-2020-12-05.xml*