Cryptology ePrint Archive: Report 2007/111

Privacy-Preserving Distributed Set Intersection

Qingsong Ye and Huaxiong Wang and Christophe Tartary

Abstract: With the growing demand of databases outsourcing and its security concerns, we investigate privacy-preserving set intersection in a distributed scenario. We propose a one-round protocol for privacy-preserving set intersection based on a combination of secret sharing scheme and homomorphic encryption. We then show that, with an extra permutation performed by each of contacted servers, the cardinality of set intersection can be computed efficiently. All protocols constructed in this paper are provably secure against a semi-honest adversary under the Decisional Diffie-Hellman assumption.

Category / Keywords: cryptographic protocols / privacy-preserving set intersection, homomorphic encryption

Date: received 26 Mar 2007, last revised 16 Jul 2007

Contact author: qingsong at ics mq edu au

Available formats: Postscript (PS) | Compressed Postscript (PS.GZ) | PDF | BibTeX Citation

Version: 20070717:034859 (All versions of this report)

Discussion forum: Show discussion | Start new discussion