# Outsourcing Set Intersection Computation Based on Bloom Filter for Privacy Preservation in Multimedia Processing

Authors: Hongliang Zhu; Meiqi Chen; Maohua Sun; Xin Liao; Lei Hu
Journal: Security and Communication Networks
 (2018)

---

## Abstract

With the development of cloud computing, the advantages of low cost and high computation ability meet the demands of complicated computation of multimedia processing. Outsourcing computation of cloud could enable users with limited computing resources to store and process distributed multimedia application data without installing multimedia application software in local computer terminals, but the main problem is how to protect the security of user data in untrusted public cloud services. In recent years, the privacy-preserving outsourcing computation is one of the most common methods to solve the security problems of cloud computing. However, the existing computation cannot meet the needs for the large number of nodes and the dynamic topologies. In this paper, we introduce a novel privacy-preserving outsourcing computation method which combines GM homomorphic encryption scheme and Bloom filter together to solve this problem and propose a new privacy-preserving outsourcing set intersection computation protocol. Results show that the new protocol resolves the privacy-preserving outsourcing set intersection computation problem without increasing the complexity and the false positive probability. Besides, the number of participants, the size of input secret sets, and the online time of participants are not limited.


---

## Body

## 1. Introduction

Network multimedia comes into fashion in the form of services; there are many methods to protect multimedia data in traditional service mode, such as steganography [1, 2] and data embedding [3]. By providing diversified media services, a new service mode, multimedia computing, has become an attractive technology to generate, edit, process, and search various media contents, like images, videos, audios, graphs, and so on [4]. For purposes of multimedia applications and services based on Internet and mobile Internet, it needs lots of computation resources so as to serve millions of netizens and wireless users, which means a large demand for multimedia cloud computing. Cloud computing is a new computing mode which could provide kinds of data service based on its computational resources. As an important application of cloud computing, outsourcing computation could enable users with narrow computing power to outsource complex function calculations to cloud servers and could guarantee the correctness of outputs and privacy of both inputs and outputs. So in this new multimedia computation mode based on cloud computing, users can store and process distributed multimedia application data without installing multimedia application software in local computer terminals to ease off the load of maintenance and updating. With regard to the large amount of computation of sites, data, and attribute dimensions, we introduce PSI into cloud computing. There is a wide range of applications where Secure Multiparty Computation is introduced into cloud computing considering the privacy-preserving algorithms.Private Set Intersection (PSI) is an important research branch of Secure Multiparty Computation (SMC), which is a research hotspot in recent years. Privacy-preserving set operation can be described as the situation that multiple participants wish to complete set intersection computation based on their private secret sets, and they cannot receive additional information other than results after computation. In PSI research model, participants complete secure computation using their private computing resources through mutual communication. Privacy preservation has become a key factor in extending the application of cloud computing, and it is the current research trend. In order to implement PSI in cloud computing successfully to solve the problems mentioned, Privacy-preserving Outsourcing Set Intersection (POSI) is proposed.


### 1.1. Contributions

The work we have completed in this paper contributes to the study and development of privacy preservation as well as outsourcing computation in several aspects as follows:(1)
We summarize system models of current privacy-preserving technology and propose a system model of privacy-preserving outsourcing computation protocol in cloud computing. It can guarantee the security and correctness of the data.(2)
We study and implement a privacy-preserving set intersection protocol based on GM homomorphic encryption scheme and Bloom filter, and the proposed protocol is proved to be significant.(3)
In detail, the protocol has some characteristics as follows:
(a)
The participant encrypts the secret set locally and consigns ciphertexts to the server who completes the outsourcing computation, but the server is unable to know about the participant’s secret set because it does not have the private key to decrypt them. So it guarantees security. Participants can check whether one or more items of data are in the intersection.(b)
The protocol does not require sizes of participants’ sets being the same as well as public compared to the existing PSI protocols [5–14].(c)
The protocol can implement secure outsourcing computation of more than two participants’ secret set intersection without the limitation that participants should be online at the same time, while the existing secure outsourcing computation protocol of set intersection [15] can only solve the situation with two participants online.(d)
The protocol has a lower probability of communication complexity and false positive error verification compared with [15].(e)
The protocol is safe under the semihonest model. We provide a full proof with simulation based security. There are two reasons why we do not design a protocol in the malicious model.(1) The proposed algorithm can be packaged as software. When we use peripheral secure technology to make the software difficult to be tampered with, semihonest model is safe enough. (2) Converting protocol in semihonest model to malicious model is an independent research topic with plenty of achievements currently. If necessary, the algorithm can be converted into one in the malicious model based on the existing research findings.


### 1.2. Related Work

The following sections describe the research progress of privacy-preserving set intersection and outsourcing computation.


#### 1.2.1. Secure Multiparty Computation

Protocols for Secure Multiparty Computation enable a set of parties to carry out a joint computation on private inputs, without revealing anything but the output. Over the past decade, there has been a major research effort to develop Secure Multiparty Computation. Zhou et al. [16] proposed a secure multiparty subset protocol using the Bloom filter and homomorphic encryption scheme. However, their protocol may yield a false positive. Liu et al. [17] proposed an information-theoretically secure protocol to solve the multiparty millionaires’ problem using the vectorization and secret splitting methods; their protocol can resist collusion attacks. Sun et al. [18] proposed a secure outsourcing multiparty computation protocol on lattice-based encrypted data in two-cloud-servers scenario. Their protocol was completely noninteractive between any users, and both of the computation and the communication complexities of each user in our solution were independent of the computing function.


#### 1.2.2. Privacy-Preserving Set Intersection

Privacy-preserving set intersection is a research focus in the field of cryptography. The PSI problem can be described as the situation that multiple participants wish to complete the set intersection computation based on their private secret sets, and they cannot receive additional information other than results after the computation.According to different implementation principles, we can classify research findings of PSI into the following four types.(i) The Oblivious Polynomial Evaluation Based Protocols. Oblivious polynomial evaluation is the first method to implement the PSI protocol. Dachman-Soled et al. [5] implemented a PSI protocol in malicious models using Shamir Threshold Secret Sharing technology. The computational complexity of the algorithm is O(mnklog⁡n+mk2log2n), and the communication complexity is O(nk+mk2log2n), in which k is the secure parameter, while m and n are the sizes of the participant input sets.(ii) The Oblivious Pseudorandom Function Based Protocols. At the TCC Conference in 2008, Hazay and Lindell [6] proposed a privacy-preserving set intersection protocol based on the oblivious pseudorandom function. The scheme is safe in the weakly malicious model, which means participants’ malicious behavior will be found with a high probability. Later, Hazay and Nissim [7] used zero-knowledge proof and perfectly hiding commitment scheme to implement a privacy-preserving set intersection protocol in malicious model. The communication complexity of the algorithm is O(m+n(log⁡log⁡m+σ)), and the computational complexity is O(m+nσ), in which m and n are the sizes of the two sets. σ is elements’ largest binary number of bits in the set. Jarecki and Liu [8] proposed a privacy-preserving intersection protocol under the CRS model based on the Decisional-q-Diffie-Hellman Inversion hypothesis. De Cristofaro and Tsudik [9, 10] proposed a privacy-preserving intersection operation protocol with linear complexity under the semihonest model based on the One-More-Gap-DH hypothesis. Later, De Cristofaro et al. [11] proposed an efficient privacy-preserving intersection operation scheme against malicious attackers based on the DDH hypothesis.(iii) The Bloom Filter Based Protocols. Bloom filter is a new data structure introduced in recent years, of which the structure is similar to bit-map. Compared to bit-map, Bloom filter saves more space and can quickly judge whether an element is in a set. But there is a certain rate of error recognition in this method. In 2012, Many et al. [12] introduced Bloom filter into the privacy-preserving intersection operations. They used the secure multipart multiplication protocol to get the Bloom filter vector corresponding to the intersection of participants and then get the set intersection. However, the algorithm is insecure because the intersection Bloom filter vector leaked information of each participant’s set. In 2013, Dong et al. [13] designed a more efficient privacy-preserving intersection protocol based on Bloom filter, using secret sharing and oblivious transfer. Take the privacy-preserving intersection operation protocol under semihonest model as an example; the scheme Dong et al. [13] proposed requires 2(k+klog2e)n times of hash operations and hundreds of public key operations. In 2014, Pinkas and Schneider [14] designed a random confusion Bloom filter to optimize efficiency of the protocol of Dong et al. [13], using oblivious extension protocol.(iv) The Garbled-Circuit Technology Based Protocols. Using garbled-circuit technology to solve privacy-preserving problems is a common method of Secure Multiparty Computation, but many references in the past suggest that the method is less efficient. In 2012, Huang et al. [19] designed the intersection-specific circuit based on the idea of“Sort-Compare-Shuffle” and implemented the privacy-preserving intersection operation protocol using Yao’s generic garbled-circuit method. The experimental results of Huang et al. [19] show that the scheme of De Cristofaro and Tsudik [9, 10] is more efficient when the security level is low, and as the security level increases, the scheme of Huang et al. [19] is significantly better than that of De Cristofaro and Tsudik [9, 10] considering efficiency of the program. In 2014, Pinkas and Schneider [14] optimized the GMW scheme using oblivious extension protocol, used the optimized GMW scheme to evaluate the intersecting circuit designed by Huang et al. [19], and implemented a more efficient privacy-preserving intersection operation protocol on Boolean circuits. The computational complexity is 18nσlog⁡n times of symmetric encryption operations, while the communication complexity is O(6nkσlog⁡n), in which k is the secure parameter.


#### 1.2.3. Privacy-Preserving Outsourcing Computation

Outsourcing computation in multimedia processing is an emerging technology in recent years. Although the study of privacy-preserving outsourcing computation has just started, it is the current research hot spot.At the CRYPTO conference in 2010, Gennaro et al. [20] proposed privacy-preserving issues in verifiable computations and designed a privacy-preserving outsourcing computation protocol that can achieve verifiable efficiency based on the homomorphic encryption technology. In 2011, Mohassel [21] designed a noninteractive security outsourcing computation protocol on linear algebraic operations based on homomorphic encryption. In 2013, Parno et al. [22] designed the Pinocchio system which implemented efficient outsourcing computation, but the system did not take into account the privacy-preserving issues of the information input by participants; Schoenmakers et al. [23] designed the Trinocchio system to solve the leakage of Pinocchio system, enabling efficient verifiable secure outsourcing computation. In the same year, Peter et al. [24] designed a secure outsourcing computation protocol for common functional functions, using a dual decryption mechanism scheme with additive homology, and implemented an efficient face recognition system in cloud computing environment based on this protocol. In 2013, Xing et al. [25] constructed a verifiable secure outsourcing computation protocol using the blind product as a matrix product, matrix determinant, and matrix inverse. The security does not depend on any cryptographic assumptions. In 2014, Hu and Tang [26] implemented the secure outsourcing protocol of multiplication on the elliptic curve in the cloud computing environment, which could effectively accelerate the efficiency of signature verification.Although the PSI protocol has implemented plenty of achievements, they cannot be converted to be used in privacy-preserving set intersection outsourcing computation directly. At present, the research on the privacy-preserving issues in set intersection outsourcing computation has just started, while the findings are still not enough. According to our searching results, Kerschbaum [15] proposed a set intersection secure outsourcing protocol based on SYY homomorphic encryption scheme and Bloom filter. However, the protocol has the following problems: (1) the protocol only solves the secure outsourcing computation of two participants’ set intersections, while one of the participants needs to be both common participant and server at the same time; (2) during the process of the protocol, all the participants are required to be online at the same time; (3) there is a high probability of false positive error judgement in the protocol.


### 1.3. Organizational Structure

In the second session, we introduce secure definition in the scheme and the underlying cryptographic tools. We show the system model in Section3 and present the privacy-preserving set intersection computation protocol which can be applied into cloud computing in Section 4. In Section 5, we give the correct proof of the protocol, error probability analysis, and security proof as well as efficiency analysis and comparison. Finally, we summarize prospects of our protocol’s application in multimedia processing based on cloud computing in the Conclusion.


## 1.1. Contributions

The work we have completed in this paper contributes to the study and development of privacy preservation as well as outsourcing computation in several aspects as follows:(1)
We summarize system models of current privacy-preserving technology and propose a system model of privacy-preserving outsourcing computation protocol in cloud computing. It can guarantee the security and correctness of the data.(2)
We study and implement a privacy-preserving set intersection protocol based on GM homomorphic encryption scheme and Bloom filter, and the proposed protocol is proved to be significant.(3)
In detail, the protocol has some characteristics as follows:
(a)
The participant encrypts the secret set locally and consigns ciphertexts to the server who completes the outsourcing computation, but the server is unable to know about the participant’s secret set because it does not have the private key to decrypt them. So it guarantees security. Participants can check whether one or more items of data are in the intersection.(b)
The protocol does not require sizes of participants’ sets being the same as well as public compared to the existing PSI protocols [5–14].(c)
The protocol can implement secure outsourcing computation of more than two participants’ secret set intersection without the limitation that participants should be online at the same time, while the existing secure outsourcing computation protocol of set intersection [15] can only solve the situation with two participants online.(d)
The protocol has a lower probability of communication complexity and false positive error verification compared with [15].(e)
The protocol is safe under the semihonest model. We provide a full proof with simulation based security. There are two reasons why we do not design a protocol in the malicious model.(1) The proposed algorithm can be packaged as software. When we use peripheral secure technology to make the software difficult to be tampered with, semihonest model is safe enough. (2) Converting protocol in semihonest model to malicious model is an independent research topic with plenty of achievements currently. If necessary, the algorithm can be converted into one in the malicious model based on the existing research findings.


## 1.2. Related Work

The following sections describe the research progress of privacy-preserving set intersection and outsourcing computation.


### 1.2.1. Secure Multiparty Computation

Protocols for Secure Multiparty Computation enable a set of parties to carry out a joint computation on private inputs, without revealing anything but the output. Over the past decade, there has been a major research effort to develop Secure Multiparty Computation. Zhou et al. [16] proposed a secure multiparty subset protocol using the Bloom filter and homomorphic encryption scheme. However, their protocol may yield a false positive. Liu et al. [17] proposed an information-theoretically secure protocol to solve the multiparty millionaires’ problem using the vectorization and secret splitting methods; their protocol can resist collusion attacks. Sun et al. [18] proposed a secure outsourcing multiparty computation protocol on lattice-based encrypted data in two-cloud-servers scenario. Their protocol was completely noninteractive between any users, and both of the computation and the communication complexities of each user in our solution were independent of the computing function.


### 1.2.2. Privacy-Preserving Set Intersection

Privacy-preserving set intersection is a research focus in the field of cryptography. The PSI problem can be described as the situation that multiple participants wish to complete the set intersection computation based on their private secret sets, and they cannot receive additional information other than results after the computation.According to different implementation principles, we can classify research findings of PSI into the following four types.(i) The Oblivious Polynomial Evaluation Based Protocols. Oblivious polynomial evaluation is the first method to implement the PSI protocol. Dachman-Soled et al. [5] implemented a PSI protocol in malicious models using Shamir Threshold Secret Sharing technology. The computational complexity of the algorithm is O(mnklog⁡n+mk2log2n), and the communication complexity is O(nk+mk2log2n), in which k is the secure parameter, while m and n are the sizes of the participant input sets.(ii) The Oblivious Pseudorandom Function Based Protocols. At the TCC Conference in 2008, Hazay and Lindell [6] proposed a privacy-preserving set intersection protocol based on the oblivious pseudorandom function. The scheme is safe in the weakly malicious model, which means participants’ malicious behavior will be found with a high probability. Later, Hazay and Nissim [7] used zero-knowledge proof and perfectly hiding commitment scheme to implement a privacy-preserving set intersection protocol in malicious model. The communication complexity of the algorithm is O(m+n(log⁡log⁡m+σ)), and the computational complexity is O(m+nσ), in which m and n are the sizes of the two sets. σ is elements’ largest binary number of bits in the set. Jarecki and Liu [8] proposed a privacy-preserving intersection protocol under the CRS model based on the Decisional-q-Diffie-Hellman Inversion hypothesis. De Cristofaro and Tsudik [9, 10] proposed a privacy-preserving intersection operation protocol with linear complexity under the semihonest model based on the One-More-Gap-DH hypothesis. Later, De Cristofaro et al. [11] proposed an efficient privacy-preserving intersection operation scheme against malicious attackers based on the DDH hypothesis.(iii) The Bloom Filter Based Protocols. Bloom filter is a new data structure introduced in recent years, of which the structure is similar to bit-map. Compared to bit-map, Bloom filter saves more space and can quickly judge whether an element is in a set. But there is a certain rate of error recognition in this method. In 2012, Many et al. [12] introduced Bloom filter into the privacy-preserving intersection operations. They used the secure multipart multiplication protocol to get the Bloom filter vector corresponding to the intersection of participants and then get the set intersection. However, the algorithm is insecure because the intersection Bloom filter vector leaked information of each participant’s set. In 2013, Dong et al. [13] designed a more efficient privacy-preserving intersection protocol based on Bloom filter, using secret sharing and oblivious transfer. Take the privacy-preserving intersection operation protocol under semihonest model as an example; the scheme Dong et al. [13] proposed requires 2(k+klog2e)n times of hash operations and hundreds of public key operations. In 2014, Pinkas and Schneider [14] designed a random confusion Bloom filter to optimize efficiency of the protocol of Dong et al. [13], using oblivious extension protocol.(iv) The Garbled-Circuit Technology Based Protocols. Using garbled-circuit technology to solve privacy-preserving problems is a common method of Secure Multiparty Computation, but many references in the past suggest that the method is less efficient. In 2012, Huang et al. [19] designed the intersection-specific circuit based on the idea of“Sort-Compare-Shuffle” and implemented the privacy-preserving intersection operation protocol using Yao’s generic garbled-circuit method. The experimental results of Huang et al. [19] show that the scheme of De Cristofaro and Tsudik [9, 10] is more efficient when the security level is low, and as the security level increases, the scheme of Huang et al. [19] is significantly better than that of De Cristofaro and Tsudik [9, 10] considering efficiency of the program. In 2014, Pinkas and Schneider [14] optimized the GMW scheme using oblivious extension protocol, used the optimized GMW scheme to evaluate the intersecting circuit designed by Huang et al. [19], and implemented a more efficient privacy-preserving intersection operation protocol on Boolean circuits. The computational complexity is 18nσlog⁡n times of symmetric encryption operations, while the communication complexity is O(6nkσlog⁡n), in which k is the secure parameter.


### 1.2.3. Privacy-Preserving Outsourcing Computation

Outsourcing computation in multimedia processing is an emerging technology in recent years. Although the study of privacy-preserving outsourcing computation has just started, it is the current research hot spot.At the CRYPTO conference in 2010, Gennaro et al. [20] proposed privacy-preserving issues in verifiable computations and designed a privacy-preserving outsourcing computation protocol that can achieve verifiable efficiency based on the homomorphic encryption technology. In 2011, Mohassel [21] designed a noninteractive security outsourcing computation protocol on linear algebraic operations based on homomorphic encryption. In 2013, Parno et al. [22] designed the Pinocchio system which implemented efficient outsourcing computation, but the system did not take into account the privacy-preserving issues of the information input by participants; Schoenmakers et al. [23] designed the Trinocchio system to solve the leakage of Pinocchio system, enabling efficient verifiable secure outsourcing computation. In the same year, Peter et al. [24] designed a secure outsourcing computation protocol for common functional functions, using a dual decryption mechanism scheme with additive homology, and implemented an efficient face recognition system in cloud computing environment based on this protocol. In 2013, Xing et al. [25] constructed a verifiable secure outsourcing computation protocol using the blind product as a matrix product, matrix determinant, and matrix inverse. The security does not depend on any cryptographic assumptions. In 2014, Hu and Tang [26] implemented the secure outsourcing protocol of multiplication on the elliptic curve in the cloud computing environment, which could effectively accelerate the efficiency of signature verification.Although the PSI protocol has implemented plenty of achievements, they cannot be converted to be used in privacy-preserving set intersection outsourcing computation directly. At present, the research on the privacy-preserving issues in set intersection outsourcing computation has just started, while the findings are still not enough. According to our searching results, Kerschbaum [15] proposed a set intersection secure outsourcing protocol based on SYY homomorphic encryption scheme and Bloom filter. However, the protocol has the following problems: (1) the protocol only solves the secure outsourcing computation of two participants’ set intersections, while one of the participants needs to be both common participant and server at the same time; (2) during the process of the protocol, all the participants are required to be online at the same time; (3) there is a high probability of false positive error judgement in the protocol.


## 1.2.1. Secure Multiparty Computation

Protocols for Secure Multiparty Computation enable a set of parties to carry out a joint computation on private inputs, without revealing anything but the output. Over the past decade, there has been a major research effort to develop Secure Multiparty Computation. Zhou et al. [16] proposed a secure multiparty subset protocol using the Bloom filter and homomorphic encryption scheme. However, their protocol may yield a false positive. Liu et al. [17] proposed an information-theoretically secure protocol to solve the multiparty millionaires’ problem using the vectorization and secret splitting methods; their protocol can resist collusion attacks. Sun et al. [18] proposed a secure outsourcing multiparty computation protocol on lattice-based encrypted data in two-cloud-servers scenario. Their protocol was completely noninteractive between any users, and both of the computation and the communication complexities of each user in our solution were independent of the computing function.


## 1.2.2. Privacy-Preserving Set Intersection

Privacy-preserving set intersection is a research focus in the field of cryptography. The PSI problem can be described as the situation that multiple participants wish to complete the set intersection computation based on their private secret sets, and they cannot receive additional information other than results after the computation.According to different implementation principles, we can classify research findings of PSI into the following four types.(i) The Oblivious Polynomial Evaluation Based Protocols. Oblivious polynomial evaluation is the first method to implement the PSI protocol. Dachman-Soled et al. [5] implemented a PSI protocol in malicious models using Shamir Threshold Secret Sharing technology. The computational complexity of the algorithm is O(mnklog⁡n+mk2log2n), and the communication complexity is O(nk+mk2log2n), in which k is the secure parameter, while m and n are the sizes of the participant input sets.(ii) The Oblivious Pseudorandom Function Based Protocols. At the TCC Conference in 2008, Hazay and Lindell [6] proposed a privacy-preserving set intersection protocol based on the oblivious pseudorandom function. The scheme is safe in the weakly malicious model, which means participants’ malicious behavior will be found with a high probability. Later, Hazay and Nissim [7] used zero-knowledge proof and perfectly hiding commitment scheme to implement a privacy-preserving set intersection protocol in malicious model. The communication complexity of the algorithm is O(m+n(log⁡log⁡m+σ)), and the computational complexity is O(m+nσ), in which m and n are the sizes of the two sets. σ is elements’ largest binary number of bits in the set. Jarecki and Liu [8] proposed a privacy-preserving intersection protocol under the CRS model based on the Decisional-q-Diffie-Hellman Inversion hypothesis. De Cristofaro and Tsudik [9, 10] proposed a privacy-preserving intersection operation protocol with linear complexity under the semihonest model based on the One-More-Gap-DH hypothesis. Later, De Cristofaro et al. [11] proposed an efficient privacy-preserving intersection operation scheme against malicious attackers based on the DDH hypothesis.(iii) The Bloom Filter Based Protocols. Bloom filter is a new data structure introduced in recent years, of which the structure is similar to bit-map. Compared to bit-map, Bloom filter saves more space and can quickly judge whether an element is in a set. But there is a certain rate of error recognition in this method. In 2012, Many et al. [12] introduced Bloom filter into the privacy-preserving intersection operations. They used the secure multipart multiplication protocol to get the Bloom filter vector corresponding to the intersection of participants and then get the set intersection. However, the algorithm is insecure because the intersection Bloom filter vector leaked information of each participant’s set. In 2013, Dong et al. [13] designed a more efficient privacy-preserving intersection protocol based on Bloom filter, using secret sharing and oblivious transfer. Take the privacy-preserving intersection operation protocol under semihonest model as an example; the scheme Dong et al. [13] proposed requires 2(k+klog2e)n times of hash operations and hundreds of public key operations. In 2014, Pinkas and Schneider [14] designed a random confusion Bloom filter to optimize efficiency of the protocol of Dong et al. [13], using oblivious extension protocol.(iv) The Garbled-Circuit Technology Based Protocols. Using garbled-circuit technology to solve privacy-preserving problems is a common method of Secure Multiparty Computation, but many references in the past suggest that the method is less efficient. In 2012, Huang et al. [19] designed the intersection-specific circuit based on the idea of“Sort-Compare-Shuffle” and implemented the privacy-preserving intersection operation protocol using Yao’s generic garbled-circuit method. The experimental results of Huang et al. [19] show that the scheme of De Cristofaro and Tsudik [9, 10] is more efficient when the security level is low, and as the security level increases, the scheme of Huang et al. [19] is significantly better than that of De Cristofaro and Tsudik [9, 10] considering efficiency of the program. In 2014, Pinkas and Schneider [14] optimized the GMW scheme using oblivious extension protocol, used the optimized GMW scheme to evaluate the intersecting circuit designed by Huang et al. [19], and implemented a more efficient privacy-preserving intersection operation protocol on Boolean circuits. The computational complexity is 18nσlog⁡n times of symmetric encryption operations, while the communication complexity is O(6nkσlog⁡n), in which k is the secure parameter.


## 1.2.3. Privacy-Preserving Outsourcing Computation

Outsourcing computation in multimedia processing is an emerging technology in recent years. Although the study of privacy-preserving outsourcing computation has just started, it is the current research hot spot.At the CRYPTO conference in 2010, Gennaro et al. [20] proposed privacy-preserving issues in verifiable computations and designed a privacy-preserving outsourcing computation protocol that can achieve verifiable efficiency based on the homomorphic encryption technology. In 2011, Mohassel [21] designed a noninteractive security outsourcing computation protocol on linear algebraic operations based on homomorphic encryption. In 2013, Parno et al. [22] designed the Pinocchio system which implemented efficient outsourcing computation, but the system did not take into account the privacy-preserving issues of the information input by participants; Schoenmakers et al. [23] designed the Trinocchio system to solve the leakage of Pinocchio system, enabling efficient verifiable secure outsourcing computation. In the same year, Peter et al. [24] designed a secure outsourcing computation protocol for common functional functions, using a dual decryption mechanism scheme with additive homology, and implemented an efficient face recognition system in cloud computing environment based on this protocol. In 2013, Xing et al. [25] constructed a verifiable secure outsourcing computation protocol using the blind product as a matrix product, matrix determinant, and matrix inverse. The security does not depend on any cryptographic assumptions. In 2014, Hu and Tang [26] implemented the secure outsourcing protocol of multiplication on the elliptic curve in the cloud computing environment, which could effectively accelerate the efficiency of signature verification.Although the PSI protocol has implemented plenty of achievements, they cannot be converted to be used in privacy-preserving set intersection outsourcing computation directly. At present, the research on the privacy-preserving issues in set intersection outsourcing computation has just started, while the findings are still not enough. According to our searching results, Kerschbaum [15] proposed a set intersection secure outsourcing protocol based on SYY homomorphic encryption scheme and Bloom filter. However, the protocol has the following problems: (1) the protocol only solves the secure outsourcing computation of two participants’ set intersections, while one of the participants needs to be both common participant and server at the same time; (2) during the process of the protocol, all the participants are required to be online at the same time; (3) there is a high probability of false positive error judgement in the protocol.


## 1.3. Organizational Structure

In the second session, we introduce secure definition in the scheme and the underlying cryptographic tools. We show the system model in Section3 and present the privacy-preserving set intersection computation protocol which can be applied into cloud computing in Section 4. In Section 5, we give the correct proof of the protocol, error probability analysis, and security proof as well as efficiency analysis and comparison. Finally, we summarize prospects of our protocol’s application in multimedia processing based on cloud computing in the Conclusion.


## 2. Background

### 2.1. Secure Model and Secure Definition

Since the protocol proposed in this paper belongs to one kind of the Secure Multiparty Computation protocols, we use secure models and secure definitions of Secure Multiparty Computation protocols.Participants of Secure Multiparty Computation are classified into honest participants, semihonest participants, and malicious participants. During the implementation of the protocol, honest participants completely comply with the protocol, with no provision of false data, leakage, eavesdropping, and suspension of the protocol; semihonest participants will finish each step following the requirements of the implementation without behaviors mentioned earlier, but they will keep all the information they collected in order to judge secret messages of other participants; malicious participants completely ignore the requirements of the protocol. They may provide false data, leak all the information they collect, eavesdrop, or even suspend protocols.The semihonest model is safe and widely used in Secure Multiparty Computation. The model can be intuitively understood as the situation that if a semihonest participant can directly use their input and output of protocols to obtain any information he can reach in the implementation of the protocol by a separate simulation of the entire protocol implementation process, it can be guaranteed in the protocol that the input is private. If a computation protocol can be simulated like this, participants cannot obtain valuable information from the execution of the protocol, and such protocol is safe.Definition 1 (private computation under semihonest model).
In the implementation of protocolΠ, the information that participants P1 and P2 obtain is recorded as(1)VIEW1Πx,y=x,r1,m11,m21,…,mt1VIEW2Πx,y=x,r2,m12,m22,…,mt2.In the equations, ri represents the random number Pi generates and mji represents the jth message Pi receives. After the protocol ends, the output of participant Pi is recorded as OUTPUTiΠx,y. We can see that in fact OUTPUTiΠx,y is a part of VIEWiΠx,y.
As for the deterministic functionf, we can say that protocol Π computes f under the semihonest model privately if and only if probability polynomial time algorithms S1 and S2 exist, and it conforms to the equations:(2)S1x,f1x,yx,y∈0,1∗≡cVIEW1Πx,yx,y∈0,1∗S2y,f2x,yx,y∈0,1∗≡cVIEW2Πx,yx,y∈0,1∗for x=y.


### 2.2. GM Homomorphic Encryption

A high-level description of Gentry’s scheme is as follows. The scheme is based on identifying idealsI in polynomial quotient rings Zx/(f(x)) (with f°=n) with euclidean lattices LI⊆Rn by mapping eachresidue polynomial rx=a0+⋯+an-1xn-1 to its vector of coefficients (a0,…,an-1). Gentry calls these objects ideal lattices. Ideal lattices provide additive and multiplicative homomorphisms modulo a public key ideal. We obtain an encryption procedure Encrypt such that Encrypt(x1)+Encrypt(x2)=Encrypt(x1+x2)andEncrypt(x1)·Encrypt(x2)=Encrypt(x1·x2). Therefore, any circuit C with efficient description can be evaluated homomorphically. However, this somewhat fully homomorphic scheme (SWHE) is not perfect. Due to the noisy nature of the scheme, with each homomorphic gate evaluation the noise term in the partial result grows. After the evaluation of only a logarithmic depth circuit, the decryption fails to recover the correct result. To make the scheme work, Gentry uses a number of tricks. He introduces a reencryption procedure called Recrypt that takes a noisy ciphertext and returns a noise-reduced version. In a brilliant move, Gentry manages to obtain Recrypt again from the SWHE scheme by simply homomorphically evaluating the decryption circuit using encrypted secret key bits on the noisy ciphertext. To make this work, the SWHE needs to be able to handle circuits that are deeper than its own decryption circuit before the level of noise becomes too large. SWHE schemes with this property are called bootstrappable.


### 2.3. XOR Secret Sharing

The secret publisher converts his secrets into n subsecrets and sends them to other participants. The secret sharing scheme is called a (t,n) threshold secret sharing scheme when they can recover the secret s if and only if at least t participants contribute their specific subsecrets.When the thresholdt=n, the XOR secret sharing scheme proposed by Ishai et al. [27] is widely used. The details are as follows.Participants. The participants are secret publisher D and n participants P1,P2,…,Pn.Input. The input is secret s that secret publisher D inputs.Secret Sharing. (1) Secret publisher generates n-1 random numbers r1,r2,…,rn-1, and the length of each is s.( 2 ) Secret publisher calculates the nth secret:(3)rn=r1⊕r2⊕⋯⊕rn-1⊕s.{r1,r2,…,rn} compose subsecrets of s.( 3 ) As for i=1,2,…,n, the secret publisher sends subsecret ri to Pi.Secret Recovery. When it is necessary to recover the secret s, n participants P1,P2,…,Pn contribute their own subsecrets and do the following operation:(4)s=r1⊕r2⊕⋯⊕rn.


### 2.4. Bloom Filter

The Bloom filter [28] set is a data structure used to judge whether an element is in a set. A Bloom filter contains several hash functions hashi(i=1,2,…,k) and a Bloom filter set BF. When building a Bloom filter set, use the hash function first to map the data x which is to be inserted to the kth position of BF, and then set the data on those positions to 1. When all the data is inserted, the Bloom filter set is completed. When verifying whether a data y is in a set, use the hash function first to map y to the kth position of BF. If the values of these k data bits are all 1, there is a great possibility that y is in the set; otherwise it is not in for sure.


## 2.1. Secure Model and Secure Definition

Since the protocol proposed in this paper belongs to one kind of the Secure Multiparty Computation protocols, we use secure models and secure definitions of Secure Multiparty Computation protocols.Participants of Secure Multiparty Computation are classified into honest participants, semihonest participants, and malicious participants. During the implementation of the protocol, honest participants completely comply with the protocol, with no provision of false data, leakage, eavesdropping, and suspension of the protocol; semihonest participants will finish each step following the requirements of the implementation without behaviors mentioned earlier, but they will keep all the information they collected in order to judge secret messages of other participants; malicious participants completely ignore the requirements of the protocol. They may provide false data, leak all the information they collect, eavesdrop, or even suspend protocols.The semihonest model is safe and widely used in Secure Multiparty Computation. The model can be intuitively understood as the situation that if a semihonest participant can directly use their input and output of protocols to obtain any information he can reach in the implementation of the protocol by a separate simulation of the entire protocol implementation process, it can be guaranteed in the protocol that the input is private. If a computation protocol can be simulated like this, participants cannot obtain valuable information from the execution of the protocol, and such protocol is safe.Definition 1 (private computation under semihonest model).
In the implementation of protocolΠ, the information that participants P1 and P2 obtain is recorded as(1)VIEW1Πx,y=x,r1,m11,m21,…,mt1VIEW2Πx,y=x,r2,m12,m22,…,mt2.In the equations, ri represents the random number Pi generates and mji represents the jth message Pi receives. After the protocol ends, the output of participant Pi is recorded as OUTPUTiΠx,y. We can see that in fact OUTPUTiΠx,y is a part of VIEWiΠx,y.
As for the deterministic functionf, we can say that protocol Π computes f under the semihonest model privately if and only if probability polynomial time algorithms S1 and S2 exist, and it conforms to the equations:(2)S1x,f1x,yx,y∈0,1∗≡cVIEW1Πx,yx,y∈0,1∗S2y,f2x,yx,y∈0,1∗≡cVIEW2Πx,yx,y∈0,1∗for x=y.


## 2.2. GM Homomorphic Encryption

A high-level description of Gentry’s scheme is as follows. The scheme is based on identifying idealsI in polynomial quotient rings Zx/(f(x)) (with f°=n) with euclidean lattices LI⊆Rn by mapping eachresidue polynomial rx=a0+⋯+an-1xn-1 to its vector of coefficients (a0,…,an-1). Gentry calls these objects ideal lattices. Ideal lattices provide additive and multiplicative homomorphisms modulo a public key ideal. We obtain an encryption procedure Encrypt such that Encrypt(x1)+Encrypt(x2)=Encrypt(x1+x2)andEncrypt(x1)·Encrypt(x2)=Encrypt(x1·x2). Therefore, any circuit C with efficient description can be evaluated homomorphically. However, this somewhat fully homomorphic scheme (SWHE) is not perfect. Due to the noisy nature of the scheme, with each homomorphic gate evaluation the noise term in the partial result grows. After the evaluation of only a logarithmic depth circuit, the decryption fails to recover the correct result. To make the scheme work, Gentry uses a number of tricks. He introduces a reencryption procedure called Recrypt that takes a noisy ciphertext and returns a noise-reduced version. In a brilliant move, Gentry manages to obtain Recrypt again from the SWHE scheme by simply homomorphically evaluating the decryption circuit using encrypted secret key bits on the noisy ciphertext. To make this work, the SWHE needs to be able to handle circuits that are deeper than its own decryption circuit before the level of noise becomes too large. SWHE schemes with this property are called bootstrappable.


## 2.3. XOR Secret Sharing

The secret publisher converts his secrets into n subsecrets and sends them to other participants. The secret sharing scheme is called a (t,n) threshold secret sharing scheme when they can recover the secret s if and only if at least t participants contribute their specific subsecrets.When the thresholdt=n, the XOR secret sharing scheme proposed by Ishai et al. [27] is widely used. The details are as follows.Participants. The participants are secret publisher D and n participants P1,P2,…,Pn.Input. The input is secret s that secret publisher D inputs.Secret Sharing. (1) Secret publisher generates n-1 random numbers r1,r2,…,rn-1, and the length of each is s.( 2 ) Secret publisher calculates the nth secret:(3)rn=r1⊕r2⊕⋯⊕rn-1⊕s.{r1,r2,…,rn} compose subsecrets of s.( 3 ) As for i=1,2,…,n, the secret publisher sends subsecret ri to Pi.Secret Recovery. When it is necessary to recover the secret s, n participants P1,P2,…,Pn contribute their own subsecrets and do the following operation:(4)s=r1⊕r2⊕⋯⊕rn.


## 2.4. Bloom Filter

The Bloom filter [28] set is a data structure used to judge whether an element is in a set. A Bloom filter contains several hash functions hashi(i=1,2,…,k) and a Bloom filter set BF. When building a Bloom filter set, use the hash function first to map the data x which is to be inserted to the kth position of BF, and then set the data on those positions to 1. When all the data is inserted, the Bloom filter set is completed. When verifying whether a data y is in a set, use the hash function first to map y to the kth position of BF. If the values of these k data bits are all 1, there is a great possibility that y is in the set; otherwise it is not in for sure.


## 3. System Model

A trusted third party is a model that solves the privacy-preserving problem in distributed computation, as shown in Figure1(a). However, it is difficult to find a completely credible third party in real life, so this system model is rarely used at present. Currently in the field of Secure Multiparty Computation, a widely used system model is shown in Figure 1(b). It needs a number of participants to complete the secure computation of a certain function through information interaction instead of a trusted third party. To achieve the privacy-preserving outsourcing computation, we can not use the model of Figure 1(a) directly because a completely trusted third party does not exist; nor can we use Figure 1(b) model directly, because a lot of computation is consigned to the server.Figure 1
Secure Multiparty Computation model.
(a) (b) (c)The system model we use is shown in Figure1(c). Although a completely trusted third party does not exist, the authority (for example, an authoritative digital certificate authority) does exist. Before the protocol is formally conducted, the participant will be authenticated by the authority first. If the audit passes, the authority sends the system key to participants. In the process of the protocol, participants use the public key to encrypt their own secret sets and consign the ciphertexts to the server. The server computes all the ciphertexts it takes over and saves them. Then every participant may request to verify whether one or some of data is in the intersection of the sets at any time.Then we describe the behavior pattern of all participants and the server after the authentication in the system model applied in cloud computing shown in Figure1(c). In this system model, the problem to be solved can be described as follows: m participants P1,P2,…,Pm hold secret messages separately, and the participant completes the operation f(s1,s2,…,sm) by leasing a server with powerful computing resources. In terms of security, the participant wishes others not to be informed of other useful information except the results after completing the computation; the server is unable to know the participants’ secret messages s1,s2,…,sm, and the server can not know the result f(s1,s2,…,sm).We divide the information interaction between participants and servers into three stages: preprocessing, outsourcing computation, and results query. In the preprocessing stage, behavior of participants and servers is as follows:(5)Pi:Si→ππSiPi→πSiServer.As for each participant Pi, the first step is converting Si to π(Si) through a certain operation π locally and then sending π(Si) to the server. The operation π should be unidirectional; otherwise the server will be informed of the participant’s secret message.In the outsourcing computation stage, the server converts all the outsourced data of participants to data sourcesFπS1,πS2,… of the results query stage through a certain operation F. We can use the following equation to represent the server’s behavior pattern:(6)Server:πS1,πS2,…→FFπS1,πS2,….In the results query stage, the behavior pattern of the inquirer Pi and the server is as follows:(7)Pi→QiServerServer:FπS1,πS2,…,Qi→ΔRiServer→RiPiPi:Ri→ΦΦRi.It means that the participant constructs query data Qi and sends it to the server first. The server conducts operation Δ using the result FπS1,πS2,… of the previous stage and Qi as input and then gets the result Ri and sends it to Pi. Participants Pi conduct a certain decryption Φ to Ri and gets the final result Φ(Ri). The correctness requirement of this model is ΦRi=f(s1,s2,…,sm).


## 4. Privacy-Preserving Set Intersection Outsourcing Computation Protocol

In this section, we design the set intersection secure outsourcing protocol in accordance with three stages of preprocessing, outsourcing computation, and results query. We state in this section that participants and authorities have completed authentication and key distribution in Figure1(c).The protocol uses the following symbols:P represents all participants, Pi represents the ith participant, and m represents the number of participants. The secret set of participant Pi is Si, and its size is represented by Si. GFi represents the Bloom filter set of participant Pi and GFi(j) represents the jth element in the Bloom filter set. The number of elements in Bloom filter is t while the number of hash functions used in the process of forming Bloom filters is k. CGFi represents ciphertexts corresponding to Bloom filter set of Pi. The length of ciphertexts in XOR secret sharing is n, and the length of ciphertexts in GM encryption algorithm is l.


### 4.1. Preprocessing

In the preprocessing stage, the participant generates Bloom filter set corresponding to his private secret set. In order to reduce the probability of false positives, participants share data of secret sets to thek elements of Bloom filter, using XOR secret sharing. We can get the positions of the k elements by hashing. In order to achieve privacy preservation, participants use the GM algorithm to do encryption operations on their respective Bloom filter sets and send them to server. The preprocessing protocol process is as shown in Algorithm 1.Algorithm 1:Preprocessing protocol.
Participants: Pi Input: the input sets of Pi: Si System parameters: k hash functions hashi (i=1,2,…,k) for (j=0;j<t;j++) B F i j = N U L L; / /In the initial state, the Bloom filter set / /of participants is empty for (j=0;j<Si;j++)  π = N U L L; for (δ=0;δ<k;δ++)  if (BFihashδ(Si(j))==NULL)  π = h a s h δ S i j; B F i h a s h δ S i j = R a n d o m ( 0,1 ) n; / /generate random numbers / /with the length of n;  if (π==NULL) Return error1; //error else B F i π = S i j ⊕ B F i h a s h 1 S i j  ⊕ B F i h a s h 2 S i j  ⊕ ⋯ ⊕ B F i h a s h k ( S i ( j ) )   ε = 0; for (j=0;j<t;j++)  if (BFij==NULL) B F i j = R a n d o m ( 0,1 ) n; for (μ=0;μ<n;μ++)  ε = ε + 1; C B F i ε = E n c B F i j μ; / / B F i j μ represents the μth / /bit in BFij;After the previous computation, participantPi gets encrypted Bloom filter set CBFi, and Pi needs to send CBFi to server to complete the data outsourcing.


### 4.2. Outsourcing Computation

After the previous stage ends, server receives the encrypted Bloom filter setsCBFi(i=0,1,…,m) that all the participants send. Server does the following operations in the outsourcing computation stage:for (j=0;j<tn;j++)CBFj=∏i=0mCBFij


### 4.3. Results Query

In the results query stage as shown in Algorithm2, participants query whether one of more data is in the intersection.Algorithm 2:Results query stage.
Participants:Pi, Server Input:Pi inputs query set Q= { q 1 , q 2 , … , q τ }; Server inputs the Bloom filter setCBF of intersection I. Output:Pi gets query results R= { r 1 , r 2 , … , r τ }, if ri=1, then data qi∈I; otherwiseqi∉I. Step  1. Server generates random Bloom filter setRBF and Bloom filter set pair PBF following the steps below. for (j=0;j<tn;j++)  R B F j = R a n d o m ( 0,1 ) l; P B F i = R B F j , C B F j;  Step  2. Pi generates query Bloom filter set Q B F according to query set Q. for (j=0;j<tn;j++) Q B F j = 0; for (j=0;j<Q;j++)  for (δ=0;δ<k;δ++)  Q B F h a s h δ ( q j ) = 1;   Step  3. Pi and Server implement oblivious transfer protocolOTlt. Pi is set to be a Receiver and Server is set to be a Sender. The input ofPi is QBF while the input of Server isPBF. After the oblivious transfer protocol is completed,Pi gets the set ABF. When Q B F j = 0, ABFj=RBFj; when Q B F j = 1, ABFj=CBFj. Step  4. Pi checks whether each element of Q is in the intersection following the steps below. for (j=0;j<τ;j++)  π = { 0 } n; for (δ=0;δ<k;δ++)  π = π ⊕ D e c ( A B F h a s h δ q j )  if (m(mod2) == 0)  if (π=={0}n) r j = 1; else r j = 0;  else  if (π==qj) r j = 1; else r j = 0;


## 4.1. Preprocessing

In the preprocessing stage, the participant generates Bloom filter set corresponding to his private secret set. In order to reduce the probability of false positives, participants share data of secret sets to thek elements of Bloom filter, using XOR secret sharing. We can get the positions of the k elements by hashing. In order to achieve privacy preservation, participants use the GM algorithm to do encryption operations on their respective Bloom filter sets and send them to server. The preprocessing protocol process is as shown in Algorithm 1.Algorithm 1:Preprocessing protocol.
Participants: Pi Input: the input sets of Pi: Si System parameters: k hash functions hashi (i=1,2,…,k) for (j=0;j<t;j++) B F i j = N U L L; / /In the initial state, the Bloom filter set / /of participants is empty for (j=0;j<Si;j++)  π = N U L L; for (δ=0;δ<k;δ++)  if (BFihashδ(Si(j))==NULL)  π = h a s h δ S i j; B F i h a s h δ S i j = R a n d o m ( 0,1 ) n; / /generate random numbers / /with the length of n;  if (π==NULL) Return error1; //error else B F i π = S i j ⊕ B F i h a s h 1 S i j  ⊕ B F i h a s h 2 S i j  ⊕ ⋯ ⊕ B F i h a s h k ( S i ( j ) )   ε = 0; for (j=0;j<t;j++)  if (BFij==NULL) B F i j = R a n d o m ( 0,1 ) n; for (μ=0;μ<n;μ++)  ε = ε + 1; C B F i ε = E n c B F i j μ; / / B F i j μ represents the μth / /bit in BFij;After the previous computation, participantPi gets encrypted Bloom filter set CBFi, and Pi needs to send CBFi to server to complete the data outsourcing.


## 4.2. Outsourcing Computation

After the previous stage ends, server receives the encrypted Bloom filter setsCBFi(i=0,1,…,m) that all the participants send. Server does the following operations in the outsourcing computation stage:for (j=0;j<tn;j++)CBFj=∏i=0mCBFij


## 4.3. Results Query

In the results query stage as shown in Algorithm2, participants query whether one of more data is in the intersection.Algorithm 2:Results query stage.
Participants:Pi, Server Input:Pi inputs query set Q= { q 1 , q 2 , … , q τ }; Server inputs the Bloom filter setCBF of intersection I. Output:Pi gets query results R= { r 1 , r 2 , … , r τ }, if ri=1, then data qi∈I; otherwiseqi∉I. Step  1. Server generates random Bloom filter setRBF and Bloom filter set pair PBF following the steps below. for (j=0;j<tn;j++)  R B F j = R a n d o m ( 0,1 ) l; P B F i = R B F j , C B F j;  Step  2. Pi generates query Bloom filter set Q B F according to query set Q. for (j=0;j<tn;j++) Q B F j = 0; for (j=0;j<Q;j++)  for (δ=0;δ<k;δ++)  Q B F h a s h δ ( q j ) = 1;   Step  3. Pi and Server implement oblivious transfer protocolOTlt. Pi is set to be a Receiver and Server is set to be a Sender. The input ofPi is QBF while the input of Server isPBF. After the oblivious transfer protocol is completed,Pi gets the set ABF. When Q B F j = 0, ABFj=RBFj; when Q B F j = 1, ABFj=CBFj. Step  4. Pi checks whether each element of Q is in the intersection following the steps below. for (j=0;j<τ;j++)  π = { 0 } n; for (δ=0;δ<k;δ++)  π = π ⊕ D e c ( A B F h a s h δ q j )  if (m(mod2) == 0)  if (π=={0}n) r j = 1; else r j = 0;  else  if (π==qj) r j = 1; else r j = 0;


## 5. Theoretical Analysis

In this section, we analyze the correctness, error probability, security, and performance of the protocol and compare the results with the existing ones.


### 5.1. Correctness

Theorem 2.
When the participant is able to construct the Bloom filter successfully, the proposed set intersection secure outsourcing protocol is correct.Proof.
∀ q ∈ I, then, for i=1,2,…,m, there is(8)q∈Siaswellas⨁j=0k-1BFihashjq=q.Because GM algorithm has a characteristic of XOR homomorphies, for j=0,1,…,k-1, there is(9)CBFhashjq=Enc⨁i=1mBFihashjq.When participants query whether q is in the set intersection, for j=0,1,…,k-1, there is(10)QBFhashjq=1.So participants use extended oblivious transfer protocol to get the set ABF, and there is(11)ABFhashjq=CBFhashjq.We can know from (9) and (11) that(12)DecABFhashjq=⨁i=1mBFihashjq.So(13)π=⨁δ=0k-1DecABFhashδq=⨁δ=0k-1⨁i=1mBFihashδq=⨁i=1m⨁δ=0k-1BFihashδq=⨁1mq.So when m is even, π={0}n; when m is odd, π=q.
Similarly, ifq∉I, when m is even, π≠{0}n; when m is odd, π≠q.
The proof is finished.


### 5.2. Error Probability

Theorem 3.
The probability that participantPi constructs Bloom filter set based on XOR secret sharing successfully is(14)P=1-p1h×1+Ohp1ln⁡t-hln⁡p1tin which p1=1-(1-1/t)h(Si-1).Proof.
The necessary and sufficient condition that participantsPi are unable to map their data x of their secret sets to the Bloom filter set when building a Bloom filter set based on XOR secret sharing is that the k positions in Bloom filter data x gets after being mapped by k hash functions are occupied. And the necessary and sufficient condition of general Bloom filters with false positive authentication is that all the k positions data y gets after being mapped by k hash functions are all set to one. Thus, the probability of participant Pi being unable to construct a Bloom filter set based on XOR secret sharing is the same as the probability of a generic Bloom filter set with false positive. From [29] we can see that the probability is p′=p1h×(1+O(h/p1ln⁡t-hln⁡p1/t)), in which p1=1-1-1/thSi-1. Thus, the probability of participant Pi successfully constructing a Bloom filter set based on XOR secret sharing is P=1-p1h×(1+O(h/p1ln⁡t-hln⁡p1/t)).
The proof is finished.Theorem 4.
After the participant constructs Bloom filter successfully, the false positive error probability is(1/2)n.Proof.
∀ x ∉ I, when the result is x∈I, then there will be false positive verification. Consider the following matrix:(15)Z=BF_x11BF_x12⋯BF_x1kBF_x21BF_x22⋯BF_x2k⋮⋮⋱⋮BF_xm1BF_xm2⋯BF_xmkin which BF_xij=BFihashj(x).
If the number of participantsm is even, ⨁i=1m(⨁j=1kBF_xij)={0}n. We can know from the process of construction that the probability is (1/2)n; if it is odd, ⨁i=1m(⨁j=1kBF_xij)=x; the probability is also (1/2)n.
In conclusion, the probability of false positive error is(1/2)n after the participant constructs the Bloom filter successfully in this scheme.
The proof is finished.


### 5.3. Security

Theorem 5.
Assuming that the underlying GM homomorphic encryption scheme and the OT protocol are secure under the semihonest model, the proposed set intersection security outsourcing protocol safely implements the outsourcing computation of the participant’s secret set under the semihonest model.Proof.
The protocol proposed in this paper is asymmetric, which means only the participant is informed of the result. So(16)fS1,S2,…,Sm,Q≝fPS1,S2,…,Sm,Q,fSS1,S2,…,Sm≝fPS1,S2,…,Sm,Q,Λin which Λ means empty strings and π means the proposed security outsourcing protocol. The security analysis is performed from the server view and the participant view, respectively, as follows.
Server View. First analyze the situation where the serve is attacked. During the execution of the protocol π, the server’s view is(17)viewsπS1,S2,…,Sm,Q=Λ,rs,CBF1,CBF2,…,CBFm,CBF,PBF,viewsOTin which Λ means output of the server and {CBF1,CBF2,…,CBFm,CBF,PBF,viewsOT} means the view of the server in the protocol.
Create the simulatorSimS as follows. SimS receives the output Λ of the server and simulates behavior of the server in the protocol. First, SimS generates even-distributed random toss rSim and generates CBF1′,CBF2′,…,CBFm′ in accordance with the following rules:fori=0;j<m;i++
forj=0;j<t;j++
CBFi′j←EncRandom0,1n
ThenSimS calculates CBF′ according to the following rules:forj=0;j<t;j++
CBF′j=∏i=0mCBFi′j
ThenSimS generates intermediate information PBF′ of the results query stage:forj=0;j<t;j++
PBF′i=Random(0,1)l,CBF′j
Finally,SimS simulates the oblivious transfer protocol of results query stage, using PBF′ as input and Λ as output, and generates the view viewSimOT.
After the whole simulation completes,SimS outputs the simulation view:(18)viewsimSπ=Λ,rSim,CBF1′,CBF2′,…,CBFm′,CBF′,PBF′,viewSimOT.rSim and rs are distributed uniformly, so(19)rSim≡crs.It is assumed that the GM encryption scheme is safe under the semihonest model, and the introduction of random numbers in the GM scheme makes ciphertexts of the GM encryption scheme indistinguishable, so(20)CBF1′,CBF2′,…,CBFm′,CBF′,PBF′≡cCBF1,CBF2,…,CBFm,CBF,PBF.In the results query stage, as for the oblivious transfer protocol, the input information PBF′ of SimS and the server’s input information PBF have indistinguishability, and we assume that the underlying OT protocol in the semihonest model is safe, so(21)viewSimOT≡cviewsOT.In conclusion,(22)viewsimSπSs,Sc≡cviewsπ.Participant View. Now we analyze the situation where participant P1 is attacked. The participant view in protocol π is(23)viewP1πS1,S2,…,Sm,Q=S1,Q,R,rP,CBF1,QBF,ABF,viewPOTin which S1 and Q are the input information of P1, while R is the output information of P1.
And{rP,CBF1,QBF,ABF,viewPOT} is the information view generated by P1 in the protocol.
We describe construction of simulatorSimP as follows. SimP receives the input information S1 and the output R of P1 and simulates the behavior of the protocol P1 in the protocol. First, SimP generates a uniform distribution of random toss rSim and generates the encrypted Bloom filter set CBF1′ following steps of the protocol according to inputs. In the results query stage, SimP generates the query Bloom filter QBF′ following steps of the protocol using Q as input. SimP simulates and generates ABF′ according to output R  (see Algorithm 3).
Finally,SimP simulates the oblivious transfer protocol in the results query stage using QBF′ as input and ABF′ as output and generates the view viewSimOT.
After the whole protocol simulation is completed,SimP outputs the simulation view(24)viewsimPπ=S1,Q,R,rSim,CBF1′,QBF′,ABF′,viewSimOT.rSim and rP are distributed uniformly, so(25)rSim≡crP.It is assumed that the GM encryption scheme is safe under the semihonest model, and the introduction of random numbers in the GM scheme makes ciphertexts of the GM encryption scheme indistinguishable, so(26)CBF1′,QBF′,ABF′≡cCBF1,QBF,ABF.In the process of generating the query Bloom filter, according to steps of the protocol, when inputs are the same, there will be identical query Bloom filter sets, so QBF=QBF′.
In the results query stage, as for the oblivious transfer protocol, the input informationQBF′ of SimS and the server’s input information QBF are the same. The output ABF′ of SimP and the input ABF of participants are indistinguishable. We assume that the underlying OT protocol under the semihonest model is safe, so(27)viewSimOT≡cviewPOT.In conclusion,(28)viewsimPπ≡cviewP1π.So we can say that the proposed protocol under semihonest model is safe.
The proof is finished.Algorithm 3
for (j=0;j<t;j++) P A B F j = N U L L; for (j=0;j<Q;j++)  π = N U L L; if (R(j)==1)  for (δ=0;δ<k;δ++)  if (PABFihashδ(Q(j))==NULL)  π = h a s h δ Q j; P A B F i h a s h δ Q j = R a n d o m ( 0,1 ) n;   P A B F i π = S i j ⊕ ( ⨁ μ = 1 k P A B F i h a s h μ Q j )   for (j=0;j<t;j++)  if (PABFij==NULL) P A B F i j = R a n d o m ( 0,1 ) n; A B F ′ ( j ) = E n c P A B F i j;


### 5.4. Performance Analysis

Now we analyze the efficiency of the protocol from two aspects: computational complexity and communication complexity.


#### 5.4.1. Computational Complexity

As for each participantPi, the hash operation is performed kSi times during the preprocessing stage, and the GM encryption operates kn times; during the results query stage, it is hashed kQi times and does OTlt operation once, while the GM decryption operation is performed at most knQi times. As for the server, the ciphertext multiplication operation is performed tmn times in the outsourcing computation stage in all; OTlt is performed once in the results query stage.When implementingOTlt using extended OT technology [27], Receiver needs to perform 2λ times of public key operations and 1.44hs times of hash operations. Sender needs to perform λ times of public key operations and 1.44hs times of hash operations, in which λ represents the security parameter of extended OT protocol. When using the GM algorithm, the encryption operation needs to perform one modular multiplication while the decryption operation needs to perform one modular multiplication, and the multiplication of ciphertexts requires one modular multiplication. Therefore, the participant in this scheme needs to implement the public key algorithm kn+knQi+2λ times and the hash algorithm 1.44ks times; the server needs to implement the public key algorithm tmn+λ times and the hash algorithm kSi+kQi+1.44ks times.


#### 5.4.2. Communication Complexity

At the end of preprocessing stage, each participant sendstl bits data to the server, and the server receives tlm bits data in all. In the results query stage, the participant and the server transfer 2λt bits of data, respectively.


## 5.1. Correctness

Theorem 2.
When the participant is able to construct the Bloom filter successfully, the proposed set intersection secure outsourcing protocol is correct.Proof.
∀ q ∈ I, then, for i=1,2,…,m, there is(8)q∈Siaswellas⨁j=0k-1BFihashjq=q.Because GM algorithm has a characteristic of XOR homomorphies, for j=0,1,…,k-1, there is(9)CBFhashjq=Enc⨁i=1mBFihashjq.When participants query whether q is in the set intersection, for j=0,1,…,k-1, there is(10)QBFhashjq=1.So participants use extended oblivious transfer protocol to get the set ABF, and there is(11)ABFhashjq=CBFhashjq.We can know from (9) and (11) that(12)DecABFhashjq=⨁i=1mBFihashjq.So(13)π=⨁δ=0k-1DecABFhashδq=⨁δ=0k-1⨁i=1mBFihashδq=⨁i=1m⨁δ=0k-1BFihashδq=⨁1mq.So when m is even, π={0}n; when m is odd, π=q.
Similarly, ifq∉I, when m is even, π≠{0}n; when m is odd, π≠q.
The proof is finished.


## 5.2. Error Probability

Theorem 3.
The probability that participantPi constructs Bloom filter set based on XOR secret sharing successfully is(14)P=1-p1h×1+Ohp1ln⁡t-hln⁡p1tin which p1=1-(1-1/t)h(Si-1).Proof.
The necessary and sufficient condition that participantsPi are unable to map their data x of their secret sets to the Bloom filter set when building a Bloom filter set based on XOR secret sharing is that the k positions in Bloom filter data x gets after being mapped by k hash functions are occupied. And the necessary and sufficient condition of general Bloom filters with false positive authentication is that all the k positions data y gets after being mapped by k hash functions are all set to one. Thus, the probability of participant Pi being unable to construct a Bloom filter set based on XOR secret sharing is the same as the probability of a generic Bloom filter set with false positive. From [29] we can see that the probability is p′=p1h×(1+O(h/p1ln⁡t-hln⁡p1/t)), in which p1=1-1-1/thSi-1. Thus, the probability of participant Pi successfully constructing a Bloom filter set based on XOR secret sharing is P=1-p1h×(1+O(h/p1ln⁡t-hln⁡p1/t)).
The proof is finished.Theorem 4.
After the participant constructs Bloom filter successfully, the false positive error probability is(1/2)n.Proof.
∀ x ∉ I, when the result is x∈I, then there will be false positive verification. Consider the following matrix:(15)Z=BF_x11BF_x12⋯BF_x1kBF_x21BF_x22⋯BF_x2k⋮⋮⋱⋮BF_xm1BF_xm2⋯BF_xmkin which BF_xij=BFihashj(x).
If the number of participantsm is even, ⨁i=1m(⨁j=1kBF_xij)={0}n. We can know from the process of construction that the probability is (1/2)n; if it is odd, ⨁i=1m(⨁j=1kBF_xij)=x; the probability is also (1/2)n.
In conclusion, the probability of false positive error is(1/2)n after the participant constructs the Bloom filter successfully in this scheme.
The proof is finished.


## 5.3. Security

Theorem 5.
Assuming that the underlying GM homomorphic encryption scheme and the OT protocol are secure under the semihonest model, the proposed set intersection security outsourcing protocol safely implements the outsourcing computation of the participant’s secret set under the semihonest model.Proof.
The protocol proposed in this paper is asymmetric, which means only the participant is informed of the result. So(16)fS1,S2,…,Sm,Q≝fPS1,S2,…,Sm,Q,fSS1,S2,…,Sm≝fPS1,S2,…,Sm,Q,Λin which Λ means empty strings and π means the proposed security outsourcing protocol. The security analysis is performed from the server view and the participant view, respectively, as follows.
Server View. First analyze the situation where the serve is attacked. During the execution of the protocol π, the server’s view is(17)viewsπS1,S2,…,Sm,Q=Λ,rs,CBF1,CBF2,…,CBFm,CBF,PBF,viewsOTin which Λ means output of the server and {CBF1,CBF2,…,CBFm,CBF,PBF,viewsOT} means the view of the server in the protocol.
Create the simulatorSimS as follows. SimS receives the output Λ of the server and simulates behavior of the server in the protocol. First, SimS generates even-distributed random toss rSim and generates CBF1′,CBF2′,…,CBFm′ in accordance with the following rules:fori=0;j<m;i++
forj=0;j<t;j++
CBFi′j←EncRandom0,1n
ThenSimS calculates CBF′ according to the following rules:forj=0;j<t;j++
CBF′j=∏i=0mCBFi′j
ThenSimS generates intermediate information PBF′ of the results query stage:forj=0;j<t;j++
PBF′i=Random(0,1)l,CBF′j
Finally,SimS simulates the oblivious transfer protocol of results query stage, using PBF′ as input and Λ as output, and generates the view viewSimOT.
After the whole simulation completes,SimS outputs the simulation view:(18)viewsimSπ=Λ,rSim,CBF1′,CBF2′,…,CBFm′,CBF′,PBF′,viewSimOT.rSim and rs are distributed uniformly, so(19)rSim≡crs.It is assumed that the GM encryption scheme is safe under the semihonest model, and the introduction of random numbers in the GM scheme makes ciphertexts of the GM encryption scheme indistinguishable, so(20)CBF1′,CBF2′,…,CBFm′,CBF′,PBF′≡cCBF1,CBF2,…,CBFm,CBF,PBF.In the results query stage, as for the oblivious transfer protocol, the input information PBF′ of SimS and the server’s input information PBF have indistinguishability, and we assume that the underlying OT protocol in the semihonest model is safe, so(21)viewSimOT≡cviewsOT.In conclusion,(22)viewsimSπSs,Sc≡cviewsπ.Participant View. Now we analyze the situation where participant P1 is attacked. The participant view in protocol π is(23)viewP1πS1,S2,…,Sm,Q=S1,Q,R,rP,CBF1,QBF,ABF,viewPOTin which S1 and Q are the input information of P1, while R is the output information of P1.
And{rP,CBF1,QBF,ABF,viewPOT} is the information view generated by P1 in the protocol.
We describe construction of simulatorSimP as follows. SimP receives the input information S1 and the output R of P1 and simulates the behavior of the protocol P1 in the protocol. First, SimP generates a uniform distribution of random toss rSim and generates the encrypted Bloom filter set CBF1′ following steps of the protocol according to inputs. In the results query stage, SimP generates the query Bloom filter QBF′ following steps of the protocol using Q as input. SimP simulates and generates ABF′ according to output R  (see Algorithm 3).
Finally,SimP simulates the oblivious transfer protocol in the results query stage using QBF′ as input and ABF′ as output and generates the view viewSimOT.
After the whole protocol simulation is completed,SimP outputs the simulation view(24)viewsimPπ=S1,Q,R,rSim,CBF1′,QBF′,ABF′,viewSimOT.rSim and rP are distributed uniformly, so(25)rSim≡crP.It is assumed that the GM encryption scheme is safe under the semihonest model, and the introduction of random numbers in the GM scheme makes ciphertexts of the GM encryption scheme indistinguishable, so(26)CBF1′,QBF′,ABF′≡cCBF1,QBF,ABF.In the process of generating the query Bloom filter, according to steps of the protocol, when inputs are the same, there will be identical query Bloom filter sets, so QBF=QBF′.
In the results query stage, as for the oblivious transfer protocol, the input informationQBF′ of SimS and the server’s input information QBF are the same. The output ABF′ of SimP and the input ABF of participants are indistinguishable. We assume that the underlying OT protocol under the semihonest model is safe, so(27)viewSimOT≡cviewPOT.In conclusion,(28)viewsimPπ≡cviewP1π.So we can say that the proposed protocol under semihonest model is safe.
The proof is finished.Algorithm 3
for (j=0;j<t;j++) P A B F j = N U L L; for (j=0;j<Q;j++)  π = N U L L; if (R(j)==1)  for (δ=0;δ<k;δ++)  if (PABFihashδ(Q(j))==NULL)  π = h a s h δ Q j; P A B F i h a s h δ Q j = R a n d o m ( 0,1 ) n;   P A B F i π = S i j ⊕ ( ⨁ μ = 1 k P A B F i h a s h μ Q j )   for (j=0;j<t;j++)  if (PABFij==NULL) P A B F i j = R a n d o m ( 0,1 ) n; A B F ′ ( j ) = E n c P A B F i j;


## 5.4. Performance Analysis

Now we analyze the efficiency of the protocol from two aspects: computational complexity and communication complexity.


### 5.4.1. Computational Complexity

As for each participantPi, the hash operation is performed kSi times during the preprocessing stage, and the GM encryption operates kn times; during the results query stage, it is hashed kQi times and does OTlt operation once, while the GM decryption operation is performed at most knQi times. As for the server, the ciphertext multiplication operation is performed tmn times in the outsourcing computation stage in all; OTlt is performed once in the results query stage.When implementingOTlt using extended OT technology [27], Receiver needs to perform 2λ times of public key operations and 1.44hs times of hash operations. Sender needs to perform λ times of public key operations and 1.44hs times of hash operations, in which λ represents the security parameter of extended OT protocol. When using the GM algorithm, the encryption operation needs to perform one modular multiplication while the decryption operation needs to perform one modular multiplication, and the multiplication of ciphertexts requires one modular multiplication. Therefore, the participant in this scheme needs to implement the public key algorithm kn+knQi+2λ times and the hash algorithm 1.44ks times; the server needs to implement the public key algorithm tmn+λ times and the hash algorithm kSi+kQi+1.44ks times.


### 5.4.2. Communication Complexity

At the end of preprocessing stage, each participant sendstl bits data to the server, and the server receives tlm bits data in all. In the results query stage, the participant and the server transfer 2λt bits of data, respectively.


## 5.4.1. Computational Complexity

As for each participantPi, the hash operation is performed kSi times during the preprocessing stage, and the GM encryption operates kn times; during the results query stage, it is hashed kQi times and does OTlt operation once, while the GM decryption operation is performed at most knQi times. As for the server, the ciphertext multiplication operation is performed tmn times in the outsourcing computation stage in all; OTlt is performed once in the results query stage.When implementingOTlt using extended OT technology [27], Receiver needs to perform 2λ times of public key operations and 1.44hs times of hash operations. Sender needs to perform λ times of public key operations and 1.44hs times of hash operations, in which λ represents the security parameter of extended OT protocol. When using the GM algorithm, the encryption operation needs to perform one modular multiplication while the decryption operation needs to perform one modular multiplication, and the multiplication of ciphertexts requires one modular multiplication. Therefore, the participant in this scheme needs to implement the public key algorithm kn+knQi+2λ times and the hash algorithm 1.44ks times; the server needs to implement the public key algorithm tmn+λ times and the hash algorithm kSi+kQi+1.44ks times.


## 5.4.2. Communication Complexity

At the end of preprocessing stage, each participant sendstl bits data to the server, and the server receives tlm bits data in all. In the results query stage, the participant and the server transfer 2λt bits of data, respectively.


## 6. Comparison

There are a number of different parameters due to the fact that existing privacy-preserving set intersection outsourcing protocols are different from privacy-preserving set intersection protocols in principle. Parameters are instantiated in order to compare efficiency of protocols. Common parameters: the sizes of the participant sets are alls. k=8, t=sk/ln22, and l=100. In the proposed protocol, the query set Q=S; the Kerschbaum scheme [15] can only achieve security outsourcing computation of two participants, so m=2 in this scheme; the length of ciphertexts in XOR secret sharing is n=8. And, in the Kerschbaum scheme, β=8. Construction and query of Bloom filter are based on Dong’s open source experimental model [13], which uses SHA-1 to instantiate hash functions; OT protocol uses classical Naor-Pinkas scheme [30].After summarizing and comparing the existing algorithms in Figure2 and Table 1, we can see the following. (1) The computational complexity and the communication complexity are lower than that of Huang’s scheme and similar to that of Dong’s. Also it is slightly lower than Kerschbaum’s. (2) The false positive probability is higher than that of Huang’s, but the same as Dong’s and Kerschbaum’s scheme. (3) The proposed algorithm solves the problem of privacy preservation in outsourcing computation considering the cloud computing environment; in the Kerschbaum scheme, a participant is needed to be the server, so it is a traditional secure computation model; in Huang’s and Dong’s scheme, traditional secure computation model is used to solve PSI problem. (4) The proposed algorithm can solve the secure outsourcing computation with two or more participants, while the others can only deal with the situation of two. (5) It does not need all the participants being online at real time in the proposed algorithm, while the others need them to be online in order to complete the computation at the same time.Table 1
Comparison of protocols in applicability.
Comparison of algorithms Number of participants System model Online necessary or not Dong et al. [13] 2 Traditional Secure Multiparty Computation model Yes Huang et al. [19] 2 Traditional Secure Multiparty Computation model Yes Kerschbaum [15] 2 Traditional Secure Multiparty Computation model Yes The proposed algorithm ≥2 Outsourcing computation model NoFigure 2
Comparison of protocols in complexity and false positive probability.In the comparison, we can know from Figure2 that our algorithm can deal with privacy preservation in outsourcing computation without increasing computational complexity, communication complexity, and false positive probability. In addition, as shown in Table 1, it has great advantages considering the limit of some factors, such as the number of participants, sizes of inputs, and requirement of being online. So, to a large extent, the proposed algorithm improves the solution of privacy preservation in cloud computing.


## 7. Conclusion

In this paper, we propose a privacy-preserving outsourcing computation system model which can be used in multimedia processing based on cloud computing to solve security and correctness problems. Based on this model, we design a privacy-preserving set intersection outsourcing computation protocol based on GM homomorphic encryption scheme and Bloom filter. The results show that the proposed protocol achieves privacy preservation in the outsourcing computation without increasing computational complexity, the communication complexity, and the false positive probability. And the protocol does not limit the number of participants, the input secret sizes, and whether participant is online in real time. Obviously, not only is the method proposed suitable for multimedia processing, but also it can be used for cloud computing, distributed computing, Internet of things, virtual property transactions, and so on.In the next few years, we will continue designing the privacy-preserving set intersection outsourcing computation protocol and extending its application in cloud computing. We will focus on the further improvement of efficiency of the algorithm, as well as the design of algorithms against malicious attackers.



---

*Source: 5841967-2018-04-05.xml*