Computer Science – Cryptography and Security
Scientific paper
2011-11-21
Computer Science
Cryptography and Security
Scientific paper
In today's digital society, electronic information is increasingly shared among different entities, and decisions are made based on common attributes. To address associated privacy concerns, the research community has begun to develop cryptographic techniques for controlled (privacy-preserving) information sharing. One interesting open problem involves two mutually distrustful parties that need to assess the {\em similarity} of their information sets, but cannot disclose their actual content. This paper presents the first efficient and provably-secure construction for privacy-preserving evaluation of sample set similarity, measured as the Jaccard similarity index. We present two protocols: the first securely computes the Jaccard index of two sets, the second approximates it, using MinHash techniques, with lower costs. We show that our novel protocols are attractive in many compelling applications, including document similarity, biometric authentication, personal genetic tests, multimedia file similarity. Finally, we demonstrate, both analytically and experimentally, that our constructions are appreciably more efficient than prior work.
Blundo Carlo
Cristofaro Emiliano de
Gasti Paolo
No associations
LandOfFree
EsPRESSo: Efficient Privacy-Preserving Evaluation of Sample Set Similarity does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with EsPRESSo: Efficient Privacy-Preserving Evaluation of Sample Set Similarity, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and EsPRESSo: Efficient Privacy-Preserving Evaluation of Sample Set Similarity will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-552019