# Privacy-Preserving Graph Operations for Mobile Authentication

Authors: Peng Li; Fucai Zhou; Zifeng Xu; Yuxi Li; Jian Xu
Journal: Wireless Communications and Mobile Computing
 (2020)

---

## Abstract

Along with the fast development of wireless technologies, smart devices have become an integral part of our daily life. Authentication is one of the most common and effective methods for these smart devices to prevent unauthorized access. Moreover, smart devices tend to have limited computing power, and they may possess sensitive data. In this paper, we investigate performing graph operations in a privacy-preserving manner, which can be used for anonymous authentication for smart devices. We propose two protocols that allow two parties to jointly compute the intersection and union of their private graphs. Our protocols utilize homomorphic encryption to prevent information leakage during the process, and we provide security proofs of the protocols in the semihonest setting. At last, we implement and evaluate the efficiency of our protocols through experiments on real-world graph data.


---

## Body

## 1. Introduction

With the rapid development of IoT technology, we are surrounded by various types of smart devices in our daily life, such as sensors, wearable devices, and smart vehicles [1]. Authentication is one of the most important mechanisms to provide security protection for these smart devices [2], and authentication for light-weighted devices has become a hot research topic in the past years [3, 4].In recent years, researchers have proposed several mobile authentication schemes based on graph data structure and graph algorithms [5–7]. Graph data and graph processing are well studied for the last decades [8, 9], since they can help to solve many practical problems in different application areas, such as web data processing [10], data mining [11], social networking [12], biological networking [13], and communication networking [14].


### 1.1. Motivation

In this paper, we consider the problem of computing graph operations between two parties while preventing information leakage, which has great potential in smart device authentication. For example, when the mobile devices communicate with cloud servers, they need to first jointly perform identity authentication for security protection. Since the mobile devices may contain sensitive information of the users and the cloud servers cannot be fully trusted in general, the privacy leakage problem for mobile authentication has become a security threat [15]. In order to protect the privacies of the mobile devices, the devices can model their identities and properties as graph-structured data, and the cloud servers can model their authentication policies as graph-structured data as well. After that, the identity authentication process can be converted into performing graph operations in a privacy-preserving manner.


### 1.2. Our Contributions

We study the problem of performing graph intersection and union while protecting the privacies of the input graphs. Suppose that for two parties, Alice and Bob, each has a private graph, denoted asGA and GB, respectively. Alice wishes to learn the intersection and union of these two graphs. In other words, Alice wishes to learn GI=GA⋂GB and GU=GA⋃GB. In addition, both Alice and Bob do not wish to reveal any information about their graphs to the other party. The contributions of this paper can be summarized as below:
(i)
We present two graph operation protocols between two parties, a server and a client. The first protocol allows the server and the client to jointly compute the intersection of their input graphs, and the second protocol computes the union of the input graphs. Our constructions first use the Paillier cryptosystem and oblivious polynomial evaluation to compute the intersection and the union of the vertices. After that, we use the homomorphic property of the Paillier cryptosystem to compute the edge intersection and union(ii)
We provide the security models of the protocols, and we prove that the protocols are secure in the semihonest setting. Furthermore, we analyze the information leakage and propose methods to minimize the leakages(iii)
We discuss the efficiencies of the protocols in terms of computation costs and communication costs. At last, we implement our constructions and perform experiments on real-world graph dataAn earlier version of this paper was presented at the 22nd Australasian Conference on Information Security and Privacy, 2017 [16]. The previous work presented a private graph intersection protocol with rough analysis. This paper extends the previous work by presenting a private graph union protocol with detailed analysis and experimental results.


## 1.1. Motivation

In this paper, we consider the problem of computing graph operations between two parties while preventing information leakage, which has great potential in smart device authentication. For example, when the mobile devices communicate with cloud servers, they need to first jointly perform identity authentication for security protection. Since the mobile devices may contain sensitive information of the users and the cloud servers cannot be fully trusted in general, the privacy leakage problem for mobile authentication has become a security threat [15]. In order to protect the privacies of the mobile devices, the devices can model their identities and properties as graph-structured data, and the cloud servers can model their authentication policies as graph-structured data as well. After that, the identity authentication process can be converted into performing graph operations in a privacy-preserving manner.


## 1.2. Our Contributions

We study the problem of performing graph intersection and union while protecting the privacies of the input graphs. Suppose that for two parties, Alice and Bob, each has a private graph, denoted asGA and GB, respectively. Alice wishes to learn the intersection and union of these two graphs. In other words, Alice wishes to learn GI=GA⋂GB and GU=GA⋃GB. In addition, both Alice and Bob do not wish to reveal any information about their graphs to the other party. The contributions of this paper can be summarized as below:
(i)
We present two graph operation protocols between two parties, a server and a client. The first protocol allows the server and the client to jointly compute the intersection of their input graphs, and the second protocol computes the union of the input graphs. Our constructions first use the Paillier cryptosystem and oblivious polynomial evaluation to compute the intersection and the union of the vertices. After that, we use the homomorphic property of the Paillier cryptosystem to compute the edge intersection and union(ii)
We provide the security models of the protocols, and we prove that the protocols are secure in the semihonest setting. Furthermore, we analyze the information leakage and propose methods to minimize the leakages(iii)
We discuss the efficiencies of the protocols in terms of computation costs and communication costs. At last, we implement our constructions and perform experiments on real-world graph dataAn earlier version of this paper was presented at the 22nd Australasian Conference on Information Security and Privacy, 2017 [16]. The previous work presented a private graph intersection protocol with rough analysis. This paper extends the previous work by presenting a private graph union protocol with detailed analysis and experimental results.


## 2. Related Work

There are many different approaches to construct authentication schemes for smart devices. Among them, graph-based authentication schemes are widely used in IoT [5, 17, 18]. In 2002, Micali and Rivest [19] first introduced the transitive signature based on graph theory, which provides an unforgeable signature for undirected graphs. After that, various graph-based signature and authentication schemes were proposed [5–7]. In 2017, Chuang et al. [5] proposed an authentication system in Internet of Things based on multigraph zero-knowledge. The system provides suitable security protection for IoT authentication services. The proposed multigraph zero-knowledge procedure is faster than traditional zero-knowledge methods and ECC-based solutions. The experiment results indicate that the system is light-weighted and highly adaptive. Lin et al. [6] proposed a transitively graph authentication scheme for blockchain-based identity management systems in 2018. The system is used to bind a digital identity object to its real-world entity, therefore achieving identity authentication. The system is constructed based on transitively closed undirected graphs and vertex signatures. According to the evaluation results, the system is efficient, even when the graph dynamically adds or deletes vertices and edges. In 2019, Shao et al. [7] proposed a multifactor authentication scheme using a fuzzy graph domination model. The scheme is adaptive choosing one or multiple privacy-preserving identities to authenticate the users. The authors designed a weighted vertex-edge dominating set to solve the weighted domination problem on fuzzy graphs. Compared to existing solutions, the scheme is more efficient for solving instances with moderate orders.In this work, we consider the problem of performing graph intersection and union in the privacy-preserving manner and proposed two secure multiparty computation protocols. Secure Multiparty computation (MPC) has been extensively studied over the past decades. Generally speaking, MPC allows multiple participants to jointly perform certain computations without losing the privacy of their input data, even when some players cheat during the process. MPC was first formally introduced by Yao in 1982 [20] and extended by Goldreich et al. [21]. Their works convert certain computation problems into a combinatorial circuit, then the parties perform computations over the gates in the circuit. After that, a large number of MPC protocols have been proposed to solve various problems, such as privacy-preserving set operations [22] and private information retrieval [23].


## 3. Preliminary

In this section, we present the preliminaries related to our proposed protocols. First, we present the relevant notations that we used in this paper in Table1.Table 1
Table of notations.
SymbolDescriptionPGIPrivate graph intersection protocolPGUPrivate graph union protocolS, CThe server, the clientGS, GCThe server’s graph, the client’s graphGIThe intersection ofGSand GCGUThe union ofGS and GCVS, VC, VI, VUThe vertices ofGS, GC, GI, and GUES, EC, EI, EUThe edges ofGS, GC, GI, and GUm, n, p, qThe number of vertices inGS, GC, GI, and GU


### 3.1. Additive Homomorphic Encryption

Homomorphic encryption schemes allow the users to perform certain computation operations on the ciphertext space, such as addition and multiplication. In our private graph operation protocols, we utilize an additive homomorphic encryption scheme called the Paillier cryptosystem, proposed by Paillier in 1999 [24]. The Paillier cryptosystem contains three algorithms, described as follows:pk,sk←KeyGen1k is the key generation algorithm. The input is a security parameter k. The outputs are a public key pk and a secret key sk. The public key contains a large number N which specifies the message space, the ciphertext space, and the random space to be ℤN, ℤN2∗, and ℤN∗, respectively.t⊕←Encpk,t;r is the encryption algorithm. The input is the public key pk, a plaintext t∈ℤN, and a random number r∈ℤN∗. The output is the ciphertext t⊕∈ℤN2∗. For simplicity, we use the notion t⊕=Enct.t←Decsk,t⊕ is the decryption algorithm. The input is the secret key sk and a ciphertext t⊕∈ℤN2∗. The output is the plaintext t∈ℤN. For simplicity, we use the notion t=Dect⊕.The Paillier cryptosystem has the following properties:


#### 3.1.1. Correctness

For any key pairspk,sk←KeyGen1k and any plaintext t∈ℤN, DecEnct=t always holds.


#### 3.1.2. IND-CPA Security

Two ciphertextst0⊕ and t1⊕ are indistinguishable for probabilistic polynomial-time adversaries that only have access to the public parameters.


#### 3.1.3. Homomorphic Property

For any two plaintextst0,t1∈ℤN, there exists an operation ⊕ in the ciphertext space, such that DecEnct0⊕Enct1=t0+t1. Furthermore, there exists another operation ⊗ in the ciphertext space, such that DecEnct0⊗t1=t0·t1.


### 3.2. Private Set Intersection

Private Set Intersection (PSI) is a cryptographic protocol that allows two parties, each holding a private set, to jointly compute the intersection of their sets without leaking any additional information. The first secure two-party private set intersection protocol is introduced by Freedman, Nissim, and Pinkas (FNP) in 2004 [25]. The protocol utilizes homomorphic encryption and oblivious polynomial evaluation to ensure each party learns no information about the other party’s private input during the computation. Later, several other protocols have been proposed with different features and security levels [26–28].


### 3.3. Graph Representation

In our protocol, we represent a graph asG=V,E, where V is the vertex collection and E is the edge collection. We represent the vertex collection as a sorted set with ascending order, V=v1,v2,⋯,vz, where z is the number of vertices in G, vi∈ℤ, and vi<vi+1 for 1≤i≤z−1. We represent the edge collection as an adjacency matrix,
(1)E=e1,1⋯e1,z⋮⋱⋮ez,1⋯ez,z,where ei,j is the adjacency relation between the vertices vi and vj, and ei,j∈0,1. If vertices vi and vj are adjacent, i.e., there is at least one edge that connects them, ei,j=1; otherwise, ei,j=0. Note that E is a square matrix with z rows and z columns. For an undirected graph, E is a symmetric matrix, since the edges are two-way.For example, we represent the directed graph illustrated in Figure1 as G=V,E, where V=1,5,23,50,74 and
(2)E=0101001000100010000100111.Figure 1
Example graph.


## 3.1. Additive Homomorphic Encryption

Homomorphic encryption schemes allow the users to perform certain computation operations on the ciphertext space, such as addition and multiplication. In our private graph operation protocols, we utilize an additive homomorphic encryption scheme called the Paillier cryptosystem, proposed by Paillier in 1999 [24]. The Paillier cryptosystem contains three algorithms, described as follows:pk,sk←KeyGen1k is the key generation algorithm. The input is a security parameter k. The outputs are a public key pk and a secret key sk. The public key contains a large number N which specifies the message space, the ciphertext space, and the random space to be ℤN, ℤN2∗, and ℤN∗, respectively.t⊕←Encpk,t;r is the encryption algorithm. The input is the public key pk, a plaintext t∈ℤN, and a random number r∈ℤN∗. The output is the ciphertext t⊕∈ℤN2∗. For simplicity, we use the notion t⊕=Enct.t←Decsk,t⊕ is the decryption algorithm. The input is the secret key sk and a ciphertext t⊕∈ℤN2∗. The output is the plaintext t∈ℤN. For simplicity, we use the notion t=Dect⊕.The Paillier cryptosystem has the following properties:


### 3.1.1. Correctness

For any key pairspk,sk←KeyGen1k and any plaintext t∈ℤN, DecEnct=t always holds.


### 3.1.2. IND-CPA Security

Two ciphertextst0⊕ and t1⊕ are indistinguishable for probabilistic polynomial-time adversaries that only have access to the public parameters.


### 3.1.3. Homomorphic Property

For any two plaintextst0,t1∈ℤN, there exists an operation ⊕ in the ciphertext space, such that DecEnct0⊕Enct1=t0+t1. Furthermore, there exists another operation ⊗ in the ciphertext space, such that DecEnct0⊗t1=t0·t1.


## 3.1.1. Correctness

For any key pairspk,sk←KeyGen1k and any plaintext t∈ℤN, DecEnct=t always holds.


## 3.1.2. IND-CPA Security

Two ciphertextst0⊕ and t1⊕ are indistinguishable for probabilistic polynomial-time adversaries that only have access to the public parameters.


## 3.1.3. Homomorphic Property

For any two plaintextst0,t1∈ℤN, there exists an operation ⊕ in the ciphertext space, such that DecEnct0⊕Enct1=t0+t1. Furthermore, there exists another operation ⊗ in the ciphertext space, such that DecEnct0⊗t1=t0·t1.


## 3.2. Private Set Intersection

Private Set Intersection (PSI) is a cryptographic protocol that allows two parties, each holding a private set, to jointly compute the intersection of their sets without leaking any additional information. The first secure two-party private set intersection protocol is introduced by Freedman, Nissim, and Pinkas (FNP) in 2004 [25]. The protocol utilizes homomorphic encryption and oblivious polynomial evaluation to ensure each party learns no information about the other party’s private input during the computation. Later, several other protocols have been proposed with different features and security levels [26–28].


## 3.3. Graph Representation

In our protocol, we represent a graph asG=V,E, where V is the vertex collection and E is the edge collection. We represent the vertex collection as a sorted set with ascending order, V=v1,v2,⋯,vz, where z is the number of vertices in G, vi∈ℤ, and vi<vi+1 for 1≤i≤z−1. We represent the edge collection as an adjacency matrix,
(1)E=e1,1⋯e1,z⋮⋱⋮ez,1⋯ez,z,where ei,j is the adjacency relation between the vertices vi and vj, and ei,j∈0,1. If vertices vi and vj are adjacent, i.e., there is at least one edge that connects them, ei,j=1; otherwise, ei,j=0. Note that E is a square matrix with z rows and z columns. For an undirected graph, E is a symmetric matrix, since the edges are two-way.For example, we represent the directed graph illustrated in Figure1 as G=V,E, where V=1,5,23,50,74 and
(2)E=0101001000100010000100111.Figure 1
Example graph.


## 4. Definitions and Security Models

### 4.1. Protocol Definitions

We formally describe the private graph intersection (PGI) protocol and the private graph union (PGU) protocol. The protocols involve two participants, a server and a client, denoted asS and C, respectively. Each of the participants holds a private graph, which is intended to be kept secret from the other participant.We denote the graphs of the server and client asGS=VS,ES and GC=VC,EC, respectively, where V and E are the sets of vertices and edges of the graphs. The intersection of GS and GC is defined as GI=GS⋂GC=VI,EI, where VI=VS⋂VC and EI=ES⋂EC. The union of GS and GC is defined as GU=GS⋃GC=VU,EU, where VU=VS⋃VC and EU=ES⋃EC.PGI and PGU allow the participants to jointly computeGI and GU, respectively, in a privacy-preserving manner. At the end of the protocols, only the server learns the result. The formal definitions of PGI and PGU are described as follows:Definition 1 (private graph intersection protocol).
If both participants are honest, for anyGS=VS,ES and any GC=VC,EC, the private graph intersection protocol computes GI=GS⋂GC. At the end of the protocol, only S learns GI.Definition 2 (private graph union protocol).
If both participants are honest, for anyGS=VS,ES and any GC=VC,EC, the private graph union protocol computes GU=GS⋃GC. At the end of the protocol, only S learns GU.


### 4.2. Security Models

When considering privacy protecting in authentication, the term privacy may have different definitions and properties, such as user identity and untraceability [29, 30]. In this work, the privacies of the server and the client refer to any information about their graphs. Therefore, any information about the vertices and edges of the graphs is considered as private, such as the number of vertices, the number of edges, the values of the vertices, and whether two vertices are connected by an edge.The security goals of both PGI and PGU protocols are protecting the privacies of both the server and the client during the computation. In other words, both the server and the client should learn no information about the graph of the other party.We use the semihonest security model for both PGI and PGU, which means both the server and the client perform the protocols faithfully, but they may try to learn any information about the graph of the other participant. The security models are adopted from the work of [31–33].While achieving no information leakage is the ideal goal, our protocols leak partial information during the process. The information leakages for PGI are defined as leakage functionsL1 and L2, and the information leakages for PGU are defined as L3 and L4. The detailed information about the leakage functions are as follows: L1 is the number of vertices in GC, L2 is the vertex intersection VI and the number of vertices in GS, L3 is the number of vertices in GC and the number of common vertices between GS and GC, and L4 is the vertex union VU and the number of vertices in GS.The formal definitions of security models are described as follows:Definition 3 (PGI security).
A semihonest server learns nothing about the client’s graph, beyond what can be deduced fromGI and the leakage function L1, and a semihonest client learns nothing about the server’s graph, beyond the leakage function L2.Definition 4 (PGU security).
A semihonest server learns nothing about the client’s graph, beyond what can be deduced fromGU and the leakage function L3, and a semihonest client learns nothing about the server’s graph, beyond the leakage function L4.


## 4.1. Protocol Definitions

We formally describe the private graph intersection (PGI) protocol and the private graph union (PGU) protocol. The protocols involve two participants, a server and a client, denoted asS and C, respectively. Each of the participants holds a private graph, which is intended to be kept secret from the other participant.We denote the graphs of the server and client asGS=VS,ES and GC=VC,EC, respectively, where V and E are the sets of vertices and edges of the graphs. The intersection of GS and GC is defined as GI=GS⋂GC=VI,EI, where VI=VS⋂VC and EI=ES⋂EC. The union of GS and GC is defined as GU=GS⋃GC=VU,EU, where VU=VS⋃VC and EU=ES⋃EC.PGI and PGU allow the participants to jointly computeGI and GU, respectively, in a privacy-preserving manner. At the end of the protocols, only the server learns the result. The formal definitions of PGI and PGU are described as follows:Definition 1 (private graph intersection protocol).
If both participants are honest, for anyGS=VS,ES and any GC=VC,EC, the private graph intersection protocol computes GI=GS⋂GC. At the end of the protocol, only S learns GI.Definition 2 (private graph union protocol).
If both participants are honest, for anyGS=VS,ES and any GC=VC,EC, the private graph union protocol computes GU=GS⋃GC. At the end of the protocol, only S learns GU.


## 4.2. Security Models

When considering privacy protecting in authentication, the term privacy may have different definitions and properties, such as user identity and untraceability [29, 30]. In this work, the privacies of the server and the client refer to any information about their graphs. Therefore, any information about the vertices and edges of the graphs is considered as private, such as the number of vertices, the number of edges, the values of the vertices, and whether two vertices are connected by an edge.The security goals of both PGI and PGU protocols are protecting the privacies of both the server and the client during the computation. In other words, both the server and the client should learn no information about the graph of the other party.We use the semihonest security model for both PGI and PGU, which means both the server and the client perform the protocols faithfully, but they may try to learn any information about the graph of the other participant. The security models are adopted from the work of [31–33].While achieving no information leakage is the ideal goal, our protocols leak partial information during the process. The information leakages for PGI are defined as leakage functionsL1 and L2, and the information leakages for PGU are defined as L3 and L4. The detailed information about the leakage functions are as follows: L1 is the number of vertices in GC, L2 is the vertex intersection VI and the number of vertices in GS, L3 is the number of vertices in GC and the number of common vertices between GS and GC, and L4 is the vertex union VU and the number of vertices in GS.The formal definitions of security models are described as follows:Definition 3 (PGI security).
A semihonest server learns nothing about the client’s graph, beyond what can be deduced fromGI and the leakage function L1, and a semihonest client learns nothing about the server’s graph, beyond the leakage function L2.Definition 4 (PGU security).
A semihonest server learns nothing about the client’s graph, beyond what can be deduced fromGU and the leakage function L3, and a semihonest client learns nothing about the server’s graph, beyond the leakage function L4.


## 5. Protocol Construction

In this section, we propose the constructions of PGI and PGU. The graphs of the server and the client are represented asGS=VS,ES and GC=VC,EC, respectively, where VS=s1,s2,⋯,sm, VC=c1,c2,⋯,cn,
(3)ES=s1,1⋯s1,m⋮⋱⋮sm,1⋯sm,m,EC=c1,1⋯c1,n⋮⋱⋮cn,1⋯cn,n.


### 5.1. PGI Construction

We use the FNP protocol [25] as a building block for computing the vertex intersection. The private graph intersection protocol is described below:Input: S and C hold the graphs GS=VS,ES and GC=VC,EC, respectively.Output:S learns GI=VI,EI.Protocol:Step 1.
S runs the key generation algorithm of the Paillier cryptosystem, pk,sk←KeyGen1k, and obtains the public key and the secret key. Then, S publishes pk.Step 2.
(a)
S constructs a polynomial Px=x−s1x−s2⋯x−sm=∑u=0mαuxu, such that all the roots of Px are exactly the elements in VS. In other words, Px=0 if and only if x∈VS(b)
S encrypts each αi, for 0≤i≤m, under the Paillier cryptosystem, and sends the set of ciphertexts α⊕=αi⊕0≤i≤m to CStep 3.
(a)
By using the homomorphic properties of the Paillier cryptosystem,C evaluates the polynomial P using each element in VC as input. In other words, C computes EncPci, for 1≤i≤n(b)
For each polynomial evaluation,C chooses a random value r and computes βi⊕=EncrPci+ci. Then, C sends β⊕=βi⊕1≤i≤n to SStep 4.
S decrypts all the ciphertexts received and compares the decrypted values with his vertex set VS. If a decrypted value βi=Decβi⊕ has a corresponding element in VS, it is an element of the intersection of VS and VC. In other words, if βi∈VS, βi∈VI. After decrypting all the received ciphertexts, the server obtains VI.Step 5.
(a)
S uses VI to construct an adjacency matrix A of size p×p, where p is the number of the vertex in VI:(4)A=a1,1⋯a1,p⋮⋱⋮ap,1⋯ap,p.
A has the property that, for each vertex pair vx∈VI and vy∈VI, if an edge exists in GS between vertices vx and vy, ax,y=1; otherwise, ax,y=0.
(b)
S encrypts each element in A under the Paillier cryptosystem and obtains an encrypted matrix A⊕=EncA(c)
S sends A⊕ and VI to CStep 6.
(a)
By usingVI, C constructs an adjacency matrix B using the same method in the last step:(5)B=b1,1⋯b1,p⋮⋱⋮bp,1⋯bp,p(b)
C computes(6)EI⊕=A⊕⊗B=a1,1⊕⋯a1,p⊕⋮⋱⋮ap,1⊕⋯ap,p⊕⊗b1,1⋯b1,p⋮⋱⋮bp,1⋯bp,p=a1,1⊕⊗b1,1⋯a1,p⊕⊗b1,p⋮⋱⋮ap,1⊕⊗bp,1⋯ap,p⊕⊗bp,p(c)
C sends EI⊕ to SStep 7.
S decrypts each element in EI⊕ and obtains EI=DecEI⊕. At last, S obtains GI=VI,EI.


### 5.2. PGU Construction

The private graph union protocol is described below:Input: S and C hold the graphs GS=VS,ES and GC=VC,EC, respectively.Output:S learns GU=VU,EU.Protocol:Step 1.
Same as Step1 of PGI.Step 2.
Same as Step2 of PGI.Step 3.
(a)
By using the homomorphic properties of the Paillier cryptosystem,C evaluates the polynomial P using each element in VC as input. In other words, C computes EncPci, for 1≤i≤n(b)
For each polynomial evaluation,C choose a random value r and computes βi⊕=EncPci⊗r. Then, C sends the set of all resulting ciphertexts β⊕=βi⊕1≤i≤n to SStep 4.
S decrypts each ciphertext received as βi=Decβi⊕ and checks the decrypted value. If βi=0, S computes γi⊕=Enc0; otherwise, S computes γi⊕=Enc1. Then, S sends γ⊕=γi⊕1≤i≤n to C.Step 5.
After receivingγ⊕, C computes δi⊕=ci⊗γi⊕, for 1≤i≤n. Then, C sends δ⊕=δi⊕1≤i≤n to S.Step 6.
(a)
S decryptes each value in δ⊕ and checks if the decrypted value δi=Decδi⊕ is zero(b)
By combining the server’s vertex setVS and the set of nonzero decrypted values δiδi≠0, S obtains VU. VU is then sorted in ascending order and is represented as VU=u1,u2,⋯,uqStep 7.
(a)
S uses VU to construct an adjacency matrix A of size q×q, where q is the number of vertex in VU:(7)A=a1,1⋯a1,q⋮⋱⋮aq,1⋯aq,q.
A has the property that, for each vertex pair ux∈VU and uy∈VU, if an edge exists in GS between vertices ux and uy, ax,y=1; otherwise, ax,y=0(b)
S encrypts each element in A under the Paillier cryptosystem and sends the encrypted matrix A⊕ and VU to CStep 8.
(a)
C uses VU to construct an adjacency matrix B in the same manner as S in the last step:(8)B=b1,1⋯b1,q⋮⋱⋮bq,1⋯bq,q(b)
C encrypts each element in B using the Paillier cryptosystem and obtains B⊕(c)
C generates a matrix R with q×q random values:(9)R=r1,1⋯r1,q⋮⋱⋮rq,1⋯rq,q(d)
C computes:(10)EU⊕=A⊕⊕B⊕⊗R=a1,1⊕⊕b1,1⊕⊗r1,1⋯a1,q⊕⊕b1,q⊕⊗r1,q⋮⋱⋮aq,1⊕⊕bq,1⊕⊗rq,1⋯aq,q⊕⊕bq,q⊕⊗rq,q=e1,1⊕⋯e1,q⊕⋮⋱⋮eq,1⊕⋯eq,q⊕(e)
C cends EU⊕ to SStep 9.
S decrypts the matrix EU⊕. For each decrypted element ei,j, if ei,j≠0, set ei,j=1. At last, S obtains EU.


## 5.1. PGI Construction

We use the FNP protocol [25] as a building block for computing the vertex intersection. The private graph intersection protocol is described below:Input: S and C hold the graphs GS=VS,ES and GC=VC,EC, respectively.Output:S learns GI=VI,EI.Protocol:Step 1.
S runs the key generation algorithm of the Paillier cryptosystem, pk,sk←KeyGen1k, and obtains the public key and the secret key. Then, S publishes pk.Step 2.
(a)
S constructs a polynomial Px=x−s1x−s2⋯x−sm=∑u=0mαuxu, such that all the roots of Px are exactly the elements in VS. In other words, Px=0 if and only if x∈VS(b)
S encrypts each αi, for 0≤i≤m, under the Paillier cryptosystem, and sends the set of ciphertexts α⊕=αi⊕0≤i≤m to CStep 3.
(a)
By using the homomorphic properties of the Paillier cryptosystem,C evaluates the polynomial P using each element in VC as input. In other words, C computes EncPci, for 1≤i≤n(b)
For each polynomial evaluation,C chooses a random value r and computes βi⊕=EncrPci+ci. Then, C sends β⊕=βi⊕1≤i≤n to SStep 4.
S decrypts all the ciphertexts received and compares the decrypted values with his vertex set VS. If a decrypted value βi=Decβi⊕ has a corresponding element in VS, it is an element of the intersection of VS and VC. In other words, if βi∈VS, βi∈VI. After decrypting all the received ciphertexts, the server obtains VI.Step 5.
(a)
S uses VI to construct an adjacency matrix A of size p×p, where p is the number of the vertex in VI:(4)A=a1,1⋯a1,p⋮⋱⋮ap,1⋯ap,p.
A has the property that, for each vertex pair vx∈VI and vy∈VI, if an edge exists in GS between vertices vx and vy, ax,y=1; otherwise, ax,y=0.
(b)
S encrypts each element in A under the Paillier cryptosystem and obtains an encrypted matrix A⊕=EncA(c)
S sends A⊕ and VI to CStep 6.
(a)
By usingVI, C constructs an adjacency matrix B using the same method in the last step:(5)B=b1,1⋯b1,p⋮⋱⋮bp,1⋯bp,p(b)
C computes(6)EI⊕=A⊕⊗B=a1,1⊕⋯a1,p⊕⋮⋱⋮ap,1⊕⋯ap,p⊕⊗b1,1⋯b1,p⋮⋱⋮bp,1⋯bp,p=a1,1⊕⊗b1,1⋯a1,p⊕⊗b1,p⋮⋱⋮ap,1⊕⊗bp,1⋯ap,p⊕⊗bp,p(c)
C sends EI⊕ to SStep 7.
S decrypts each element in EI⊕ and obtains EI=DecEI⊕. At last, S obtains GI=VI,EI.


## 5.2. PGU Construction

The private graph union protocol is described below:Input: S and C hold the graphs GS=VS,ES and GC=VC,EC, respectively.Output:S learns GU=VU,EU.Protocol:Step 1.
Same as Step1 of PGI.Step 2.
Same as Step2 of PGI.Step 3.
(a)
By using the homomorphic properties of the Paillier cryptosystem,C evaluates the polynomial P using each element in VC as input. In other words, C computes EncPci, for 1≤i≤n(b)
For each polynomial evaluation,C choose a random value r and computes βi⊕=EncPci⊗r. Then, C sends the set of all resulting ciphertexts β⊕=βi⊕1≤i≤n to SStep 4.
S decrypts each ciphertext received as βi=Decβi⊕ and checks the decrypted value. If βi=0, S computes γi⊕=Enc0; otherwise, S computes γi⊕=Enc1. Then, S sends γ⊕=γi⊕1≤i≤n to C.Step 5.
After receivingγ⊕, C computes δi⊕=ci⊗γi⊕, for 1≤i≤n. Then, C sends δ⊕=δi⊕1≤i≤n to S.Step 6.
(a)
S decryptes each value in δ⊕ and checks if the decrypted value δi=Decδi⊕ is zero(b)
By combining the server’s vertex setVS and the set of nonzero decrypted values δiδi≠0, S obtains VU. VU is then sorted in ascending order and is represented as VU=u1,u2,⋯,uqStep 7.
(a)
S uses VU to construct an adjacency matrix A of size q×q, where q is the number of vertex in VU:(7)A=a1,1⋯a1,q⋮⋱⋮aq,1⋯aq,q.
A has the property that, for each vertex pair ux∈VU and uy∈VU, if an edge exists in GS between vertices ux and uy, ax,y=1; otherwise, ax,y=0(b)
S encrypts each element in A under the Paillier cryptosystem and sends the encrypted matrix A⊕ and VU to CStep 8.
(a)
C uses VU to construct an adjacency matrix B in the same manner as S in the last step:(8)B=b1,1⋯b1,q⋮⋱⋮bq,1⋯bq,q(b)
C encrypts each element in B using the Paillier cryptosystem and obtains B⊕(c)
C generates a matrix R with q×q random values:(9)R=r1,1⋯r1,q⋮⋱⋮rq,1⋯rq,q(d)
C computes:(10)EU⊕=A⊕⊕B⊕⊗R=a1,1⊕⊕b1,1⊕⊗r1,1⋯a1,q⊕⊕b1,q⊕⊗r1,q⋮⋱⋮aq,1⊕⊕bq,1⊕⊗rq,1⋯aq,q⊕⊕bq,q⊕⊗rq,q=e1,1⊕⋯e1,q⊕⋮⋱⋮eq,1⊕⋯eq,q⊕(e)
C cends EU⊕ to SStep 9.
S decrypts the matrix EU⊕. For each decrypted element ei,j, if ei,j≠0, set ei,j=1. At last, S obtains EU.


## 6. Analysis

### 6.1. Security Analysis

In this section, we prove the correctness and security of both PGI and PGU. When analyzing the security of the proposed protocols, we assume both the server and the client evaluate the protocols faithfully, but they may try to obtain as much information about the graph of the other party as possible. The security analysis for the protocols is divided into two cases, where one of the server and the client acts as the adversary in each case. Then, we prove the zero-knowledge properties of the server and the client in each case, using the methods and techniques introduced in [15, 34].Lemma 5 (PGI correctness).
If both participants are honest, for anyGS=VS,ES and any GC=VC,EC, the private graph intersection protocol computes GI=VI,EI=GS⋂GC.Proof.
The correctness of PGI is ensured by the correctness of the FNP protocol and the homomorphic property of the Paillier cryptosystem.During Steps2 to 4 of the protocol, the client and the server jointly perform a FNP protocol using their vertex collections as inputs. At the end of Step 4, the server learns the vertex intersection VI, and the client receives VI from the server in Step 5.In Steps5 and 6, the server and the client construct two adjacency matrices by using VI, denoted as A and B, respectively. Note that A and B contain the adjacency relations between the vertices in VI for graphs GS and GC, respectively. In other words, if an edge exists between two vertices in VI, it leads to a value of 1 in the corresponding position of the constructed adjacency matrix; otherwise, it leads to a value of 0 instead. Therefore, the dot product of A and B will produce an adjacency matrix that represents the edge intersection. If an edge exists in both A and B, i.e., it is a common edge between GS and GC, the dot product of its adjacency relations will result a value of 1. If an edge only exists in one of GS and GC, or the edge does not exist at all, the dot product will result in a value of 0.In Step6, the client receives the encryption of A under the Paillier cryptosystem from the server. If the Paillier cryptosystem has the homomorphic property, i.e., it supports multiplication between a ciphertext and a constant, the client can homomorphically compute the dot product of the A⊕ and B, and the result is the encryption of the edge intersection. Finally, in Step 7, the server obtains the edge intersection after decryption.As a result, if the FNP protocol is correct and the Paillier cryptosystem has the homomorphic property, the private graph intersection protocol computesGI=VI,EI=GS⋂GC.Lemma 6 (PGI server zero-knowledge).
A semihonest server learns nothing about the client’s graph, beyond what can be deduced fromGI and the leakage function L1.Proof.
The proof of PGI server zero-knowledge is trivial. During PGI, there are two parts where the server receives information about the client’s graph. The first part is during the FNP protocol in Step3, and the second part is at the end of Step 6.For the first part, in Step3, the server receives a set of ciphertexts from the client. The server can learn the number of vertices in the client’s graph by counting the number of ciphertexts, which is the predefined leakage function L1. By decrypting the ciphertexts, the server obtains a set of values. If a value exists in VS, it is a common vertex between GS and GC, which is a part of the final result of the protocol. Otherwise, if the value does not exist in VS, it will be a random value, which has no relation to the client’s graph.For the second part, the server receivesEI⊕ from the client, which is the ciphertext of the edge intersection. Upon decryption, the server only learns the edge intersection. As a result, the PGI server zero-knowledge holds.Lemma 7 (PGI client zero-knowledge).
A semihonest client learns nothing about the server’s graph, beyond the leakage functionL2.Proof.
There are two parts where the client receives information about the server’s graph. The first part is during the FNP protocol in Step2, and the second part is at the end of Step 5.For the first part, the client receives a set of encrypted coefficientsα⊕ of the polynomial P from the server. The client can learn the number of vertices of the server’s graph by counting the number of encrypted coefficients received, which is a part of the predefined leakage function L2.For the second part, the client receives an encrypted matrixA⊕ and the vertex intersection VI. Since VI is also a part of the predefined leakage function L2, we need to show that A⊕ does not reveal any information about the server’s graph. According to the protocol construction, A⊕ contains the encryptions of adjacency relations between the vertices in VI for the server’s graph. Therefore, if the client cannot distinguish between the cases where the server has different input graphs, given the knowledge of A⊕ and VI, the PGI client zero-knowledge holds. Consider the following experiment:
(11)EXPA1k,G0,G1←A,b←$0,1,pk,sk←Step11k,α⊕←Step2Gb,pk,β⊕←Step3α⊕,GC,VI←Step4β⊕,sk,A⊕←Step5Gb,VI,pk,b^←Aα⊕,VI,A⊕ifb^=b,output1,otherwise,output0.In the above experiment,A is a probabilistic polynomial-time adversarial client with a private graph GC=EC,VC. The adversary first chooses two graphs, denoted as G0=V0,E0 and G1=V1,E1, respectively. The two graphs have the property that V0⋂VC=V1⋂VC and ∣V0∣=∣V1∣. A then sends the graphs to the server. The server randomly picks a bit b=0,1, and chooses Gb as the private graph. After that, the server and A jointly perform the private graph intersection protocol from Steps 1 to 5.At the end of Step5, A needs to output a bit b^, using the information he recevied during the protocol. If b^=b, the experiment outputs 1; otherwise, it outputs 0. The advantage of the above experiment for A is defined as AdvA=PrEXPA1k=1−1/2.During PGI, the information thatA receives contains α⊕, VI, and A⊕. α⊕ contains a set of ciphertexts under the Paillier cryptosystem, VI is the vertex intersection, and A⊕ is an encrypted adjacency matrix under the Paillier cryptosystem.Due to the conditionV0⋂VC=V1⋂VC, the vertex intersection VI gives no useful information since VI will be the same for both G0 and G1. Since the Paillier cryptosystem is IND-CPA secure and A cannot decrypt the ciphertexts without the private key, α⊕ and A⊕ cannot help A to distinguish which graph the server has chosen. As a result, if the Paillier cryptosystem is IND-CPA secure, the advantage of the above experiment for A is negligible, i.e., AdvA=PrEXPA1k=1−1/2=ε, where ε is negligible.At last, we construct a simulatorSimS to simulate the view of the client in the ideal model. SimS is given the knowledge of the vertex intersection VI and the vertex number m of the server’s graph. In the above experiment, SimS sends a set of m+1 random values to the client in Step 2 and sends VI and a matrix with p×p random values to the client in Step 5. Since the client cannot distinguish between the ciphertexts under the Paillier cryptosystem and random values, the view of the client in the ideal model is computationally indistinguishable from the view in the real model, i.e., ViewCrealSGS,C≈ViewCidealSimSVI,m,C. As a result, the PGI client zero-knowledge holds.Lemma 8 (PGU correctness).
If both participants are honest, for anyGS=VS,ES and any GC=VC,EC, the private graph union protocol computes GU=VU,EU=GS⋃GC.Proof.
The correctness of PGU is ensured by the homomorphic property of the Paillier cryptosystem. Steps2– of PGU compute the vertex union, and Steps 7–9 compute the edge union.In order to compute the vertex union betweenGS and GC, the server needs to obtain the vertices in GC that are not in GS.In Step2, the server constructs a polynomial, such that all the roots are exactly the vertices in GS. After that, the client homomorphically evaluates the polynomial using all the vertices in GC, and each polynomial evaluation is homomorphically multiplied by a random value. Therefore, the common vertices between GS and GC will result in encryptions of zero, and other vertices will result in encryptions of random values. In Step 4, the server decrypts all the polynomial evaluations. If the decryption is zero, the server generates an encryption of 0; otherwise, the server generates an encryption of 1. In the next step, the client homomorphically multiplies the received encryptions with the vertices in VC. For an encryption of 0, i.e., the vertex is a common vertex, the client will result in an encryption of 0; for an encryption of 1, i.e., the vertex is not a common vertex, the client will result in an encryption of the vertex. As a result, in Step 6, the server learns the set of vertices that only exists in GC. By combing the above set and VS, the server obtains the vertex union VU.In order to compute the edge union, the server needs to obtain an adjacency matrix, such that if an edge does not exist in eitherGS and GC, it will have a corresponding value of 0 in the matrix; otherwise, it will have a corresponding value of 1.In Steps7 and 8, each of the server and the client constructs an adjacency matrix using the vertex union and his own graph and encrypts each element under the Paillier cryptosystem. The client then homomorphically adds the encrypted values at the same locations in the two matrices. There are three circumstances for the addition results. If an edge does not exist in either of the graphs, the addition will result in an encryption of 0; if an edge only exists in one of the graphs, the addition will result in an encryption of 1; if an edge exists in both of the graphs, the addition will result in an encryption of 2. Then, the client homomorphically multiplies each result by a random value. Therefore, for the edges that do not exist in either of the graphs, the final result will still be an encryption of 0; for the edges that only exist in one of the graphs and the edges that exist in both of the graphs, the final result will be encryptions of random values. Finally, in Step 9, the server decrypts the encrypted matrix and replaces all the nonzero values to 1, which is the edge union of GS and GC.As a result, if the Paillier cryptosystem has the homomorphic property, the private graph union protocol computesGU=VU,EU=GS⋃GC.Lemma 9 (PGU server zero-knowledge).
A semihonest server learns nothing about the client’s graph, beyond what can be deduced fromGU and the leakage function L3.Proof.
There are three parts where the server receives information from the client, which are Steps3, 5, and 8.In Step3, the server receives a set of ciphertexts, β⊕, from the client. Each vertex in VC has a corresponding ciphertext in β⊕. If a vertex in VC also exists in VS, i.e., it is a common vertex in both graphs, it will result in an encryption of 0; otherwise, it will result in an encryption of a random value. By counting the number of ciphertexts in β⊕, the server can learn the number of vertices in the client’s graph, and by decrypting and counting the number of 0 s, the server can learn the number of common vertices. The above information is defined as leakage function L3.In Step5, the server receives another set of ciphertexts, γ⊕, from the client. Similar as above, each vertex in VC has a corresponding ciphertext in γ⊕. If a vertex exists in both VS and VC, it will result in an encryption of 0; otherwise, it will result in an encryption of the vertex itself. Therefore, upon decryption, the server learns of the vertices in VC that do not exist in VS, which are a part of the vertex union.In Step8, the server receives an encrypted matrix, EU⊕, from the client. Each element of the matrix represents the adjacency relation between two vertices in the graph union. If an edge exists in at least one of the input graphs, the corresponding adjacency value will be a random number; if an edge does not exist in either of the input graphs, it will result in an adjacency value of 0. By decrypting the matrix and replacing the random values to 1, the server obtains the edge union. As a result, the PGU server zero-knowledge holds.Lemma 10 (PGU client zero-knowledge).
A semihonest client learns nothing about the server’s graph, beyond what can be deduced fromVU and the leakage function L4.Proof.
There are three parts where the client receives information from the server, which are Steps2, 4, and 7. In Step 2, the client receives a set α⊕ that contains m+1 ciphertexts under the Paillier cryptosystem, which are encryptions of the coefficients of the server’s polynomial. The client can learn the vertex number of the server’s graph by counting the ciphertexts in α⊕, which is the leakage function L4. In Step 4, the client receives another set of ciphertexts γ⊕, which contains n encryptions of 1 s and 0 s. In Step 7, the client receives an encrypted matrix of size q×q, which contains encryptions of 1 s and 0 s. In order to prove that the above information does not reveal anything about the server’s graph beyond what can be deduced from VU and the leakage function L4, consider the following experiment:
(12)EXPA1k,G0,G1←A,b←$0,1,pk,sk←Step11k,α⊕←Step2Gb,pk,β⊕←Step3α⊕,GC,γ⊕←Step4β⊕,pk,sk,δ⊕←Step5γ⊕,GC,VU←Step6δ⊕,sk,Gb,A⊕←Step7Gb,VU,pk,b^←Aα⊕,γ⊕,A⊕,VU,ifb^=b,output1,otherwise,output0.
In the above experiment,A is a probabilistic polynomial-time adversarial client with a private graph GC=EC,VC. The adversary first chooses two graphs, denoted as G0=V0,E0 and G1=V1,E1, respectively. The two graphs have the property that V0⋃VC=V1⋃VC and ∣V0∣=∣V1∣. A then sends the graphs to the server. The server randomly picks a bit b=0,1 and chooses Gb as the private graph. After that, the server and A jointly perform the private graph union protocol from Steps 1 to 7.At the end of Step7, A needs to output a bit b^, using the information he received during the protocol. If b^=b, the experiment outputs 1; otherwise, it outputs 0. The advantage of the above experiment for A is defined as AdvA=PrEXPA1k=1−1/2.During PGU, the information thatA receives contains α⊕,γ⊕,A⊕, and VU. α⊕ and γ⊕ are both sets of ciphertexts under the Paillier cryptosystem. Since G0 and G1 satisfied the condition ∣V0∣=∣V1∣, the numbers of ciphertexts in α⊕ will be the same for both G0 and G1. A⊕ is a matrix filled with q×q ciphertexts. Since the Paillier cryptosystem is IND-CPA secure and A cannot decrypt the ciphertexts without the private key, α⊕, γ⊕, and A⊕ cannot help A to distinguish which graph the server has chosen. Furthermore, since G0 and G1 satisfied the condition V0⋃VC=V1⋃VC, VU will be the same for both G0 and G1. As a result, if the Paillier cryptosystem is IND-CPA secure, the advantage of the above experiment for A is negligible, i.e., AdvA=PrEXPA1k=1−1/2=ε, where ε is negligible.At last, we construct a simulatorSimS to simulate the view of the client in the ideal model. SimS is given the knowledge of the vertex union VU and the vertex number m of the server’s graph. In the ideal model, SimS genereates a set of m+1 random values in Step 2, a set of n random values in Step 4, and a matrix of size q×q filled with random values in Step 7. Since the Paillier cryptosystem is IND-CPA secure, the client cannot distinguish the ciphertexts and random values. Therefore, the view of the client in the ideal model is computationally indistinguishable from the view in the real model, i.e., ViewCrealSGS,C≈ViewCidealSimSVU,m,C. As a result, the PGU client zero-knowledge holds.


### 6.2. Efficiency Analysis

In this section, we analyze the efficiencies of PGI and PGU in terms of communication cost and computation cost. The communication cost is measured in terms of the amount of ciphertexts that has been transferred between the server and the client, and the computation cost is measured in terms of modular exponentiations and multiplications.We denotem as the number of vertices in GS, n as the number of vertices in GC, p as the number of vertices in the intersection of GS and GC, and q as the number of vertices in the union of GS and GC.


#### 6.2.1. PGI Communication Cost

The construction of PGI is simple and only requiresO1 rounds of communication. In Step 2, the server sends m+1 ciphertexts to the client. In Step 3, the client sends n ciphertexts to the server. In Step 5, the server sends p2 ciphertexts to the client. At last, in Step 6, the client sends p2 ciphertexts to the server. As a result, the total communication cost of our protocol is Om+n+p2 ciphertexts.


#### 6.2.2. PGI Server Computation Cost

In Step2, constructing the polynomial requires Om2 modular multiplication, and encrypting the coefficients requires Om modular exponentiations. In Step 4, decrypting the received ciphertexts requires On modular exponentiations. In Step 5, encrypting each element in A requires Op2 modular exponentiations. In Step 7, decrypting each element in EI⊕ requires Op2 exponentiations. As a result, the total computation cost for the server is Om+n+p2 modular exponentiations and Om2 modular multiplications.


#### 6.2.3. PGI Client Computation Cost

In Step3, obliviously evaluating the polynomial requires Omn modular exponentiations. In Step 6, computing EI⊕ requires Op2 modular exponentiations. As a result, the total computation cost for the client is Omn+p2 modular exponentiations.


#### 6.2.4. PGU Communication Cost

The construction of PGU also only requiresO1 rounds of communication. During Steps 2–5, the server sends m+1+n ciphertexts to the client, and the client sends 2n ciphertexts to the server. During Steps 7 and 8, the server sends q2 ciphertexts to the client, and the client sends q2 ciphertexts to the server. As a result, the total communication cost is Om+n+q2 ciphertexts.


#### 6.2.5. PGU Server Computation Cost

In Step2, constructing the polynomial requires Om2 modular multiplication, and encrypting the coefficients requires Om modular exponentiations. In Step 4, decrypting n ciphertexts requires On modular exponentiations, and encrypting n ciphertexts requires On modular exponentiations. In Step 6, decrypting n ciphertexts requires On modular exponentiations. In Step 7, encrypting each element in A requires Oq2 modular exponentiations. In Step 9, decrypting each element in EU⊕ requires Oq2 modular exponentiations. As a result, the total computation cost for the server is Om+n+q2 modular exponentiations and Om2 modular multiplications.


#### 6.2.6. PGU Client Computation Cost

In Step3, obliviously evaluating the polynomial requires Omn modular exponentiations. Computing n homomorphic multiplication requires On modular exponentiations. In Step 5, computing n homomorphic multiplication requires On modular exponentiations. In Step 8, encrypting the each element in B requires Oq2 modular exponentiations. Computing q2 homomorphic addition and multiplication requires Oq2 modular exponentiations and Oq2 modular multiplication. As a result, the total computation cost for the client is Omn+q2 modular exponentiations and Oq2 modular multiplications.


### 6.3. Leakage Analysis

#### 6.3.1. PGI Leakage

As stated before, the proposed PGI leaks certain information about the private graphs, which is modeled as the leakage functionsL1 and L2. There are several techniques that can be used to reduce the amount of information leakage; however, it cannot be completely avoided.In Step2, the server constructs a polynomial P, such that all the roots of Px are exactly the elements in VS. After that, the server sends the encryptions of the coefficients of P to the client. In order to prevent the client from learning the exact vertex number of the server’s graph, the server first randomly constructs an irreducible polynomial Rx with degree d. The server then computes P′x=PxRx and uses P′x instead of Px in Step 2. The polynomial P′x has the same property as Px; therefore, it will not affect the result of the protocol. As a result, by counting the number of ciphertexts received, the client can only learn the upper bound of the vertex number of the server’s graph, i.e., m+d.In order to hide the exact vertex number of the client’s graph, the client can randomly generate a set ofh values from the message space of the Paillier cryptosystem in Step 3. After that, the client encrypts the random values and sends the encrypted random set to the server along with β⊕. Since the message space of the Paillier cryptosystem is large enough, the probability that a random value equals to an element in VS can be assumed as negligible. Therefore, the random values will not affect the result of the protocol, since they are not in the vertex intersection. As a result, by counting the number ciphertexts received in Step 3, the server can only learn the upper bound of the vertex number of the client’s graph, i.e., n+h.


#### 6.3.2. PGU Leakage

Similar as PGI, PGU also leaks partial information about the input graphs during the process, which is modeled asL3 and L4.In Step2, the server can utilize the same technique, as introduced above, to hide the exact vertex number of his graph, and the client can only learn the upper bound instead, i.e., m+d.In Step3, in order to hide the exact vertex number of the client’s graph, the client generates k encryptions of zero and sends the ciphertexts along with β⊕. An encryption of zero in Step 3 indicates that a vertex in the client’s graph also exists in the server’s graph. In later steps, extra encryptions of zero will not affect the final result, since the vertex union between the two input graphs will remain the same. As a result, the server can only learn the upper bound of the vertex number of the client’s graph, i.e., n+k, and the upper bound of the common vertex number, i.e., p+k.In addition, we consider the case where the server sends a graph with small size to the client in Step2. If the server’s graph is small enough, i.e., only 1 vertex and no edge, the union of the graphs will be almost the graph of the client. To prevent the server from learning the client’s graph in such a method, there are two points where the client can choose to end the protocol.The first point is at Step3. If the client receives a very small polynomial, the client can choose to end the protocol, and at this point, the server has not learned anything yet. However, if the server uses the technique stated above, the polynomial that the client receives will not give the exact size of the server’s graph. In this case, the client can check if the vertex union received in Step 8 is almost the same as his vertex set VC. If VU≈VC, it means either the server has a very small graph or the vertices in both graphs are highly overlapping. At this point, the client can choose to end the protocol; however, the server has already learned the vertex set of the client.


## 6.1. Security Analysis

In this section, we prove the correctness and security of both PGI and PGU. When analyzing the security of the proposed protocols, we assume both the server and the client evaluate the protocols faithfully, but they may try to obtain as much information about the graph of the other party as possible. The security analysis for the protocols is divided into two cases, where one of the server and the client acts as the adversary in each case. Then, we prove the zero-knowledge properties of the server and the client in each case, using the methods and techniques introduced in [15, 34].Lemma 5 (PGI correctness).
If both participants are honest, for anyGS=VS,ES and any GC=VC,EC, the private graph intersection protocol computes GI=VI,EI=GS⋂GC.Proof.
The correctness of PGI is ensured by the correctness of the FNP protocol and the homomorphic property of the Paillier cryptosystem.During Steps2 to 4 of the protocol, the client and the server jointly perform a FNP protocol using their vertex collections as inputs. At the end of Step 4, the server learns the vertex intersection VI, and the client receives VI from the server in Step 5.In Steps5 and 6, the server and the client construct two adjacency matrices by using VI, denoted as A and B, respectively. Note that A and B contain the adjacency relations between the vertices in VI for graphs GS and GC, respectively. In other words, if an edge exists between two vertices in VI, it leads to a value of 1 in the corresponding position of the constructed adjacency matrix; otherwise, it leads to a value of 0 instead. Therefore, the dot product of A and B will produce an adjacency matrix that represents the edge intersection. If an edge exists in both A and B, i.e., it is a common edge between GS and GC, the dot product of its adjacency relations will result a value of 1. If an edge only exists in one of GS and GC, or the edge does not exist at all, the dot product will result in a value of 0.In Step6, the client receives the encryption of A under the Paillier cryptosystem from the server. If the Paillier cryptosystem has the homomorphic property, i.e., it supports multiplication between a ciphertext and a constant, the client can homomorphically compute the dot product of the A⊕ and B, and the result is the encryption of the edge intersection. Finally, in Step 7, the server obtains the edge intersection after decryption.As a result, if the FNP protocol is correct and the Paillier cryptosystem has the homomorphic property, the private graph intersection protocol computesGI=VI,EI=GS⋂GC.Lemma 6 (PGI server zero-knowledge).
A semihonest server learns nothing about the client’s graph, beyond what can be deduced fromGI and the leakage function L1.Proof.
The proof of PGI server zero-knowledge is trivial. During PGI, there are two parts where the server receives information about the client’s graph. The first part is during the FNP protocol in Step3, and the second part is at the end of Step 6.For the first part, in Step3, the server receives a set of ciphertexts from the client. The server can learn the number of vertices in the client’s graph by counting the number of ciphertexts, which is the predefined leakage function L1. By decrypting the ciphertexts, the server obtains a set of values. If a value exists in VS, it is a common vertex between GS and GC, which is a part of the final result of the protocol. Otherwise, if the value does not exist in VS, it will be a random value, which has no relation to the client’s graph.For the second part, the server receivesEI⊕ from the client, which is the ciphertext of the edge intersection. Upon decryption, the server only learns the edge intersection. As a result, the PGI server zero-knowledge holds.Lemma 7 (PGI client zero-knowledge).
A semihonest client learns nothing about the server’s graph, beyond the leakage functionL2.Proof.
There are two parts where the client receives information about the server’s graph. The first part is during the FNP protocol in Step2, and the second part is at the end of Step 5.For the first part, the client receives a set of encrypted coefficientsα⊕ of the polynomial P from the server. The client can learn the number of vertices of the server’s graph by counting the number of encrypted coefficients received, which is a part of the predefined leakage function L2.For the second part, the client receives an encrypted matrixA⊕ and the vertex intersection VI. Since VI is also a part of the predefined leakage function L2, we need to show that A⊕ does not reveal any information about the server’s graph. According to the protocol construction, A⊕ contains the encryptions of adjacency relations between the vertices in VI for the server’s graph. Therefore, if the client cannot distinguish between the cases where the server has different input graphs, given the knowledge of A⊕ and VI, the PGI client zero-knowledge holds. Consider the following experiment:
(11)EXPA1k,G0,G1←A,b←$0,1,pk,sk←Step11k,α⊕←Step2Gb,pk,β⊕←Step3α⊕,GC,VI←Step4β⊕,sk,A⊕←Step5Gb,VI,pk,b^←Aα⊕,VI,A⊕ifb^=b,output1,otherwise,output0.In the above experiment,A is a probabilistic polynomial-time adversarial client with a private graph GC=EC,VC. The adversary first chooses two graphs, denoted as G0=V0,E0 and G1=V1,E1, respectively. The two graphs have the property that V0⋂VC=V1⋂VC and ∣V0∣=∣V1∣. A then sends the graphs to the server. The server randomly picks a bit b=0,1, and chooses Gb as the private graph. After that, the server and A jointly perform the private graph intersection protocol from Steps 1 to 5.At the end of Step5, A needs to output a bit b^, using the information he recevied during the protocol. If b^=b, the experiment outputs 1; otherwise, it outputs 0. The advantage of the above experiment for A is defined as AdvA=PrEXPA1k=1−1/2.During PGI, the information thatA receives contains α⊕, VI, and A⊕. α⊕ contains a set of ciphertexts under the Paillier cryptosystem, VI is the vertex intersection, and A⊕ is an encrypted adjacency matrix under the Paillier cryptosystem.Due to the conditionV0⋂VC=V1⋂VC, the vertex intersection VI gives no useful information since VI will be the same for both G0 and G1. Since the Paillier cryptosystem is IND-CPA secure and A cannot decrypt the ciphertexts without the private key, α⊕ and A⊕ cannot help A to distinguish which graph the server has chosen. As a result, if the Paillier cryptosystem is IND-CPA secure, the advantage of the above experiment for A is negligible, i.e., AdvA=PrEXPA1k=1−1/2=ε, where ε is negligible.At last, we construct a simulatorSimS to simulate the view of the client in the ideal model. SimS is given the knowledge of the vertex intersection VI and the vertex number m of the server’s graph. In the above experiment, SimS sends a set of m+1 random values to the client in Step 2 and sends VI and a matrix with p×p random values to the client in Step 5. Since the client cannot distinguish between the ciphertexts under the Paillier cryptosystem and random values, the view of the client in the ideal model is computationally indistinguishable from the view in the real model, i.e., ViewCrealSGS,C≈ViewCidealSimSVI,m,C. As a result, the PGI client zero-knowledge holds.Lemma 8 (PGU correctness).
If both participants are honest, for anyGS=VS,ES and any GC=VC,EC, the private graph union protocol computes GU=VU,EU=GS⋃GC.Proof.
The correctness of PGU is ensured by the homomorphic property of the Paillier cryptosystem. Steps2– of PGU compute the vertex union, and Steps 7–9 compute the edge union.In order to compute the vertex union betweenGS and GC, the server needs to obtain the vertices in GC that are not in GS.In Step2, the server constructs a polynomial, such that all the roots are exactly the vertices in GS. After that, the client homomorphically evaluates the polynomial using all the vertices in GC, and each polynomial evaluation is homomorphically multiplied by a random value. Therefore, the common vertices between GS and GC will result in encryptions of zero, and other vertices will result in encryptions of random values. In Step 4, the server decrypts all the polynomial evaluations. If the decryption is zero, the server generates an encryption of 0; otherwise, the server generates an encryption of 1. In the next step, the client homomorphically multiplies the received encryptions with the vertices in VC. For an encryption of 0, i.e., the vertex is a common vertex, the client will result in an encryption of 0; for an encryption of 1, i.e., the vertex is not a common vertex, the client will result in an encryption of the vertex. As a result, in Step 6, the server learns the set of vertices that only exists in GC. By combing the above set and VS, the server obtains the vertex union VU.In order to compute the edge union, the server needs to obtain an adjacency matrix, such that if an edge does not exist in eitherGS and GC, it will have a corresponding value of 0 in the matrix; otherwise, it will have a corresponding value of 1.In Steps7 and 8, each of the server and the client constructs an adjacency matrix using the vertex union and his own graph and encrypts each element under the Paillier cryptosystem. The client then homomorphically adds the encrypted values at the same locations in the two matrices. There are three circumstances for the addition results. If an edge does not exist in either of the graphs, the addition will result in an encryption of 0; if an edge only exists in one of the graphs, the addition will result in an encryption of 1; if an edge exists in both of the graphs, the addition will result in an encryption of 2. Then, the client homomorphically multiplies each result by a random value. Therefore, for the edges that do not exist in either of the graphs, the final result will still be an encryption of 0; for the edges that only exist in one of the graphs and the edges that exist in both of the graphs, the final result will be encryptions of random values. Finally, in Step 9, the server decrypts the encrypted matrix and replaces all the nonzero values to 1, which is the edge union of GS and GC.As a result, if the Paillier cryptosystem has the homomorphic property, the private graph union protocol computesGU=VU,EU=GS⋃GC.Lemma 9 (PGU server zero-knowledge).
A semihonest server learns nothing about the client’s graph, beyond what can be deduced fromGU and the leakage function L3.Proof.
There are three parts where the server receives information from the client, which are Steps3, 5, and 8.In Step3, the server receives a set of ciphertexts, β⊕, from the client. Each vertex in VC has a corresponding ciphertext in β⊕. If a vertex in VC also exists in VS, i.e., it is a common vertex in both graphs, it will result in an encryption of 0; otherwise, it will result in an encryption of a random value. By counting the number of ciphertexts in β⊕, the server can learn the number of vertices in the client’s graph, and by decrypting and counting the number of 0 s, the server can learn the number of common vertices. The above information is defined as leakage function L3.In Step5, the server receives another set of ciphertexts, γ⊕, from the client. Similar as above, each vertex in VC has a corresponding ciphertext in γ⊕. If a vertex exists in both VS and VC, it will result in an encryption of 0; otherwise, it will result in an encryption of the vertex itself. Therefore, upon decryption, the server learns of the vertices in VC that do not exist in VS, which are a part of the vertex union.In Step8, the server receives an encrypted matrix, EU⊕, from the client. Each element of the matrix represents the adjacency relation between two vertices in the graph union. If an edge exists in at least one of the input graphs, the corresponding adjacency value will be a random number; if an edge does not exist in either of the input graphs, it will result in an adjacency value of 0. By decrypting the matrix and replacing the random values to 1, the server obtains the edge union. As a result, the PGU server zero-knowledge holds.Lemma 10 (PGU client zero-knowledge).
A semihonest client learns nothing about the server’s graph, beyond what can be deduced fromVU and the leakage function L4.Proof.
There are three parts where the client receives information from the server, which are Steps2, 4, and 7. In Step 2, the client receives a set α⊕ that contains m+1 ciphertexts under the Paillier cryptosystem, which are encryptions of the coefficients of the server’s polynomial. The client can learn the vertex number of the server’s graph by counting the ciphertexts in α⊕, which is the leakage function L4. In Step 4, the client receives another set of ciphertexts γ⊕, which contains n encryptions of 1 s and 0 s. In Step 7, the client receives an encrypted matrix of size q×q, which contains encryptions of 1 s and 0 s. In order to prove that the above information does not reveal anything about the server’s graph beyond what can be deduced from VU and the leakage function L4, consider the following experiment:
(12)EXPA1k,G0,G1←A,b←$0,1,pk,sk←Step11k,α⊕←Step2Gb,pk,β⊕←Step3α⊕,GC,γ⊕←Step4β⊕,pk,sk,δ⊕←Step5γ⊕,GC,VU←Step6δ⊕,sk,Gb,A⊕←Step7Gb,VU,pk,b^←Aα⊕,γ⊕,A⊕,VU,ifb^=b,output1,otherwise,output0.
In the above experiment,A is a probabilistic polynomial-time adversarial client with a private graph GC=EC,VC. The adversary first chooses two graphs, denoted as G0=V0,E0 and G1=V1,E1, respectively. The two graphs have the property that V0⋃VC=V1⋃VC and ∣V0∣=∣V1∣. A then sends the graphs to the server. The server randomly picks a bit b=0,1 and chooses Gb as the private graph. After that, the server and A jointly perform the private graph union protocol from Steps 1 to 7.At the end of Step7, A needs to output a bit b^, using the information he received during the protocol. If b^=b, the experiment outputs 1; otherwise, it outputs 0. The advantage of the above experiment for A is defined as AdvA=PrEXPA1k=1−1/2.During PGU, the information thatA receives contains α⊕,γ⊕,A⊕, and VU. α⊕ and γ⊕ are both sets of ciphertexts under the Paillier cryptosystem. Since G0 and G1 satisfied the condition ∣V0∣=∣V1∣, the numbers of ciphertexts in α⊕ will be the same for both G0 and G1. A⊕ is a matrix filled with q×q ciphertexts. Since the Paillier cryptosystem is IND-CPA secure and A cannot decrypt the ciphertexts without the private key, α⊕, γ⊕, and A⊕ cannot help A to distinguish which graph the server has chosen. Furthermore, since G0 and G1 satisfied the condition V0⋃VC=V1⋃VC, VU will be the same for both G0 and G1. As a result, if the Paillier cryptosystem is IND-CPA secure, the advantage of the above experiment for A is negligible, i.e., AdvA=PrEXPA1k=1−1/2=ε, where ε is negligible.At last, we construct a simulatorSimS to simulate the view of the client in the ideal model. SimS is given the knowledge of the vertex union VU and the vertex number m of the server’s graph. In the ideal model, SimS genereates a set of m+1 random values in Step 2, a set of n random values in Step 4, and a matrix of size q×q filled with random values in Step 7. Since the Paillier cryptosystem is IND-CPA secure, the client cannot distinguish the ciphertexts and random values. Therefore, the view of the client in the ideal model is computationally indistinguishable from the view in the real model, i.e., ViewCrealSGS,C≈ViewCidealSimSVU,m,C. As a result, the PGU client zero-knowledge holds.


## 6.2. Efficiency Analysis

In this section, we analyze the efficiencies of PGI and PGU in terms of communication cost and computation cost. The communication cost is measured in terms of the amount of ciphertexts that has been transferred between the server and the client, and the computation cost is measured in terms of modular exponentiations and multiplications.We denotem as the number of vertices in GS, n as the number of vertices in GC, p as the number of vertices in the intersection of GS and GC, and q as the number of vertices in the union of GS and GC.


### 6.2.1. PGI Communication Cost

The construction of PGI is simple and only requiresO1 rounds of communication. In Step 2, the server sends m+1 ciphertexts to the client. In Step 3, the client sends n ciphertexts to the server. In Step 5, the server sends p2 ciphertexts to the client. At last, in Step 6, the client sends p2 ciphertexts to the server. As a result, the total communication cost of our protocol is Om+n+p2 ciphertexts.


### 6.2.2. PGI Server Computation Cost

In Step2, constructing the polynomial requires Om2 modular multiplication, and encrypting the coefficients requires Om modular exponentiations. In Step 4, decrypting the received ciphertexts requires On modular exponentiations. In Step 5, encrypting each element in A requires Op2 modular exponentiations. In Step 7, decrypting each element in EI⊕ requires Op2 exponentiations. As a result, the total computation cost for the server is Om+n+p2 modular exponentiations and Om2 modular multiplications.


### 6.2.3. PGI Client Computation Cost

In Step3, obliviously evaluating the polynomial requires Omn modular exponentiations. In Step 6, computing EI⊕ requires Op2 modular exponentiations. As a result, the total computation cost for the client is Omn+p2 modular exponentiations.


### 6.2.4. PGU Communication Cost

The construction of PGU also only requiresO1 rounds of communication. During Steps 2–5, the server sends m+1+n ciphertexts to the client, and the client sends 2n ciphertexts to the server. During Steps 7 and 8, the server sends q2 ciphertexts to the client, and the client sends q2 ciphertexts to the server. As a result, the total communication cost is Om+n+q2 ciphertexts.


### 6.2.5. PGU Server Computation Cost

In Step2, constructing the polynomial requires Om2 modular multiplication, and encrypting the coefficients requires Om modular exponentiations. In Step 4, decrypting n ciphertexts requires On modular exponentiations, and encrypting n ciphertexts requires On modular exponentiations. In Step 6, decrypting n ciphertexts requires On modular exponentiations. In Step 7, encrypting each element in A requires Oq2 modular exponentiations. In Step 9, decrypting each element in EU⊕ requires Oq2 modular exponentiations. As a result, the total computation cost for the server is Om+n+q2 modular exponentiations and Om2 modular multiplications.


### 6.2.6. PGU Client Computation Cost

In Step3, obliviously evaluating the polynomial requires Omn modular exponentiations. Computing n homomorphic multiplication requires On modular exponentiations. In Step 5, computing n homomorphic multiplication requires On modular exponentiations. In Step 8, encrypting the each element in B requires Oq2 modular exponentiations. Computing q2 homomorphic addition and multiplication requires Oq2 modular exponentiations and Oq2 modular multiplication. As a result, the total computation cost for the client is Omn+q2 modular exponentiations and Oq2 modular multiplications.


## 6.2.1. PGI Communication Cost

The construction of PGI is simple and only requiresO1 rounds of communication. In Step 2, the server sends m+1 ciphertexts to the client. In Step 3, the client sends n ciphertexts to the server. In Step 5, the server sends p2 ciphertexts to the client. At last, in Step 6, the client sends p2 ciphertexts to the server. As a result, the total communication cost of our protocol is Om+n+p2 ciphertexts.


## 6.2.2. PGI Server Computation Cost

In Step2, constructing the polynomial requires Om2 modular multiplication, and encrypting the coefficients requires Om modular exponentiations. In Step 4, decrypting the received ciphertexts requires On modular exponentiations. In Step 5, encrypting each element in A requires Op2 modular exponentiations. In Step 7, decrypting each element in EI⊕ requires Op2 exponentiations. As a result, the total computation cost for the server is Om+n+p2 modular exponentiations and Om2 modular multiplications.


## 6.2.3. PGI Client Computation Cost

In Step3, obliviously evaluating the polynomial requires Omn modular exponentiations. In Step 6, computing EI⊕ requires Op2 modular exponentiations. As a result, the total computation cost for the client is Omn+p2 modular exponentiations.


## 6.2.4. PGU Communication Cost

The construction of PGU also only requiresO1 rounds of communication. During Steps 2–5, the server sends m+1+n ciphertexts to the client, and the client sends 2n ciphertexts to the server. During Steps 7 and 8, the server sends q2 ciphertexts to the client, and the client sends q2 ciphertexts to the server. As a result, the total communication cost is Om+n+q2 ciphertexts.


## 6.2.5. PGU Server Computation Cost

In Step2, constructing the polynomial requires Om2 modular multiplication, and encrypting the coefficients requires Om modular exponentiations. In Step 4, decrypting n ciphertexts requires On modular exponentiations, and encrypting n ciphertexts requires On modular exponentiations. In Step 6, decrypting n ciphertexts requires On modular exponentiations. In Step 7, encrypting each element in A requires Oq2 modular exponentiations. In Step 9, decrypting each element in EU⊕ requires Oq2 modular exponentiations. As a result, the total computation cost for the server is Om+n+q2 modular exponentiations and Om2 modular multiplications.


## 6.2.6. PGU Client Computation Cost

In Step3, obliviously evaluating the polynomial requires Omn modular exponentiations. Computing n homomorphic multiplication requires On modular exponentiations. In Step 5, computing n homomorphic multiplication requires On modular exponentiations. In Step 8, encrypting the each element in B requires Oq2 modular exponentiations. Computing q2 homomorphic addition and multiplication requires Oq2 modular exponentiations and Oq2 modular multiplication. As a result, the total computation cost for the client is Omn+q2 modular exponentiations and Oq2 modular multiplications.


## 6.3. Leakage Analysis

### 6.3.1. PGI Leakage

As stated before, the proposed PGI leaks certain information about the private graphs, which is modeled as the leakage functionsL1 and L2. There are several techniques that can be used to reduce the amount of information leakage; however, it cannot be completely avoided.In Step2, the server constructs a polynomial P, such that all the roots of Px are exactly the elements in VS. After that, the server sends the encryptions of the coefficients of P to the client. In order to prevent the client from learning the exact vertex number of the server’s graph, the server first randomly constructs an irreducible polynomial Rx with degree d. The server then computes P′x=PxRx and uses P′x instead of Px in Step 2. The polynomial P′x has the same property as Px; therefore, it will not affect the result of the protocol. As a result, by counting the number of ciphertexts received, the client can only learn the upper bound of the vertex number of the server’s graph, i.e., m+d.In order to hide the exact vertex number of the client’s graph, the client can randomly generate a set ofh values from the message space of the Paillier cryptosystem in Step 3. After that, the client encrypts the random values and sends the encrypted random set to the server along with β⊕. Since the message space of the Paillier cryptosystem is large enough, the probability that a random value equals to an element in VS can be assumed as negligible. Therefore, the random values will not affect the result of the protocol, since they are not in the vertex intersection. As a result, by counting the number ciphertexts received in Step 3, the server can only learn the upper bound of the vertex number of the client’s graph, i.e., n+h.


### 6.3.2. PGU Leakage

Similar as PGI, PGU also leaks partial information about the input graphs during the process, which is modeled asL3 and L4.In Step2, the server can utilize the same technique, as introduced above, to hide the exact vertex number of his graph, and the client can only learn the upper bound instead, i.e., m+d.In Step3, in order to hide the exact vertex number of the client’s graph, the client generates k encryptions of zero and sends the ciphertexts along with β⊕. An encryption of zero in Step 3 indicates that a vertex in the client’s graph also exists in the server’s graph. In later steps, extra encryptions of zero will not affect the final result, since the vertex union between the two input graphs will remain the same. As a result, the server can only learn the upper bound of the vertex number of the client’s graph, i.e., n+k, and the upper bound of the common vertex number, i.e., p+k.In addition, we consider the case where the server sends a graph with small size to the client in Step2. If the server’s graph is small enough, i.e., only 1 vertex and no edge, the union of the graphs will be almost the graph of the client. To prevent the server from learning the client’s graph in such a method, there are two points where the client can choose to end the protocol.The first point is at Step3. If the client receives a very small polynomial, the client can choose to end the protocol, and at this point, the server has not learned anything yet. However, if the server uses the technique stated above, the polynomial that the client receives will not give the exact size of the server’s graph. In this case, the client can check if the vertex union received in Step 8 is almost the same as his vertex set VC. If VU≈VC, it means either the server has a very small graph or the vertices in both graphs are highly overlapping. At this point, the client can choose to end the protocol; however, the server has already learned the vertex set of the client.


## 6.3.1. PGI Leakage

As stated before, the proposed PGI leaks certain information about the private graphs, which is modeled as the leakage functionsL1 and L2. There are several techniques that can be used to reduce the amount of information leakage; however, it cannot be completely avoided.In Step2, the server constructs a polynomial P, such that all the roots of Px are exactly the elements in VS. After that, the server sends the encryptions of the coefficients of P to the client. In order to prevent the client from learning the exact vertex number of the server’s graph, the server first randomly constructs an irreducible polynomial Rx with degree d. The server then computes P′x=PxRx and uses P′x instead of Px in Step 2. The polynomial P′x has the same property as Px; therefore, it will not affect the result of the protocol. As a result, by counting the number of ciphertexts received, the client can only learn the upper bound of the vertex number of the server’s graph, i.e., m+d.In order to hide the exact vertex number of the client’s graph, the client can randomly generate a set ofh values from the message space of the Paillier cryptosystem in Step 3. After that, the client encrypts the random values and sends the encrypted random set to the server along with β⊕. Since the message space of the Paillier cryptosystem is large enough, the probability that a random value equals to an element in VS can be assumed as negligible. Therefore, the random values will not affect the result of the protocol, since they are not in the vertex intersection. As a result, by counting the number ciphertexts received in Step 3, the server can only learn the upper bound of the vertex number of the client’s graph, i.e., n+h.


## 6.3.2. PGU Leakage

Similar as PGI, PGU also leaks partial information about the input graphs during the process, which is modeled asL3 and L4.In Step2, the server can utilize the same technique, as introduced above, to hide the exact vertex number of his graph, and the client can only learn the upper bound instead, i.e., m+d.In Step3, in order to hide the exact vertex number of the client’s graph, the client generates k encryptions of zero and sends the ciphertexts along with β⊕. An encryption of zero in Step 3 indicates that a vertex in the client’s graph also exists in the server’s graph. In later steps, extra encryptions of zero will not affect the final result, since the vertex union between the two input graphs will remain the same. As a result, the server can only learn the upper bound of the vertex number of the client’s graph, i.e., n+k, and the upper bound of the common vertex number, i.e., p+k.In addition, we consider the case where the server sends a graph with small size to the client in Step2. If the server’s graph is small enough, i.e., only 1 vertex and no edge, the union of the graphs will be almost the graph of the client. To prevent the server from learning the client’s graph in such a method, there are two points where the client can choose to end the protocol.The first point is at Step3. If the client receives a very small polynomial, the client can choose to end the protocol, and at this point, the server has not learned anything yet. However, if the server uses the technique stated above, the polynomial that the client receives will not give the exact size of the server’s graph. In this case, the client can check if the vertex union received in Step 8 is almost the same as his vertex set VC. If VU≈VC, it means either the server has a very small graph or the vertices in both graphs are highly overlapping. At this point, the client can choose to end the protocol; however, the server has already learned the vertex set of the client.


## 7. Experiments

In order to evaluate the performances of the proposed PGI and PGU protocols, we implement the protocols and perform experiments over the Enron email dataset. All the experiments were conducted on two PCs with Intel Core i7-2600 4.2 GHz CPU, 16 GB RAM, and Windows 10 operating system. (Due to the COVID-19 crisis, we cannot access the lab in the university at the moment, which contains the environment and equipment to perform the experiments on real mobile devices. As a result, the experiments are performed on a PC in this paper, and we will improve the experiments on mobile devices in later works.). The protocols are implemented in Python 3.6, and we used the phe library for the Paillier cryptosystem with a 1024-bit key length.


### 7.1. Dataset

The Enron email dataset is publicly available from the Stanford SNAP website (https://snap.stanford.edu/data/). The dataset contains email communications of around half a million emails. In order to convert the dataset to a graph, the senders and the receivers of the emails are represented as vertices, and if vertex i sends at least one email to vertex j, there exists an undirected edge between i and j. The resulting graph has 36,692 vertices and 183,831 edges. In addition, each vertex of the graph is represented as a unique integer.


### 7.2. Evaluation of PGI

When evaluating the performance of PGI, we randomly generate two subgraphs from the Enron email graph dataset and assign them to the server and the client, respectively. For each experiment, we setm and n to have the same value, and they increase from 1,000 to 10,000. Furthermore, the graphs of the server and the client are generated following the rule that 5% of the vertices are the same between the two graphs. Figure 2(a) shows the computation time for the server and the client.Figure 2
Evaluation of private graph intersection protocol.
(a)
Computation time(b)
Communication costAs analyzed before, the computation costs for the server and the client areOm+n+p2 and Omn+p2, respectively, where p is the number of vertices in the intersection of GS and GC. Therefore, the most dominant part of the computation costs for both the server and the client is most likely to be the number of common vertices between GS and GC. As shown in Figure 2(a), the computation time for both the server and the client grows quadratically as the number of common vertices increases. The detailed computation time for each step is shown in Table 2.Table 2
The computation time for each step of private graph intersection protocol.
m/npStep2 time (s)Step3 time (s)Step4 time (s)Step5 time (s)Step6 time (s)Step7 time (s)1,000502.073.261.054.721.041.222,0001003.586.171.9020.265.012.943,0001504.909.792.1248.1616.576.154,0002006.5715.962.6495.9538.4010.495,0002507.9324.423.38164.4762.3214.356,0003008.6832.853.74225.50108.2120.237,00035010.0746.654.70336.07165.5226.878,00040011.1465.605.54449.29262.0836.909,00045013.3596.326.63654.43382.2846.8810,00050015.48130.698.19832.97493.0158.28As shown in Table2, the most time-consuming parts of PGI are Steps 5 and 6. In Step 5, the server performs p2 Paillier encryptions, and in Step 6, the client performs p2 homomorphic multiplications. Since the computations for both Steps 5 and 6 are highly parallelizable, the computation time can be greatly reduced if cluster computing is deployed.The communication costs of PGI for both the server and the client are shown in Figure2(b). As analyzed before, the total communication cost is Om+n+p2. As a result, the communication costs have a quadratic growth in the figure. In addition, the communication costs are nearly the same for both the server and the client, and the overall communication cost for PGI is practical for the experimental dataset.


### 7.3. Evaluation of PGU

When evaluating the performance of PGU, we first randomly generate a subgraph from the Enron email graph dataset as the graph unionGU. Then, we randomly choose two subgraphs of GU and assign them to the server and the client, respectively. The numbers of the vertices in the subgraphs are 60% of the vertex number in GU; therefore, both m and n will have the same value. For each experiment, the number of vertices in GU increases from 50 to 500. Figure 3(a) shows the computation time for the server and the client, and the detailed computation time for each step is shown in Table 3.Figure 3
Evaluation of private graph union protocol.
(a)
Computation Time(b)
Communication CostTable 3
The computation time for each step of private graph union protocol.
m/nqStep2 time (s)Step3 time (s)Step4 time (s)Step5 time (s)Step6 time (s)Step7 time (s)Step8 time (s)Step9 time (s)30500.541.130.520.450.464.105.121.74601000.591.230.500.500.5214.3216.625.43901500.661.320.470.470.5131.1735.6610.941202000.681.260.450.450.5354.9062.1119.251502500.771.300.480.480.5284.5096.9230.051803000.801.320.520.520.65117.55130.7243.262103500.821.380.480.480.63162.46185.1259.092404000.801.480.490.490.65212.23242.7577.692704500.951.590.580.580.65275.12311.5094.983005000.871.520.530.530.63336.23355.94118.34As analyzed before, the computation costs for PGU areOm+n+q2 and Omn+q2 for the server and the client, respectively, where q is the number of vertices in the union of GS and GC. Therefore, similar as PGI, the most dominant part of the computation costs for both the server and the client is most likely to be the number of vertices in GU.As shown in Table3, most of the computation time is spent in Steps 7 and 8. In Step 7, the server performs q2 Paillier encryptions, and in Step 8, the client performs q2 Paillier encryptions and q2 homomorphic additions and multiplications. Similar as before, the above computations are highly parallelizable, and cluster computing will greatly optimize the computation time.As shown in Figure3(b), the communication cost of PGU is similar to PGI, and the communication costs for both the server and the client have a quadratic growth as the number of vertices in GU increases. For our experimental dataset, the overall communication cost for the PGU protocol is also practical.


## 7.1. Dataset

The Enron email dataset is publicly available from the Stanford SNAP website (https://snap.stanford.edu/data/). The dataset contains email communications of around half a million emails. In order to convert the dataset to a graph, the senders and the receivers of the emails are represented as vertices, and if vertex i sends at least one email to vertex j, there exists an undirected edge between i and j. The resulting graph has 36,692 vertices and 183,831 edges. In addition, each vertex of the graph is represented as a unique integer.


## 7.2. Evaluation of PGI

When evaluating the performance of PGI, we randomly generate two subgraphs from the Enron email graph dataset and assign them to the server and the client, respectively. For each experiment, we setm and n to have the same value, and they increase from 1,000 to 10,000. Furthermore, the graphs of the server and the client are generated following the rule that 5% of the vertices are the same between the two graphs. Figure 2(a) shows the computation time for the server and the client.Figure 2
Evaluation of private graph intersection protocol.
(a)
Computation time(b)
Communication costAs analyzed before, the computation costs for the server and the client areOm+n+p2 and Omn+p2, respectively, where p is the number of vertices in the intersection of GS and GC. Therefore, the most dominant part of the computation costs for both the server and the client is most likely to be the number of common vertices between GS and GC. As shown in Figure 2(a), the computation time for both the server and the client grows quadratically as the number of common vertices increases. The detailed computation time for each step is shown in Table 2.Table 2
The computation time for each step of private graph intersection protocol.
m/npStep2 time (s)Step3 time (s)Step4 time (s)Step5 time (s)Step6 time (s)Step7 time (s)1,000502.073.261.054.721.041.222,0001003.586.171.9020.265.012.943,0001504.909.792.1248.1616.576.154,0002006.5715.962.6495.9538.4010.495,0002507.9324.423.38164.4762.3214.356,0003008.6832.853.74225.50108.2120.237,00035010.0746.654.70336.07165.5226.878,00040011.1465.605.54449.29262.0836.909,00045013.3596.326.63654.43382.2846.8810,00050015.48130.698.19832.97493.0158.28As shown in Table2, the most time-consuming parts of PGI are Steps 5 and 6. In Step 5, the server performs p2 Paillier encryptions, and in Step 6, the client performs p2 homomorphic multiplications. Since the computations for both Steps 5 and 6 are highly parallelizable, the computation time can be greatly reduced if cluster computing is deployed.The communication costs of PGI for both the server and the client are shown in Figure2(b). As analyzed before, the total communication cost is Om+n+p2. As a result, the communication costs have a quadratic growth in the figure. In addition, the communication costs are nearly the same for both the server and the client, and the overall communication cost for PGI is practical for the experimental dataset.


## 7.3. Evaluation of PGU

When evaluating the performance of PGU, we first randomly generate a subgraph from the Enron email graph dataset as the graph unionGU. Then, we randomly choose two subgraphs of GU and assign them to the server and the client, respectively. The numbers of the vertices in the subgraphs are 60% of the vertex number in GU; therefore, both m and n will have the same value. For each experiment, the number of vertices in GU increases from 50 to 500. Figure 3(a) shows the computation time for the server and the client, and the detailed computation time for each step is shown in Table 3.Figure 3
Evaluation of private graph union protocol.
(a)
Computation Time(b)
Communication CostTable 3
The computation time for each step of private graph union protocol.
m/nqStep2 time (s)Step3 time (s)Step4 time (s)Step5 time (s)Step6 time (s)Step7 time (s)Step8 time (s)Step9 time (s)30500.541.130.520.450.464.105.121.74601000.591.230.500.500.5214.3216.625.43901500.661.320.470.470.5131.1735.6610.941202000.681.260.450.450.5354.9062.1119.251502500.771.300.480.480.5284.5096.9230.051803000.801.320.520.520.65117.55130.7243.262103500.821.380.480.480.63162.46185.1259.092404000.801.480.490.490.65212.23242.7577.692704500.951.590.580.580.65275.12311.5094.983005000.871.520.530.530.63336.23355.94118.34As analyzed before, the computation costs for PGU areOm+n+q2 and Omn+q2 for the server and the client, respectively, where q is the number of vertices in the union of GS and GC. Therefore, similar as PGI, the most dominant part of the computation costs for both the server and the client is most likely to be the number of vertices in GU.As shown in Table3, most of the computation time is spent in Steps 7 and 8. In Step 7, the server performs q2 Paillier encryptions, and in Step 8, the client performs q2 Paillier encryptions and q2 homomorphic additions and multiplications. Similar as before, the above computations are highly parallelizable, and cluster computing will greatly optimize the computation time.As shown in Figure3(b), the communication cost of PGU is similar to PGI, and the communication costs for both the server and the client have a quadratic growth as the number of vertices in GU increases. For our experimental dataset, the overall communication cost for the PGU protocol is also practical.


## 8. Conclusion

In this work, we proposed two privacy-preserving graph operation protocols between two parties, which can be used for secure authentication for smart devices. The first protocol, PGI, allows a server and a client to jointly compute the intersection between their private graphs, while the second protocol, PGU, computes the union of the graphs. The protocols first use polynomial representation and oblivious polynomial evaluation to compute the intersection and union of the vertices. The intersection and union of the edges are then computed by using an additive homomorphic cryptosystem.We proved that the proposed protocols are secure in the semihonest security model. In other words, a semihonest client learns nothing about the server’s graph and a semihonest server learns nothing about the client’s graph. We analyzed the leakages during the protocols for both the server and the client and modeled the leakages as leakage functions. At last, we implemented the constructions of the protocols and evaluated the efficiencies over real-word graph data.



---

*Source: 8859213-2020-11-23.xml*