# Efficient Private Set Intersection Using Point-Value Polynomial Representation

Authors: Ou Ruan; Hao Mao
Journal: Security and Communication Networks
 (2020)

---

## Abstract

Private set intersection (PSI) allows participants to securely compute the intersection of their inputs, which has a wide range of applications such as privacy-preserving contact tracing of COVID-19. Most existing PSI protocols were based on asymmetric/symmetric cryptosystem. Therefore, keys-related operations would burden these systems. In this paper, we transform the problem of the intersection of sets into the problem of finding roots of polynomials by using point-value polynomial representation, blind polynomials’ point-value pairs for secure transportation and computation with the pseudorandom function, and then propose an efficient PSI protocol without any cryptosystem. We optimize the protocol based on the permutation-based hash technique which divides a set into multisubsets to reduce the degree of the polynomial. The following advantages can be seen from the experimental result and theoretical analysis: (1) there is no cryptosystem for data hiding or encrypting and, thus, our design provides a lightweight system; (2) with set elements less than212, our protocol is highly efficient compared to the related protocols; and (3) a detailed formal proof is given in the semihonest model.


---

## Body

## 1. Introduction

Private set intersection (PSI) can be described that participants complete computation based on their private inputs and cannot learn additional information other than the set intersection. PSI has a wide range of applications such as privacy-preserving contact tracing for infection detection [1, 2], private contact discovery [3], similar document detection [4], suspects detection [5], relationship path discovery in social networks [6], and satellite collisions matching [7].PSI has been well studied. Several cryptographic technologies have been proposed to implement PSI. According to cryptographic techniques involved, PSI protocols are mainly divided into the following three categories:(1)
PSI based on the public-key technology: the main cryptographic technique was homomorphic encryption. The protocols were designed in such a way that the sender encrypted sets and the receiver performed some operations on the ciphertexts using the property of homomorphic encryption; then, the sender decrypted them by using his private key and got the intersection. With small communication complexity, these protocols were suitable for the scenario where the participants had strong computing power but the communication bandwidth was a bottleneck. However, the protocols had a higher time complexity because of using public-key cryptography.(2)
PSI based on the generic circuit: the protocols transformed any function into garbled Boolean circuit and then completed the generic secure computation. The circuit generator encrypted each circuit gate using a double symmetric cryptosystem and generated a garbled circuit; the evaluator computed keys for the output wires by decrypting the appropriate ciphertexts without learning any intermediate values. The key technique used in the protocols was symmetric cryptosystem. The advantage of the general circuit protocol was that it made the protocol easier to design and implement. But as a general solution, the garbled circuit could not achieve scalability, and the protocols were inefficient.(3)
PSI based on the oblivious transfer (OT) scheme: this kind of protocols introduced some variants of OT. The protocols were that elements were stored in some data structures, and parties ran an OT for each bit of inputs to get private outputs. Then, each party performed XOR operations with random values and its own elements. Lastly, the sender sent the results to the receiver, who locally checked the existence of its inputs. To improve efficiency, most of OT variants were implemented by using the symmetric cryptosystem. Thus, these protocols had lower time complexity and communication complexity. Nevertheless, such protocols required additional keys-related computations such as secret key negotiations.From the above analysis, PSI protocols based on public-key cryptosystem suffer from two constraints: low efficiency and needing a complicated system for private/public-keys management. On the other hand, PSI protocols based on symmetric cryptosystem have higher efficiency, but negotiating or secure transferring of secret keys leads to additional computations and communications. Furthermore, the secure storage of keys will burden the system. In the paper, we transform the problem of the intersection of sets into the problem of finding the roots of polynomials by using point-value polynomial representation and propose an efficient PSI protocol without any cryptosystem.


### 1.1. Application Scenarios

Our work can be applied to the following several practical scenarios.


#### 1.1.1. Contact Tracing for Infection Detection

The COVID-19 pandemic has posed an unprecedented challenge for humans. Due to the highly contagious nature of the virus, social distancing is one fundamental measure that has already been adopted by many countries. Based on the matching of location information between infected patients and regular people, contact tracing for infection detection enables users to securely upload their data to the server, and later, in case one user got infected, other users can check if they had ever got in contact with the infected user in the past. To protect users’ private location information, PSI can be applied to securely compute shared location data.


#### 1.1.2. Suspects Detection

Two national law enforcement bodies have a list of suspected terrorists. Due to national laws, they may not be allowed to disclose their whole lists, even when collaborating. Using a PSI protocol, both agencies can find commonly suspected terrorists and share their information, while other relevant information will not be disclosed.


#### 1.1.3. Satellite Collisions

Different space agencies have their own orbiting satellites. In order to determine the collision problem of the same orbiting satellite pair and adjust the orbit of the satellite appropriately, these agencies need to share more detailed information. However, each agency does not want to disclose anything other than whether there was a collision in orbital information. Thus, it is necessary to use PSI for computing the probability of a collision among satellites without revealing their other private information.


### 1.2. Contributions

We transform the problem of the intersection of sets into the problem of finding roots of polynomials by using point-value polynomial representation and propose a new approach to PSI protocol without any cryptosystem. Then, we optimize our protocol based on the permutation-based hashing technique that reduces the length of the stored elements and the degree of the polynomial. Eventually, our protocol and the related PSI protocols are implemented on the Linux platform. The main contributions are as follows.


#### 1.2.1. A New Approach to PSI Protocol

We propose a new approach for designing PSI protocol based on point-value polynomial representation and pseudorandom function. Firstly, we represent sets as polynomials’ point-value pairs. Each party denotesd elements s1,…,sd as a d-degree polynomial ρx=∏i=1dx−si and represents ρx as n distinct point-value pairs x1,ρx1,…,xn,ρxn where n>d. Secondly, we blind polynomials’ point-value pairs for secure transportation and computation. Each party blinds them as x1,ρx1+z1,…,xn,ρxn+zn by using pseudorandom function and exchanges the blinded point-value pairs. Thirdly, we compute the sum of two blinded polynomials’ point-value pairs. Through computation and transportation, one party can get the sum of two blinded polynomials’ point-value pairs. Lastly, we can learn the polynomial by interpolation and get the intersection by computing the roots of the polynomial. With this representation, we could get the set intersection without any cryptosystem.


#### 1.2.2. Efficient Hashing PSI Protocol

We optimize the new PSI protocol using the permutation-based hashing method, which converts the hashed elements into shorter strings without collisions and reduces the degree of polynomials. The hashing is to create a two-dimensional tableHTbmaxb and map each element to its hashed bins, resulting in b⋅maxb stored elements, which split an n-degree polynomial into b⋅maxb-degree polynomials. This approach improves efficiency remarkably.


#### 1.2.3. Implementation of Our Hashing PSI Protocol

We implement our hashing protocol and other related protocols in C/C++ on the Linux platform. We use Number Theory Library (NTL) [8] along with GNU Multiprecision (GMP) library [9] for polynomial arithmetic. Based on the detailed experimental data, we conclude that our protocol is more efficient than public-key-based and circuit-based PSI protocols and is more efficient than OT-based PSI protocols at set elements less than 212.


### 1.3. Organizational Structure

The related works on PSI protocols are introduced in Section2. In Section 3, polynomial representation, hash technique, and security definition are given. In Section 4, a new approach to PSI protocol without any cryptosystem is shown. In Section 5, an optimized PSI protocol with the permutation-based hashing method is proposed. Implementation and performance analysis are presented in Section 6. Finally, conclusion and future work are provided in Section 7.


## 1.1. Application Scenarios

Our work can be applied to the following several practical scenarios.


### 1.1.1. Contact Tracing for Infection Detection

The COVID-19 pandemic has posed an unprecedented challenge for humans. Due to the highly contagious nature of the virus, social distancing is one fundamental measure that has already been adopted by many countries. Based on the matching of location information between infected patients and regular people, contact tracing for infection detection enables users to securely upload their data to the server, and later, in case one user got infected, other users can check if they had ever got in contact with the infected user in the past. To protect users’ private location information, PSI can be applied to securely compute shared location data.


### 1.1.2. Suspects Detection

Two national law enforcement bodies have a list of suspected terrorists. Due to national laws, they may not be allowed to disclose their whole lists, even when collaborating. Using a PSI protocol, both agencies can find commonly suspected terrorists and share their information, while other relevant information will not be disclosed.


### 1.1.3. Satellite Collisions

Different space agencies have their own orbiting satellites. In order to determine the collision problem of the same orbiting satellite pair and adjust the orbit of the satellite appropriately, these agencies need to share more detailed information. However, each agency does not want to disclose anything other than whether there was a collision in orbital information. Thus, it is necessary to use PSI for computing the probability of a collision among satellites without revealing their other private information.


## 1.1.1. Contact Tracing for Infection Detection

The COVID-19 pandemic has posed an unprecedented challenge for humans. Due to the highly contagious nature of the virus, social distancing is one fundamental measure that has already been adopted by many countries. Based on the matching of location information between infected patients and regular people, contact tracing for infection detection enables users to securely upload their data to the server, and later, in case one user got infected, other users can check if they had ever got in contact with the infected user in the past. To protect users’ private location information, PSI can be applied to securely compute shared location data.


## 1.1.2. Suspects Detection

Two national law enforcement bodies have a list of suspected terrorists. Due to national laws, they may not be allowed to disclose their whole lists, even when collaborating. Using a PSI protocol, both agencies can find commonly suspected terrorists and share their information, while other relevant information will not be disclosed.


## 1.1.3. Satellite Collisions

Different space agencies have their own orbiting satellites. In order to determine the collision problem of the same orbiting satellite pair and adjust the orbit of the satellite appropriately, these agencies need to share more detailed information. However, each agency does not want to disclose anything other than whether there was a collision in orbital information. Thus, it is necessary to use PSI for computing the probability of a collision among satellites without revealing their other private information.


## 1.2. Contributions

We transform the problem of the intersection of sets into the problem of finding roots of polynomials by using point-value polynomial representation and propose a new approach to PSI protocol without any cryptosystem. Then, we optimize our protocol based on the permutation-based hashing technique that reduces the length of the stored elements and the degree of the polynomial. Eventually, our protocol and the related PSI protocols are implemented on the Linux platform. The main contributions are as follows.


### 1.2.1. A New Approach to PSI Protocol

We propose a new approach for designing PSI protocol based on point-value polynomial representation and pseudorandom function. Firstly, we represent sets as polynomials’ point-value pairs. Each party denotesd elements s1,…,sd as a d-degree polynomial ρx=∏i=1dx−si and represents ρx as n distinct point-value pairs x1,ρx1,…,xn,ρxn where n>d. Secondly, we blind polynomials’ point-value pairs for secure transportation and computation. Each party blinds them as x1,ρx1+z1,…,xn,ρxn+zn by using pseudorandom function and exchanges the blinded point-value pairs. Thirdly, we compute the sum of two blinded polynomials’ point-value pairs. Through computation and transportation, one party can get the sum of two blinded polynomials’ point-value pairs. Lastly, we can learn the polynomial by interpolation and get the intersection by computing the roots of the polynomial. With this representation, we could get the set intersection without any cryptosystem.


### 1.2.2. Efficient Hashing PSI Protocol

We optimize the new PSI protocol using the permutation-based hashing method, which converts the hashed elements into shorter strings without collisions and reduces the degree of polynomials. The hashing is to create a two-dimensional tableHTbmaxb and map each element to its hashed bins, resulting in b⋅maxb stored elements, which split an n-degree polynomial into b⋅maxb-degree polynomials. This approach improves efficiency remarkably.


### 1.2.3. Implementation of Our Hashing PSI Protocol

We implement our hashing protocol and other related protocols in C/C++ on the Linux platform. We use Number Theory Library (NTL) [8] along with GNU Multiprecision (GMP) library [9] for polynomial arithmetic. Based on the detailed experimental data, we conclude that our protocol is more efficient than public-key-based and circuit-based PSI protocols and is more efficient than OT-based PSI protocols at set elements less than 212.


## 1.2.1. A New Approach to PSI Protocol

We propose a new approach for designing PSI protocol based on point-value polynomial representation and pseudorandom function. Firstly, we represent sets as polynomials’ point-value pairs. Each party denotesd elements s1,…,sd as a d-degree polynomial ρx=∏i=1dx−si and represents ρx as n distinct point-value pairs x1,ρx1,…,xn,ρxn where n>d. Secondly, we blind polynomials’ point-value pairs for secure transportation and computation. Each party blinds them as x1,ρx1+z1,…,xn,ρxn+zn by using pseudorandom function and exchanges the blinded point-value pairs. Thirdly, we compute the sum of two blinded polynomials’ point-value pairs. Through computation and transportation, one party can get the sum of two blinded polynomials’ point-value pairs. Lastly, we can learn the polynomial by interpolation and get the intersection by computing the roots of the polynomial. With this representation, we could get the set intersection without any cryptosystem.


## 1.2.2. Efficient Hashing PSI Protocol

We optimize the new PSI protocol using the permutation-based hashing method, which converts the hashed elements into shorter strings without collisions and reduces the degree of polynomials. The hashing is to create a two-dimensional tableHTbmaxb and map each element to its hashed bins, resulting in b⋅maxb stored elements, which split an n-degree polynomial into b⋅maxb-degree polynomials. This approach improves efficiency remarkably.


## 1.2.3. Implementation of Our Hashing PSI Protocol

We implement our hashing protocol and other related protocols in C/C++ on the Linux platform. We use Number Theory Library (NTL) [8] along with GNU Multiprecision (GMP) library [9] for polynomial arithmetic. Based on the detailed experimental data, we conclude that our protocol is more efficient than public-key-based and circuit-based PSI protocols and is more efficient than OT-based PSI protocols at set elements less than 212.


## 1.3. Organizational Structure

The related works on PSI protocols are introduced in Section2. In Section 3, polynomial representation, hash technique, and security definition are given. In Section 4, a new approach to PSI protocol without any cryptosystem is shown. In Section 5, an optimized PSI protocol with the permutation-based hashing method is proposed. Implementation and performance analysis are presented in Section 6. Finally, conclusion and future work are provided in Section 7.


## 2. Related Work

According to the underlying cryptographic techniques, PSI protocols can be divided into the following three categories.


### 2.1. PSI Based on the Public-Key

In 1986, Meadows [10] introduced a PSI protocol that could solve the problem of authentication of mutually suspicious parties. But, they revealed the cardinality of sets during the authentication. To solve this problem, an improved PSI protocol [11] was proposed.The PSI protocol based on oblivious polynomial evaluation [12] was proposed in 2004, which used the homomorphic encryption, balanced hashing, and properties of polynomials. They represented its elements as roots of polynomials and used interpolation to find out the coefficients of polynomials and sent the ciphertexts of coefficients of polynomials to the server by using ElGamal [13] or Pailler [14] encryption. In this protocol, it would lead to a high cost of exponential calculation in homomorphic encryption if the degree of the polynomial was large. An extended version [15] was presented, where the client and the server used the cuckoo hashing technique to reduce its computational complexity.In 2009, Jarecki et al. [16] showed a PSI protocol based on the composite residual hypothesis. The protocol used additive homomorphic and zero-knowledge proof to realize the pseudorandom function and then performed the intersection operation on the random values of the set. The client and the server carried on the parallel oblivious pseudorandom function (OPRF) to get the intersection. However, the protocol relied on the common reference model.In 2010, Cristofaro et al. proposed PSI and Authorized PSI (APSI) protocols [17, 18]. But, these PSI protocols revealed the client’s set cardinality. To hide the client’s set cardinality, Ateniese et al. [19] presented a PSI protocol that was to batch the hash value of the client. In 2012, Cristofaro et al. [20] used RSA and OPRF techniques to reduce the total cost of cryptographic operations based on Cristofaro et al.’s constructions [17, 18].In 2017, Chen et al. [21] gave a PSI protocol with a low communication complexity based on the fully homomorphic encryption technology. In 2018, Chen et al. [22] implemented an unbalanced labeled PSI protocol against malicious adversaries by using OPRF into a preprocessing phase.


### 2.2. PSI Based on the Generic Circuit

The two main approaches were Yao’s garbled circuits [23, 24] and Goldreich protocol [25], which were to replace arbitrary functions with Boolean circuit computations. The communication overhead and the number of cryptographic operations depended on nonlinear gates’ number in the circuit. Thus, compared with the most special-purpose PSI protocols, the running time and communication complexity became more prominent problems for PSI protocols based on generic secure computation.In 2012, Huang et al. [26] proposed several Boolean circuits for PSI protocols and evaluated based on Yao’s circuit, which used homomorphic encryption and adopted various circuit optimization techniques. The main method was that the client and the server sorted the elements in their sets locally and merged them in order through the garbled circuit and determined the equality of adjacent elements in the merged set. If they were equal, they would be the elements in the intersection. In 2015, Pinkas et al. [27] presented a circuit-phasing PSI protocol, which was up to 5 times faster than [26].In 2018, Pinkas et al. [28] used a two-dimensional cuckoo hashing technique to realize a PSI based on the generic circuit, where it was asymptotically with better efficiency and could be extended to multiparties. For the general assumption of linear communication, Hemenway et al. [29], based on Pinkas et al.’s construction [27], represented a simple and generic circuit-based PSI protocol in 2019.


### 2.3. PSI Based on the Oblivious Transfer (OT) Scheme

In 2001, Naor et al. [30] proposed an OT protocol with asymmetric cryptographic operations, which spent expensive public-key operations when performing OT. Huberman et al. [11] used OT extensions (OTs) technology [31] to reduce expensive public-key operations by using more efficient symmetric cryptographic operations.In 2013, Dong et al. [32] showed a PSI protocol that could process elements up to a size of 100 million. This protocol was based on bloom filter (BF), garbled bloom filter (GBF), secret sharing, and OTs. The linear complexity and high scalability of the protocol came from the effective symmetric cryptosystem and parallel processing, respectively. But, there was a problem with this protocol that the server might cause a selective failure to terminate the protocol in the malicious setting when the client performed a specific input. Thus, Rindal et al. [33] brought up an efficient fix using the cut-and-choose approach. Based on the method [30], Pinkas et al. [34] optimized it by replacing OTs with random OT, which did not need to save the GBF structure, but let the server and the client generate BF structure as the input of OT.In 2015, Pinkas et al. [27] applied the phase and permutation hashing methods, which resulted in a reduction of computation and memory. Kolesnikov et al. [35] improved Pinkas et al.’s construction based on efficient OPRF. Subsequently, Kolesnikov et al. [36] proposed an extended version based on the literature [35], which gave a lightweight protocol. Rindal et al. [33] gave the first implementation of PSI protocol against malicious adversaries. In 2018, Pinkas et al. [3] analyzed the current exiting protocols in detail and optimized PSI protocol using OPRF and the hashing techniques. A new PSI protocol was constructed by Pinkas et al. [37] in 2019, which used the 2-choice hashing [38], sparse OT extension, and the polynomial slice and stream techniques to reduce the communication cost and improve the efficiency of the protocol. In 2020, Pinkas et al. [39] proposed a PSI protocol based on a probe-and-XOR of strings (PaXoS) data structure, which not only had linear communication and computational complexity, but also can safely resist the malicious adversary in a nonprogrammable random oracle.


## 2.1. PSI Based on the Public-Key

In 1986, Meadows [10] introduced a PSI protocol that could solve the problem of authentication of mutually suspicious parties. But, they revealed the cardinality of sets during the authentication. To solve this problem, an improved PSI protocol [11] was proposed.The PSI protocol based on oblivious polynomial evaluation [12] was proposed in 2004, which used the homomorphic encryption, balanced hashing, and properties of polynomials. They represented its elements as roots of polynomials and used interpolation to find out the coefficients of polynomials and sent the ciphertexts of coefficients of polynomials to the server by using ElGamal [13] or Pailler [14] encryption. In this protocol, it would lead to a high cost of exponential calculation in homomorphic encryption if the degree of the polynomial was large. An extended version [15] was presented, where the client and the server used the cuckoo hashing technique to reduce its computational complexity.In 2009, Jarecki et al. [16] showed a PSI protocol based on the composite residual hypothesis. The protocol used additive homomorphic and zero-knowledge proof to realize the pseudorandom function and then performed the intersection operation on the random values of the set. The client and the server carried on the parallel oblivious pseudorandom function (OPRF) to get the intersection. However, the protocol relied on the common reference model.In 2010, Cristofaro et al. proposed PSI and Authorized PSI (APSI) protocols [17, 18]. But, these PSI protocols revealed the client’s set cardinality. To hide the client’s set cardinality, Ateniese et al. [19] presented a PSI protocol that was to batch the hash value of the client. In 2012, Cristofaro et al. [20] used RSA and OPRF techniques to reduce the total cost of cryptographic operations based on Cristofaro et al.’s constructions [17, 18].In 2017, Chen et al. [21] gave a PSI protocol with a low communication complexity based on the fully homomorphic encryption technology. In 2018, Chen et al. [22] implemented an unbalanced labeled PSI protocol against malicious adversaries by using OPRF into a preprocessing phase.


## 2.2. PSI Based on the Generic Circuit

The two main approaches were Yao’s garbled circuits [23, 24] and Goldreich protocol [25], which were to replace arbitrary functions with Boolean circuit computations. The communication overhead and the number of cryptographic operations depended on nonlinear gates’ number in the circuit. Thus, compared with the most special-purpose PSI protocols, the running time and communication complexity became more prominent problems for PSI protocols based on generic secure computation.In 2012, Huang et al. [26] proposed several Boolean circuits for PSI protocols and evaluated based on Yao’s circuit, which used homomorphic encryption and adopted various circuit optimization techniques. The main method was that the client and the server sorted the elements in their sets locally and merged them in order through the garbled circuit and determined the equality of adjacent elements in the merged set. If they were equal, they would be the elements in the intersection. In 2015, Pinkas et al. [27] presented a circuit-phasing PSI protocol, which was up to 5 times faster than [26].In 2018, Pinkas et al. [28] used a two-dimensional cuckoo hashing technique to realize a PSI based on the generic circuit, where it was asymptotically with better efficiency and could be extended to multiparties. For the general assumption of linear communication, Hemenway et al. [29], based on Pinkas et al.’s construction [27], represented a simple and generic circuit-based PSI protocol in 2019.


## 2.3. PSI Based on the Oblivious Transfer (OT) Scheme

In 2001, Naor et al. [30] proposed an OT protocol with asymmetric cryptographic operations, which spent expensive public-key operations when performing OT. Huberman et al. [11] used OT extensions (OTs) technology [31] to reduce expensive public-key operations by using more efficient symmetric cryptographic operations.In 2013, Dong et al. [32] showed a PSI protocol that could process elements up to a size of 100 million. This protocol was based on bloom filter (BF), garbled bloom filter (GBF), secret sharing, and OTs. The linear complexity and high scalability of the protocol came from the effective symmetric cryptosystem and parallel processing, respectively. But, there was a problem with this protocol that the server might cause a selective failure to terminate the protocol in the malicious setting when the client performed a specific input. Thus, Rindal et al. [33] brought up an efficient fix using the cut-and-choose approach. Based on the method [30], Pinkas et al. [34] optimized it by replacing OTs with random OT, which did not need to save the GBF structure, but let the server and the client generate BF structure as the input of OT.In 2015, Pinkas et al. [27] applied the phase and permutation hashing methods, which resulted in a reduction of computation and memory. Kolesnikov et al. [35] improved Pinkas et al.’s construction based on efficient OPRF. Subsequently, Kolesnikov et al. [36] proposed an extended version based on the literature [35], which gave a lightweight protocol. Rindal et al. [33] gave the first implementation of PSI protocol against malicious adversaries. In 2018, Pinkas et al. [3] analyzed the current exiting protocols in detail and optimized PSI protocol using OPRF and the hashing techniques. A new PSI protocol was constructed by Pinkas et al. [37] in 2019, which used the 2-choice hashing [38], sparse OT extension, and the polynomial slice and stream techniques to reduce the communication cost and improve the efficiency of the protocol. In 2020, Pinkas et al. [39] proposed a PSI protocol based on a probe-and-XOR of strings (PaXoS) data structure, which not only had linear communication and computational complexity, but also can safely resist the malicious adversary in a nonprogrammable random oracle.


## 3. Preliminaries

### 3.1. Representing Set with Polynomial Point-Value Pairs

We give the transformation from operations of sets to operations of polynomials. This representation allows us to represent a set using a random point evaluation polynomial.Definition 1.
Polynomial representation of a set. Given a setS=s1,…,sd, whose set cardinality is d; then, we define its characteristic polynomial as(1)ρx=∏i=1dx−si,and thus every element si∈S for 1≤i≤d is a root of ρx.Definition 2.
Polynomial in point-value pairs: distinct point-value pairsx1,y1,…,xn,yn can represent a degree d polynomial ρx=∏i=1dx−si, where yj=ρxj for 1≤j≤n,n>d. If x⟶ is fixed, the vector y⟶=y1,…,yn represents the polynomial ρx.Definition 3.
Set intersection: letSA and SB be two sets with the same degree d and represented as polynomials ρAx and ρBx, respectively. Then, the intersection SA∩SB could be learnt by finding the roots of the following polynomial:(2)ρAx⋅γBx+ρBx⋅γAx,where γAx and γBx are d-degree polynomials, γAx=∏i=1dx−riA and γBx=∏i=1dx−riB, and riA and riB are random values picked uniformly.


### 3.2. Hashing Techniques

#### 3.2.1. The Simple Hashing

The simple hashing maps each elementx to its hashed positions. In particular, when hashing an element x, it stores x in the bin HTHx, where H is a random function: 0,1∗↦1,b. To contain the multiple elements, HT will be denoted as a double array HTimaxb for 1≤i≤b. The insert function of simple hashing can be described as(3)for each elementxdo,ifHTHx⋅length≤maxb,x⟶HTHx,where maxb is introduced to represent the maximum number of each bin of hash table.


#### 3.2.2. Permutation-Based Hashing

Permutation-based hashing technique is to allow the hashed elements to be converted shorter strings that can be stored in the hash table for reducing storage space and computation complexity, which was proposed by Arbitman et al. [40]. Originally, an element x=xLxR is represented as bits, where xL=logb, b is the bins’ size in the hash table. Then, the element x gets the index, xL⊕HxR, where H is a random function: 0,1∗↦1,b. Finally, the value stored in the bin is xR, xR=x−xL. Thus, the stored data’s length is significantly reduced and efficiency will be improved.


### 3.3. Security Definitions

This section focuses on the security definition of PSI protocol.


#### 3.3.1. Adversary

We consider a semihonest adversary who follows the protocol specifications while trying to obtain extra information from the exchanging messages.


#### 3.3.2. Functionality

The functionality being implemented in this paper isf∩SA,SB=SA∩SB,⊥, that is, two parties; A has a set SA=s1A,…,sdA and gets the intersection, and B has a set SB=s1B,…,sdB but does not learn any output.Definition 4.
Semihonest security: in the semihonest model, a protocolπ is secure if each party does not get any information other than his input and output. This is formalized by the simulation paradigm. The view of the party U during the execution of protocol π on input tuple SA,SB is denoted by viewUπSA,SB that includes his input and output, internal random coins, and messages exchanged. We say that π privately computes f∩ if there exist polynomial-time simulation algorithms, denoted as SimA and SimB, such that(4)veiwAπSA,SB≡cSimASA,f∩SA,SB,veiwBπSA,SB≡cSimBSB,⊥.where “≡” represents two views that are computationally indistinguishable.


## 3.1. Representing Set with Polynomial Point-Value Pairs

We give the transformation from operations of sets to operations of polynomials. This representation allows us to represent a set using a random point evaluation polynomial.Definition 1.
Polynomial representation of a set. Given a setS=s1,…,sd, whose set cardinality is d; then, we define its characteristic polynomial as(1)ρx=∏i=1dx−si,and thus every element si∈S for 1≤i≤d is a root of ρx.Definition 2.
Polynomial in point-value pairs: distinct point-value pairsx1,y1,…,xn,yn can represent a degree d polynomial ρx=∏i=1dx−si, where yj=ρxj for 1≤j≤n,n>d. If x⟶ is fixed, the vector y⟶=y1,…,yn represents the polynomial ρx.Definition 3.
Set intersection: letSA and SB be two sets with the same degree d and represented as polynomials ρAx and ρBx, respectively. Then, the intersection SA∩SB could be learnt by finding the roots of the following polynomial:(2)ρAx⋅γBx+ρBx⋅γAx,where γAx and γBx are d-degree polynomials, γAx=∏i=1dx−riA and γBx=∏i=1dx−riB, and riA and riB are random values picked uniformly.


## 3.2. Hashing Techniques

### 3.2.1. The Simple Hashing

The simple hashing maps each elementx to its hashed positions. In particular, when hashing an element x, it stores x in the bin HTHx, where H is a random function: 0,1∗↦1,b. To contain the multiple elements, HT will be denoted as a double array HTimaxb for 1≤i≤b. The insert function of simple hashing can be described as(3)for each elementxdo,ifHTHx⋅length≤maxb,x⟶HTHx,where maxb is introduced to represent the maximum number of each bin of hash table.


### 3.2.2. Permutation-Based Hashing

Permutation-based hashing technique is to allow the hashed elements to be converted shorter strings that can be stored in the hash table for reducing storage space and computation complexity, which was proposed by Arbitman et al. [40]. Originally, an element x=xLxR is represented as bits, where xL=logb, b is the bins’ size in the hash table. Then, the element x gets the index, xL⊕HxR, where H is a random function: 0,1∗↦1,b. Finally, the value stored in the bin is xR, xR=x−xL. Thus, the stored data’s length is significantly reduced and efficiency will be improved.


## 3.2.1. The Simple Hashing

The simple hashing maps each elementx to its hashed positions. In particular, when hashing an element x, it stores x in the bin HTHx, where H is a random function: 0,1∗↦1,b. To contain the multiple elements, HT will be denoted as a double array HTimaxb for 1≤i≤b. The insert function of simple hashing can be described as(3)for each elementxdo,ifHTHx⋅length≤maxb,x⟶HTHx,where maxb is introduced to represent the maximum number of each bin of hash table.


## 3.2.2. Permutation-Based Hashing

Permutation-based hashing technique is to allow the hashed elements to be converted shorter strings that can be stored in the hash table for reducing storage space and computation complexity, which was proposed by Arbitman et al. [40]. Originally, an element x=xLxR is represented as bits, where xL=logb, b is the bins’ size in the hash table. Then, the element x gets the index, xL⊕HxR, where H is a random function: 0,1∗↦1,b. Finally, the value stored in the bin is xR, xR=x−xL. Thus, the stored data’s length is significantly reduced and efficiency will be improved.


## 3.3. Security Definitions

This section focuses on the security definition of PSI protocol.


### 3.3.1. Adversary

We consider a semihonest adversary who follows the protocol specifications while trying to obtain extra information from the exchanging messages.


### 3.3.2. Functionality

The functionality being implemented in this paper isf∩SA,SB=SA∩SB,⊥, that is, two parties; A has a set SA=s1A,…,sdA and gets the intersection, and B has a set SB=s1B,…,sdB but does not learn any output.Definition 4.
Semihonest security: in the semihonest model, a protocolπ is secure if each party does not get any information other than his input and output. This is formalized by the simulation paradigm. The view of the party U during the execution of protocol π on input tuple SA,SB is denoted by viewUπSA,SB that includes his input and output, internal random coins, and messages exchanged. We say that π privately computes f∩ if there exist polynomial-time simulation algorithms, denoted as SimA and SimB, such that(4)veiwAπSA,SB≡cSimASA,f∩SA,SB,veiwBπSA,SB≡cSimBSB,⊥.where “≡” represents two views that are computationally indistinguishable.


## 3.3.1. Adversary

We consider a semihonest adversary who follows the protocol specifications while trying to obtain extra information from the exchanging messages.


## 3.3.2. Functionality

The functionality being implemented in this paper isf∩SA,SB=SA∩SB,⊥, that is, two parties; A has a set SA=s1A,…,sdA and gets the intersection, and B has a set SB=s1B,…,sdB but does not learn any output.Definition 4.
Semihonest security: in the semihonest model, a protocolπ is secure if each party does not get any information other than his input and output. This is formalized by the simulation paradigm. The view of the party U during the execution of protocol π on input tuple SA,SB is denoted by viewUπSA,SB that includes his input and output, internal random coins, and messages exchanged. We say that π privately computes f∩ if there exist polynomial-time simulation algorithms, denoted as SimA and SimB, such that(4)veiwAπSA,SB≡cSimASA,f∩SA,SB,veiwBπSA,SB≡cSimBSB,⊥.where “≡” represents two views that are computationally indistinguishable.


## 4. The New PSI Protocol Based on Point-Value Polynomial Representation

The functionality that is implemented in the new PSI protocol isf∩SA,SB=fSA∩SB,⊥. Let I∈A,B, SI=s1I,…,sdI, where SI=d. The new protocol is shown in Figure 1 and has the following four steps.(a)
Setup: partyA constructs a public finite field Fp where p is a large prime, a pseudorandom functionPRF:0,1∗×Zp⟶Fp that generates pseudorandom values in Fp, and a vector x⟶ with n=2d+1 distinct nonzero values picked randomly from Fp. Then, it publishes Fp, PRF, and x⟶.(b)
Initialization: each partyI performs the following steps:(1)
Select a dummy numbertkI and compute pseudorandom values riI=PRFtkI,i for 1≤i≤d and then generate random polynomial γIx=∏i=1dx−riI(2)
Construct polynomialρIx=∏i=1dx−siI(3)
Compute vectorsγ⟶I and ρ⟶I with values γIxj and ρIxj, respectively, for 1≤j≤n, which are used to represent polynomials γIx and ρIx(4)
Pick another random numbermkI and generate pseudorandom values zjI=PRFmkI,j for 1≤j≤n that are used to blind polynomial values(c)
Intersection interaction: partyA tries to get the sum of two blinded polynomials point-value pairs whose roots are the intersection with party B. To do so, the following computations will be performed.(1)
PartyA computes pj=γAxj+ρAxj⋅zjA for 1≤j≤n and sends the vector p⟶=p1,…,pn to party B.(2)
Receiving partyA′s message, party B blinds the vector ρ⟶Bas follows:(5)dj=ρBxj⋅zjB+γBxj,ej=ρBxj+γBxj⋅zjB.where1≤j≤n. Then, it gets the blinded vectors e⟶=e1,…,en and d⟶=d1,…,dnand sends them to party A.(3)
PartyA computes the blinded vector q⟶, whose elements qj for 1≤j≤n are computed as follows:(6)qj=ej⋅γAxj−ρAxj⋅dj⋅zjA.(4)
PartyB removes the blinding factors zjB for 1≤j≤n as follows:(7)cj=pj⋅oj+qj⋅zjB+1−1=ρBxj⋅γAxj−ρAxj⋅γBxj⋅zjA.Then, it sends the vectorc⟶ to party A.(d)
Intersection result: partyA gets set intersection.(1)
PartyA unblinds the blinding factors zjAfor 1≤j≤n as follows:(8)yj=cj⋅zjA−1=ρBxj⋅γAxj−ρAxj⋅γBxj.(2)
PartyA restores polynomials φx by using point-value pair interpolation xj,yj for 1≤j≤n.(3)
PartyA checks each element siA for 1≤i≤d whether it is a root of φx. If it holds, it is an element of intersection; otherwise it is not.Figure 1
A PSI Protocol based on point-value polynomial representation.


### 4.1. Correctness of the New Protocol

Because for1≤j≤n,(9)qj=ej⋅γAxj−ρAxj⋅dj⋅zjA=ρBxj+γBxj⋅zjB⋅γAxj⋅zjA−γBxj+ρBxj⋅zjB⋅ρAxj⋅zjA.Next,(10)cj=pj⋅oj+qj⋅1+zjB−1=ρAxj+γAxj⋅zjA⋅ρBxj−γBxj⋅zjB+ρBxj+γBxj⋅zjB⋅γAxj⋅zjA−γBxj+ρBxj⋅zjB⋅ρAxj⋅zjA⋅1+zjB−1=γAxj⋅ρBxj−γBxj⋅ρAxj⋅zjA⋅1+zjB⋅1+zjB−1=γAxj⋅ρBxj−γBxj⋅ρAxj⋅zjA.Then,(11)yj=cj⋅zjA−1=γAxj⋅ρBxj⋅zjA⋅zjA−1−γBxj⋅ρAxj⋅zjA⋅zjA−1=γAxj⋅ρBxj−γBxj⋅ρAxj.And we can get the polynomialφx by point-value pairs xj,yj for 1≤j≤n, where φx=γAx⋅ρBx−γBx⋅ρAx. From Definition 3, we can get the intersection by computing the roots of the polynomial φx.Thus, the new protocol is correct.


## 4.1. Correctness of the New Protocol

Because for1≤j≤n,(9)qj=ej⋅γAxj−ρAxj⋅dj⋅zjA=ρBxj+γBxj⋅zjB⋅γAxj⋅zjA−γBxj+ρBxj⋅zjB⋅ρAxj⋅zjA.Next,(10)cj=pj⋅oj+qj⋅1+zjB−1=ρAxj+γAxj⋅zjA⋅ρBxj−γBxj⋅zjB+ρBxj+γBxj⋅zjB⋅γAxj⋅zjA−γBxj+ρBxj⋅zjB⋅ρAxj⋅zjA⋅1+zjB−1=γAxj⋅ρBxj−γBxj⋅ρAxj⋅zjA⋅1+zjB⋅1+zjB−1=γAxj⋅ρBxj−γBxj⋅ρAxj⋅zjA.Then,(11)yj=cj⋅zjA−1=γAxj⋅ρBxj⋅zjA⋅zjA−1−γBxj⋅ρAxj⋅zjA⋅zjA−1=γAxj⋅ρBxj−γBxj⋅ρAxj.And we can get the polynomialφx by point-value pairs xj,yj for 1≤j≤n, where φx=γAx⋅ρBx−γBx⋅ρAx. From Definition 3, we can get the intersection by computing the roots of the polynomial φx.Thus, the new protocol is correct.


## 5. Efficient PSI Protocol Using Hashing

We optimize the above protocol using the permutation-based hashing. At first, each party constructs a two-dimensional hash tableHT, where the first dimension is the index of the hashed element and the second dimension stores the elements. Then, each party pads the second dimension with random values to the maximum load. The permutation-based hashing makes each party break down its original set into several small subsets. Thus, it will greatly reduce the degree of polynomials and then significantly improve the efficiency of the protocol. Let I∈A,B, SI=s1I,…,sdI, where SI=d. The hashing PSI protocol is shown in Figure 2, and the details include the following steps.(a)
Setup: partyA selects a permutation-based hashing function H with the parameters b and maxb for the hash table, where b is bins’ size in the hash table and maxb denotes the maximum length in a bin. Next, it constructs a public finite field Fp where p is a large prime, a pseudorandom function PRF:0,1∗×Zp⟶Fpthat generates pseudorandom values in Fp, and a vector x⟶ with n=2maxb+1 distinct nonzero values picked randomly from Fp. Then, it publishes H, b, maxb, Fp, x⟶, and PRF.(b)
Hashing: each partyI performs the following.(1)
Create a hash tableHTI by doing the following:(12)HsiI=j,siI⟶HTIj,for1≤i≤d.(2)
For every binHTIj1≤j≤b, get an array flagIj=HTIj.size that holds the size of the actual mapped elements. If its size is less than maxb, pick dummy elements, aj,tIflagIj+1≤t≤maxb, and pad them to the bin HTIj.(c)
Initialization: each partyI chooses a dummy quantity tkI, and for each bin, j1≤j≤b does the following.(1)
Generate a pseudorandom valuekjI by using tkI:(13)kjI=PRFtkI,j.(2)
Generatemaxb pseudorandom values and construct a random polynomial as follows:(14)rj,iI=PRFkjI,i,for1≤i≤maxb,γjIx=∏i=1maxbx−rj,iI.(3)
Construct a polynomialρjIx to represent the elements in the bin HTIj:(15)ρjIx=∏i=1maxbx−HTIji.(4)
Choose a random numbermkjI and get n pseudorandom values zj,tI that are used to blind the polynomial values:(16)zj,tI=PRFmkjI,t,for1≤t≤n.(5)
Compute vectorsγ⟶jI and ρ⟶jIwith values γjIxt and ρjIxt, respectively, for 1≤t≤n, which are used to represent polynomials γjIx and ρjIx.(d)
Intersection interaction: partyA tries to get the sum of two blinded polynomials point-value pairs whose roots are the intersection with party B. To do so, the following computation will be performed.(1)
PartyA computes pj,t=γjAxt+ρjAxt⋅zj,tA for 1≤j≤b and 1≤t≤n and sends the vector p⟶=p1⟶,…,pb⟶ to party B.(2)
Receiving partyA’s message, party B blinds every value as follows:(17)dj,t=ρjBxt⋅zj,tB+γjBxt,ej,t=ρjBxt+γjBxt⋅zj,tB,where1≤j≤b and 1≤t≤n. Then, it gets the blinded vectors e⟶=e1⟶,…,eb⟶ and d⟶=d1⟶,…,db⟶and sends them to party A.(3)
PartyA computes the blinded vector q⟶ as follows:(18)qj,t=ej,t⋅γjAxt−ρjAxt⋅dj,t⋅zj,tA,where1≤j≤b and 1≤t≤n. Then, it gets the blinded vectors q⟶=q1⟶,…,qb⟶ and sends them to party B.(4)
PartyB removes the blinding factors zj,tB as follows:(19)cj,t=pj,t⋅oj,t+qj,t⋅zj,tB+1−1=ρjBxt⋅γjAxt−ρjAxt⋅γjBxt⋅zj,tA,where1≤j≤b and 1≤t≤n. Then, it gets the vectors c⟶=c1⟶,…,cb⟶ and sends them to party A.(e)
Intersection result: for each binj1≤j≤b, party A restores the subpolynomial by the interpolation and gets the intersection by computing the roots of the subpolynomial.(1)
PartyA removes the blinding factors zj,tA for 1≤t≤n as follows:(20)yj,t=cj,t⋅zj,tA−1=ρjBxt⋅γjAxt−ρjAxt⋅γjBxt.(2)
PartyA restores the subpolynomial φjx by using the point-value pairs interpolation x⟶,yj⟶.(3)
PartyA finds the elements of the intersection SA∩SB by computing the roots of polynomial φjx as follows:(21)ifφjHTAji==0,HTAji∈SA∩SB,where 1≤i≤flagAj, flagAj denotes the size of the actual elements in bin j.Figure 2
Efficient PSI protocol using the permutation-based hashing.


### 5.1. Correctness of the Hashing Protocol

Because for1≤j≤b, 1≤t≤n,(22)qj,t=ej,t⋅γjAxt−ρjAxt⋅dj,t⋅zj,tA=ρjBxt+γjBxt⋅zj,tB⋅γjAxt⋅zj,tA−γjBxt+ρjBxt⋅zj,tB⋅ρjAxt⋅zj,tA.Next,(23)cj,t=pj,t⋅oj,t+qj,t⋅1+zj,tB−1=ρjAxt+γjAxt⋅zj,tA⋅ρjBxt−γjBxt⋅zj,tB+ρjBxt+γjBxt⋅zj,tB⋅γjAxt⋅zj,tA−γjBxt+ρjBxt⋅zj,tB⋅ρjAxt⋅zj,tA⋅1+zj,tB−1=γjAxt⋅ρjBxt−γjBxt⋅ρjAxt⋅zj,tA⋅1+zj,tB⋅1+zj,tB−1=γjAxt⋅ρjBxt−γjBxt⋅ρjAxt⋅zj,tA.Then,(24)yj,t=cj,t⋅zj,tA−1=γjAxt⋅ρjBxt⋅zj,tA⋅zj,tA−1−γjBxt⋅ρjAxt⋅zj,tA⋅zj,tA−1=γjAxt⋅ρjBxt−γjBxt⋅ρjAxt.And the polynomialsφjx are restored using the point-value pairs xj,yj,t, where φjx=γjAx⋅ρjBx−γjBx⋅ρjAx.. From Definition 3, the intersection SA∩SB could be learnt by finding roots of the polynomials φjx1≤j≤b.Thus, the hashing protocol is correct.


### 5.2. Security Proof

The above hashing PSI protocol is securely computing the set intersection in the presence of a semihonest adversary.Theorem 1.
IfPRF is a pseudorandom function, then the hashing PSI protocol π is secure in the presence of a semihonest adversary.Proof.
We prove it by considering the cases where each of parties has been corrupted. In each case, we will construct a simulator who is only given the corrupted party’s input/output and generates a simulated view that has to be computationally indistinguishable from the real protocol.Case 1.
Corrupted partyA: in the real protocol, party A′s view is(25)ViewAπSA,SB=SA,p⟶,d⟶,e⟶,q⟶,c⟶,f∩SA,SB.
The simulatorSimA is constructed and performs the following steps:(1)
Create an empty view and then appendSA and f∩SA,SB to it.(2)
Pick a setS′B with d elements at random such that SA∩S′B=f∩SA,SB.(3)
Construct polynomialsρj′Ax and ρj′Bx1≤j≤b representing sets SA and S′B, respectively. And generate random polynomials γj′Ax and γj′Bx for 1≤j≤b.(4)
Generate the Random Valueszj,t′A and zj,t′B for 1≤j≤b,1≤t≤n(5)
Blind the polynomials’ values and get random vectorsp⟶′, q⟶′, e⟶′, and d⟶′, where pj,t′, ej,t′, dj,t′, and qj,t′ (1≤j≤b, 1≤t≤n) are computed as follows:(26)pj,t′=γj′Axt+ρj′Axt⋅zj,t′A,dj,t′=ρj′Bxt⋅zj,t′B+γj′Bxt,ej,t′=ρj′Bxt+γj′Bxt⋅zj,t′B,qj,t′=ej,t′⋅γj′Axt−ρj′Axt⋅dj,t′⋅zj,t′A.(6)
Computecj,t′=ρj′Bxt⋅γj′Axt−ρj′Axt⋅γj′Bxt⋅zj,t′A for 1≤j≤b, 1≤t≤n and get random vector c⟶′.(7)
Insert vectorsp⟶′, q⟶′, d⟶′, e⟶′, and c⟶′ to the view.
So, the view of the simulatorSimA’s construction is(27)SimASA,f∩SA,SB=SA,p⟶′,d⟶′,e⟶′,q⟶′,c⟶′,f∩SA,SB.
Note that, in both views, the inputSA and the output f∩SA,SB are identical. Pseudorandom function is used to blind the elements in the real protocol. We can get blinded vectors p⟶,q⟶,d⟶,e⟶,c⟶ from the real protocol. On the other hand, through the calculation of the simulator, p⟶′,d⟶′,e⟶′,q⟶′, and c⟶′ are random vectors. So, p⟶ and p⟶′, q⟶ and q⟶′, d⟶ and d⟶′, e⟶ and e⟶′, c⟶ and c⟶′ are computationally indistinguishable.Case 2.
Corrupted partyB: in the real protocol, party B′s view is(28)ViewBπSA,SB=SB,p⟶,d⟶,e⟶,q⟶,c⟶,⊥.
We construct a simulatorSimB who has the input SB and performs the following steps:(1)
Create an empty view and then appendSB to it.(2)
Pick a setS′A with d elements at random.(3)
Construct polynomialsρj′Ax and ρj′Bxt1≤j≤b, representing sets S′A and SB, respectively. And generate random polynomials γj′Ax and γj′Bx for 1≤j≤b.(4)
Generate the Random Valueszj,t′A and zj,t′B for 1≤j≤b,1≤t≤n(5)
Blind the polynomials’ values and get random vectorsp⟶′, q⟶′, e⟶′, and d⟶′, where pj,t′, ej,t′, dj,t′, and qj,t′ for 1≤j≤b, 1≤t≤n are computed as follows:(29)pj,t′=γj′Axt+ρj′Axt⋅zj,t′A,dj,t′=ρj′Bxt⋅zj,t′B+γj′Bxt,ej,t′=ρj′Bxt+γj′Bxt⋅zj,t′B,qj,t′=ej,t′⋅γj′Axt−ρj′Axt⋅dj,t′⋅zj,t′A.(6)
Computecj,t′=ρj′Bxt⋅γj′Axt−ρj′Axt⋅γj′Bxt⋅zj,t′Afor 1≤j≤b, 1≤t≤n, and get random vector c⟶^′.(7)
Insert vectorp⟶′, q⟶′, d⟶′, e⟶′, and c⟶′ to the view.
So, the view of the simulatorSimB’s construction is(30)SimBSB,⊥=SB,p⟶′,d⟶′,e⟶′,q⟶′,c⟶′,⊥.
Note that, in both views, the inputSB is identical and the output ⊥ is empty. Pseudorandom function is used to blind the elements in the real protocol. We can get blinded vectors p⟶,q⟶,d⟶,e⟶,c⟶. On the other hand, through the calculation of the simulator SimB, p⟶′,q⟶′,d⟶′,e⟶′, and c⟶′ are random vectors. Thus, p⟶ and p⟶′, q⟶ and q⟶′, d⟶ and d⟶′, e⟶ and e⟶′, and c⟶ and c⟶′ are computationally indistinguishable.
Combining the above, we can get that(31)veiwAπSA,SB≡cSimASA,f∩SA,SB,veiwBπSA,SB≡cSimBSB,⊥.
Therefore, the hashing protocol is secure in the semihonest model.


## 5.1. Correctness of the Hashing Protocol

Because for1≤j≤b, 1≤t≤n,(22)qj,t=ej,t⋅γjAxt−ρjAxt⋅dj,t⋅zj,tA=ρjBxt+γjBxt⋅zj,tB⋅γjAxt⋅zj,tA−γjBxt+ρjBxt⋅zj,tB⋅ρjAxt⋅zj,tA.Next,(23)cj,t=pj,t⋅oj,t+qj,t⋅1+zj,tB−1=ρjAxt+γjAxt⋅zj,tA⋅ρjBxt−γjBxt⋅zj,tB+ρjBxt+γjBxt⋅zj,tB⋅γjAxt⋅zj,tA−γjBxt+ρjBxt⋅zj,tB⋅ρjAxt⋅zj,tA⋅1+zj,tB−1=γjAxt⋅ρjBxt−γjBxt⋅ρjAxt⋅zj,tA⋅1+zj,tB⋅1+zj,tB−1=γjAxt⋅ρjBxt−γjBxt⋅ρjAxt⋅zj,tA.Then,(24)yj,t=cj,t⋅zj,tA−1=γjAxt⋅ρjBxt⋅zj,tA⋅zj,tA−1−γjBxt⋅ρjAxt⋅zj,tA⋅zj,tA−1=γjAxt⋅ρjBxt−γjBxt⋅ρjAxt.And the polynomialsφjx are restored using the point-value pairs xj,yj,t, where φjx=γjAx⋅ρjBx−γjBx⋅ρjAx.. From Definition 3, the intersection SA∩SB could be learnt by finding roots of the polynomials φjx1≤j≤b.Thus, the hashing protocol is correct.


## 5.2. Security Proof

The above hashing PSI protocol is securely computing the set intersection in the presence of a semihonest adversary.Theorem 1.
IfPRF is a pseudorandom function, then the hashing PSI protocol π is secure in the presence of a semihonest adversary.Proof.
We prove it by considering the cases where each of parties has been corrupted. In each case, we will construct a simulator who is only given the corrupted party’s input/output and generates a simulated view that has to be computationally indistinguishable from the real protocol.Case 1.
Corrupted partyA: in the real protocol, party A′s view is(25)ViewAπSA,SB=SA,p⟶,d⟶,e⟶,q⟶,c⟶,f∩SA,SB.
The simulatorSimA is constructed and performs the following steps:(1)
Create an empty view and then appendSA and f∩SA,SB to it.(2)
Pick a setS′B with d elements at random such that SA∩S′B=f∩SA,SB.(3)
Construct polynomialsρj′Ax and ρj′Bx1≤j≤b representing sets SA and S′B, respectively. And generate random polynomials γj′Ax and γj′Bx for 1≤j≤b.(4)
Generate the Random Valueszj,t′A and zj,t′B for 1≤j≤b,1≤t≤n(5)
Blind the polynomials’ values and get random vectorsp⟶′, q⟶′, e⟶′, and d⟶′, where pj,t′, ej,t′, dj,t′, and qj,t′ (1≤j≤b, 1≤t≤n) are computed as follows:(26)pj,t′=γj′Axt+ρj′Axt⋅zj,t′A,dj,t′=ρj′Bxt⋅zj,t′B+γj′Bxt,ej,t′=ρj′Bxt+γj′Bxt⋅zj,t′B,qj,t′=ej,t′⋅γj′Axt−ρj′Axt⋅dj,t′⋅zj,t′A.(6)
Computecj,t′=ρj′Bxt⋅γj′Axt−ρj′Axt⋅γj′Bxt⋅zj,t′A for 1≤j≤b, 1≤t≤n and get random vector c⟶′.(7)
Insert vectorsp⟶′, q⟶′, d⟶′, e⟶′, and c⟶′ to the view.
So, the view of the simulatorSimA’s construction is(27)SimASA,f∩SA,SB=SA,p⟶′,d⟶′,e⟶′,q⟶′,c⟶′,f∩SA,SB.
Note that, in both views, the inputSA and the output f∩SA,SB are identical. Pseudorandom function is used to blind the elements in the real protocol. We can get blinded vectors p⟶,q⟶,d⟶,e⟶,c⟶ from the real protocol. On the other hand, through the calculation of the simulator, p⟶′,d⟶′,e⟶′,q⟶′, and c⟶′ are random vectors. So, p⟶ and p⟶′, q⟶ and q⟶′, d⟶ and d⟶′, e⟶ and e⟶′, c⟶ and c⟶′ are computationally indistinguishable.Case 2.
Corrupted partyB: in the real protocol, party B′s view is(28)ViewBπSA,SB=SB,p⟶,d⟶,e⟶,q⟶,c⟶,⊥.
We construct a simulatorSimB who has the input SB and performs the following steps:(1)
Create an empty view and then appendSB to it.(2)
Pick a setS′A with d elements at random.(3)
Construct polynomialsρj′Ax and ρj′Bxt1≤j≤b, representing sets S′A and SB, respectively. And generate random polynomials γj′Ax and γj′Bx for 1≤j≤b.(4)
Generate the Random Valueszj,t′A and zj,t′B for 1≤j≤b,1≤t≤n(5)
Blind the polynomials’ values and get random vectorsp⟶′, q⟶′, e⟶′, and d⟶′, where pj,t′, ej,t′, dj,t′, and qj,t′ for 1≤j≤b, 1≤t≤n are computed as follows:(29)pj,t′=γj′Axt+ρj′Axt⋅zj,t′A,dj,t′=ρj′Bxt⋅zj,t′B+γj′Bxt,ej,t′=ρj′Bxt+γj′Bxt⋅zj,t′B,qj,t′=ej,t′⋅γj′Axt−ρj′Axt⋅dj,t′⋅zj,t′A.(6)
Computecj,t′=ρj′Bxt⋅γj′Axt−ρj′Axt⋅γj′Bxt⋅zj,t′Afor 1≤j≤b, 1≤t≤n, and get random vector c⟶^′.(7)
Insert vectorp⟶′, q⟶′, d⟶′, e⟶′, and c⟶′ to the view.
So, the view of the simulatorSimB’s construction is(30)SimBSB,⊥=SB,p⟶′,d⟶′,e⟶′,q⟶′,c⟶′,⊥.
Note that, in both views, the inputSB is identical and the output ⊥ is empty. Pseudorandom function is used to blind the elements in the real protocol. We can get blinded vectors p⟶,q⟶,d⟶,e⟶,c⟶. On the other hand, through the calculation of the simulator SimB, p⟶′,q⟶′,d⟶′,e⟶′, and c⟶′ are random vectors. Thus, p⟶ and p⟶′, q⟶ and q⟶′, d⟶ and d⟶′, e⟶ and e⟶′, and c⟶ and c⟶′ are computationally indistinguishable.
Combining the above, we can get that(31)veiwAπSA,SB≡cSimASA,f∩SA,SB,veiwBπSA,SB≡cSimBSB,⊥.
Therefore, the hashing protocol is secure in the semihonest model.


## 6. Evaluation

### 6.1. Implementation

We ran our experiments in Ubuntu 18.04 with Linux 4.4.0.59 64-bit desktop PC. All protocols were implemented and executed using the same hardware equipped with Intel Core i7-7700K CPU with 3.6 GHz and 8 GB of RAM. We implemented our protocol and related protocols [3, 18, 26, 32, 34] in the same environment setting. Our protocol and related protocols had the same number of input elements, whose size was 32 bits. Our protocol was implemented using the Number Theory Library (NTL) along with the GNU Multiprecision (GMP) library for polynomial arithmetic.We give the running times of related protocols in Table1 and Figure 3. From them, it can be seen that our protocol is more efficient than public-key-based and circuit-based PSI protocols, and it is more efficient than OT-based PSI protocols with the set size less than 212.Table 1
Running time in ms with related PSI protocols.
TypeProtocolSet size28212216220Public-keyCristofaro2010 [18]779125462030363193920CircuitHuang2012 [26]79137732292—OTDong2013 [32]105448417965218Pinkas2014 [34]95346299149171Pinkas2018 [3]3113627025847NovelOur223185095132220Figure 3
Running time in ms with related PSI protocols.


### 6.2. Experimental Results

A detailed analysis with related PSI protocols is given in Table2. We evaluate the performance in terms of four properties: needing cryptosystem or not, simulated-based security, computation complexity, and communication complexity. From Table 2, our protocol enjoys the following advantages. (1) There is no need for a complicated cryptographic system in our protocol, which only uses hashing and pseudorandom function and provides a lightweight system. But, in other protocols, asymmetric encryption system or symmetric encryption system is needed. (2) Our protocol gives a detailed formal security proof by using the ideal/real simulation mechanism in the standard model while [3, 26, 34] only show an informal security analysis. (3) Computation complexity and communication complexity of our protocol are Od, while both of [26] are Od⋅logd.Table 2
Comparison with related PSI protocols.
TypeProtocolPropertyNeeding cryptosystemSimulated-based SecurityComputation ComplexityCommunication ComplexityPublic-keyCristofaro2010 [18]asymYesOdOdCircuitHuang2012 [26]symNoOd⋅logdOd⋅logdOTDong2013 [32]symYesOdOdPinkas2014 [34]symNoOdOdPinkas2018 [3]symNoOdOdNovelOurNoYesOdOdasym: public-key cryptography. sym: symmetric cryptography.d: set cardinality.


## 6.1. Implementation

We ran our experiments in Ubuntu 18.04 with Linux 4.4.0.59 64-bit desktop PC. All protocols were implemented and executed using the same hardware equipped with Intel Core i7-7700K CPU with 3.6 GHz and 8 GB of RAM. We implemented our protocol and related protocols [3, 18, 26, 32, 34] in the same environment setting. Our protocol and related protocols had the same number of input elements, whose size was 32 bits. Our protocol was implemented using the Number Theory Library (NTL) along with the GNU Multiprecision (GMP) library for polynomial arithmetic.We give the running times of related protocols in Table1 and Figure 3. From them, it can be seen that our protocol is more efficient than public-key-based and circuit-based PSI protocols, and it is more efficient than OT-based PSI protocols with the set size less than 212.Table 1
Running time in ms with related PSI protocols.
TypeProtocolSet size28212216220Public-keyCristofaro2010 [18]779125462030363193920CircuitHuang2012 [26]79137732292—OTDong2013 [32]105448417965218Pinkas2014 [34]95346299149171Pinkas2018 [3]3113627025847NovelOur223185095132220Figure 3
Running time in ms with related PSI protocols.


## 6.2. Experimental Results

A detailed analysis with related PSI protocols is given in Table2. We evaluate the performance in terms of four properties: needing cryptosystem or not, simulated-based security, computation complexity, and communication complexity. From Table 2, our protocol enjoys the following advantages. (1) There is no need for a complicated cryptographic system in our protocol, which only uses hashing and pseudorandom function and provides a lightweight system. But, in other protocols, asymmetric encryption system or symmetric encryption system is needed. (2) Our protocol gives a detailed formal security proof by using the ideal/real simulation mechanism in the standard model while [3, 26, 34] only show an informal security analysis. (3) Computation complexity and communication complexity of our protocol are Od, while both of [26] are Od⋅logd.Table 2
Comparison with related PSI protocols.
TypeProtocolPropertyNeeding cryptosystemSimulated-based SecurityComputation ComplexityCommunication ComplexityPublic-keyCristofaro2010 [18]asymYesOdOdCircuitHuang2012 [26]symNoOd⋅logdOd⋅logdOTDong2013 [32]symYesOdOdPinkas2014 [34]symNoOdOdPinkas2018 [3]symNoOdOdNovelOurNoYesOdOdasym: public-key cryptography. sym: symmetric cryptography.d: set cardinality.


## 7. Conclusion and Future Work

In this paper, we proposed a new approach to PSI protocol without any cryptosystem based on point-value polynomial representation and pseudorandom function and optimized it based on hashing techniques. Our protocol had high performance with set elements less than212. In our protocols, there was a constraint that both parties should have the same set degree. In the future, we will extend our approach and study PSI protocols with a lightweight client where the server had a very large degree but the client’s degree is relatively small.



---

*Source: 8890677-2020-09-01.xml*