EFFICIENT DELEGATED PRIVATE SET INTERSECTION ON OUTSOURCED PRIVATE DATASETS
ABSTRACT
Private set intersection (PSI) is an essential cryptographic protocol that has many real world applications. As cloudcomputing power and popularity have been swiftly growing, it is now desirable to leverage the cloud to store private datasets anddelegate PSI computation to it. Although a set of efficient PSI protocols have been designed, none support outsourcing of the datasetsand the computation. In this paper, we propose two protocols for delegated PSI computation on outsourced private datasets. Ourprotocols have a unique combination of properties that make them particularly appealing for a cloud computing setting. Our firstprotocol, O-PSI, satisfies these properties by using additive homomorphic encryption and point-value polynomial representation of aset. Our second protocol, EO-PSI, is mainly based on a hash table and point-value polynomial representation and it does not requirepublic key encryption; meanwhile, it retains all the desirable properties and is much more efficient than the first one. We also provide aformal security analysis of the two protocols in the semi-honest model and we analyze their performance utilizing prototypeimplementations we have developed. Our performance analysis shows that EO-PSI scales well and is also more efficient than similarstate-of-the-art protocols for large set sizes.
EXISTING SYSTEM:
Private Set Intersection (PSI) was initially introduced in . Followingthat many protocols such as were proposed. A them, provides a numberof protocols supporting further private set operations based onadditive homomorphic encryption and polynomial representationof sets. In, the first PSI protocols with linear complexity(in the semi-honest and malicious models respectively) wereproposed. In addition, proposed PSI protocols that allowresult recipients to hide their set size from the other party duringthe computation of the intersection, while also proposedprotocols that output only the cardinality of the intersection.More recently, some efficient protocols, like, havebeen proposed. The protocols in use Bloom filters, secretsharing and oblivious transfer to offer efficient PSI. Later on, extended by using hash tables and a more efficient oblivioustransfer extension protocol for better efficiency. Recently, further improved the efficiency of by utilizing permutationbasedhashing. Nevertheless, all these regular PSI protocols areinteractive, which means clients jointly compute the intersectionusing locally available datasets. In general, they do not supportoutsourcing of the data and the computation to a third party (e.g.the cloud) without non-trivial modifications. For example in ,both parties can send encrypted sets to the cloud and let the cloudcompute the intersection. However, by doing so the cloud learnsthe cardinality of the intersection. Also, the parties must re-encrypttheir data if they want to compute another intersection, otherwisethe cloud can learn even more information about the parties’ sets.
PROPOSED SYSTEM:
we present two protocols for delegated PSI onoutsourced private datasets. Our first protocol, O-PSI, is basedon additive homomorphic encryption and point-value set representation.The protocol lets clients independently outsource theirdatasets by representing them as blinded polynomials. To achievedelegated PSI computation, homomorphic encryption is used to“switch” blinding factors so that the outsourced datasets blindedunder different blinding keys can now be combined in the computationprocess. The protocol ensures that intersections can only becomputed with the permission of all the clients and that the result(i.e. the intersection and its cardinality) will be protected from thecloud. The protocol also allows the datasets to be used securely anunlimited number of times without the need to secure them again.Although O-PSI has all the desirable properties, it is somewhatinefficient, as it requires costly homomorphic encryption (operations)which has a major impact on its performance. To mitigatethis problem, we propose a more efficient protocol, EO-PSI, thatpreserves all O-PSI’s desirable characteristics, while requires nopublic key encryption or exponentiation operations. The protocolalso lets clients outsource their datasets by representing them asblinded polynomials. However, by changing the way the blindingis done and the interaction between the clients, the protocol nolonger needs to “switch” blinding factors in order to combinethe outsourced datasets in the computation process. We furtherimprove the protocol performance by leveraging hash tables. As aresult, EO-PSI is 1 – 2 orders of magnitude faster than O-PSI. Wealso provide a formal security analysis of the two protocols, andanalyze their performance based on prototype implementationswe have developed. Our performance analysis shows that EO-PSIscales well and it performs better than not only O-PSI but alsoother similar state-of-the-art protocols when the dataset is large.
CONCLUSIONS
Cloud computing is rapidly gaining in popularity a individualsand businesses, mainly due to the innovation it enablesand the opportunities it offers. With its importance increasing,outsourcing datasets and computation to the cloud becomes anappealing approach. Nevertheless, as the cloud cannot be fullytrusted the privacy of the outsourced data is a major concernfor clients. So, the need arises for protocols that can carry outprivate set operations on outsourced private data without revealinganything about the data and the computation results to the cloud.In this paper, we presented two such protocols for privateset intersection, O-PSI and EO-PSI. The protocols let clientsindependently prepare and outsource their private datasets to thecloud. At any point later in time, they can ask the cloud to run PSIon their private datasets. In this process, the cloud learns nothingabout the dataset elements, the intersection, and the intersectioncardinality. Furthermore, the protocols ensure that the cloud cancompute the intersection only when all the clients agree and theclients can securely delegate PSI computation on the outsourceddatasets an unlimited number of times with no need to downloadand re-prepare the datasets. These properties make the protocolsparticularly suitable for a cloud computing setting, allowing clientsto fully benefit from the increased collaboration the cloud enablesand the cost-efficient resources it provides without sacrificing theirprivacy.
REFERENCES
1545-5971 (c) 2016 IEEE. Personal use is permitted, but republication/redistribution requires IEEE permission. See http://www.ieee.org/publications_standards/publications/rights/index.html for more information.219
[1] A. Abadi, S. Terzis, and C. , “O-PSI: delegated private set intersectionon outsourced datasets,” in 30th IFIP TC11 International Conferenceon ICT Systems Security and Privacy Protection (SEC), 2015, pp. 3–17.
[2] M. J. Freedman, K. Nissim, and B. Pinkas, “Efficient private matchingand set intersection,” in EUROCRYPT, 2004, pp. 1–19.
[3] C. C. Aggarwal and P. S. Yu, Eds., Privacy-Preserving Data Mining Modelsand Algorithms, ser. Advances in Database Systems. Springer,2008, vol. 34.
[4] E. D. Cristofaro, J. Kim, and G. Tsudik, “Linear-complexity private setintersection protocols secure in malicious model,” in ASIACRYPT, 2010,pp. 213–231.
[5] G. Mezzour, A. Perrig, V. D. Gligor, and P. Papadimitratos, “Privacypreservingrelationship path discovery in social networks,” in CANS,2009, pp. 189–208.
[6] S. Nagaraja, P. Mittal, C. Hong, M. Caesar, and N. Borisov, “BotGrep:Finding P2P bots with structured graph analysis,” in USENIX SecuritySymposium, 2010, pp. 95–110.
[7] S. Marston, Z. Li, S. Bandyopadhyay, and A. Ghalsasi, “Cloud computing- the business perspective,” in HICSS-44, 2011, pp. 1–11.
[8] J. Webster, “An enterprise cloud ‘survey of surveys’,” Forbes, 2016.[Online]. Available: http://www.forbes.com/sites/johnwebster/2016/05/03/an-enterprise-cloud-survey-of-surveys/
[9] O. Annenko, “Enterprise cloud adoption: It’s high time werun the first reality check,” elastic.io, 2016. [Online]. Available:https://www.elastic.io/enterprise-cloud-adoption-reality-check/
[10] X. Chen, J. Li, X. Huang, J. Ma, and W. Lou, “New publicly verifiabledatabases with efficient updates,” IEEE Trans. Dependable Sec. Comput.,vol. 12, no. 5, pp. 546–556, 2015.