EsPRESSO: Efficient privacy-preserving evaluation of sample set similarity
- 20 March 2014
- journal article
- Published by SAGE Publications in Journal of Computer Security
- Vol. 22 (3) , 355-381
Abstract
Electronic information is increasingly often shared among entities without complete mutual trust. To address related security and privacy issues, a few cryptographic techniques have emerged that support privacy-preserving information sharing and retrieval. One interesting open problem in this context involves two parties that need to assess the similarity of their datasets, but are reluctant to disclose their actual content. This paper presents an efficient and provably-secure construction supporting the privacy-preserving evaluation of sample set similarity, where similarity is measured as the Jaccard index. We present two protocols: the first securely computes the (Jaccard) similarity of two sets, and the second approximates it, using MinHash techniques, with lower complexities. We show that our novel protocols are attractive in many compelling applications, including document/multimedia similarity, biometric authentication and genetic tests. In the process, we demonstrate that our constructions are appreciably more efficient than prior work.Keywords
All Related Versions
This publication has 43 references indexed in Scilit:
- Efficient privacy-preserving similar document detectionThe VLDB Journal, 2010
- Protection and Retrieval of Encrypted Multimedia Content: When Cryptography Meets Signal ProcessingEURASIP Journal on Information Security, 2007
- Security in Mobile Ad-Hoc Networks2005
- Efficient Private Matching and Set Intersection2004
- Verifiable Homomorphic Oblivious Transfer and Private Equality TestLecture Notes in Computer Science, 2003
- Content-based image retrieval at the end of the early yearsIEEE Transactions on Pattern Analysis and Machine Intelligence, 2000
- Filterbank-based fingerprint matchingIEEE Transactions on Image Processing, 2000
- Deformable prototypes for encoding shape categories in image databasesPattern Recognition, 1997
- Image retrieval using color and shapePattern Recognition, 1996
- A Measure of Asymptotic Efficiency for Tests of a Hypothesis Based on the sum of ObservationsThe Annals of Mathematical Statistics, 1952