Fast, private and verifiable: Server-aided approximate similarity computation over large-scale datasets

Shuo Qiu, Boyang Wang, Ming Li, Jesse Victors, Jiqiang Liu, Yanfeng Shi, Wei Wang

Research output: Chapter in Book/Report/Conference proceedingConference contribution

3 Scopus citations

Abstract

Computing similarity, especially Jaccard Similarity, between two datasets is a fundamental building block in big data analytics, and extensive applications including genome matching, plagiarism detection, social networking, etc. The increasing user privacy concerns over the release of has sensitive data have made it desirable and necessary for two users to evaluate Jaccard Similarity over their datasets in a privacy-preserving manner. In this paper, we propose two efficient and secure protocols to compute the Jaccard Similarity of two users' private sets with the help of an unfully-trusted server. Specifically, in order to boost the efficiency, we leverage Minhashing algorithm on encrypted data, where the output of our protocols is guaranteed to be a close approximation of the exact value. In both protocols, only an approximate similarity result is leaked to the server and users. The first protocol is secure against a semi-honest server, while the second protocol, with a novel consistencycheck mechanism, further achieves result verifiability against a malicious server who cheats in the executions. Experimental results show that our first protocol computes an approximate Jaccard Similarity of two billion-element sets within only 6 minutes (under 256-bit security in parallel mode). To the best of our knowledge, our consistency-check mechanism represents the very first work to realize an efficient verification particularly on approximate similarity computation.

Original languageEnglish (US)
Title of host publicationSCC 2016 - Proceedings of the 4th ACM International Workshop on Security in Cloud Computing, Co-located with Asia CCS 2016
PublisherAssociation for Computing Machinery, Inc
Pages29-36
Number of pages8
ISBN (Electronic)9781450342858
DOIs
StatePublished - May 30 2016
Event4th ACM International Workshop on Security in Cloud Computing, SCC 2016 - Xi'an, China
Duration: May 30 2016 → …

Publication series

NameSCC 2016 - Proceedings of the 4th ACM International Workshop on Security in Cloud Computing, Co-located with Asia CCS 2016

Conference

Conference4th ACM International Workshop on Security in Cloud Computing, SCC 2016
Country/TerritoryChina
CityXi'an
Period5/30/16 → …

ASJC Scopus subject areas

  • Software

Fingerprint

Dive into the research topics of 'Fast, private and verifiable: Server-aided approximate similarity computation over large-scale datasets'. Together they form a unique fingerprint.

Cite this