Secure Similar Document Detection: Optimized Computation Using the Jaccard Coefficient

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

Abstract

Secure Similar Document Detection (SSDD) problem considers two parties, each holding a private document, who want to compute the similarity between their documents without leaking the document contents to one another. This is a unique problem whose applications span across a variety of domains, including the medical field, military intelligence, and academia. In this paper, we aim to solve the SSDD problem by representing documents as multisets and using the Jaccard Coefficient (JC) as a similarity measure. We first illustrate how the computation of Jaccard Coefficient can be reduced to the computation of intersection size between the multisets. Then, we propose a novel way to securely approximate the size of intersection between multisets using Bloom filters and hash functions, without significant reductions in security and accuracy. Our proposed protocol exploits a unique property of Bloom filters -that computing the dot product of two Bloom filters yields their intersection size.

Original languageEnglish
Title of host publicationProceedings - 4th IEEE International Conference on Big Data Security on Cloud, BigDataSecurity 2018, 4th IEEE International Conference on High Performance and Smart Computing, HPSC 2018 and 3rd IEEE International Conference on Intelligent Data and Security, IDS 2018
PublisherInstitute of Electrical and Electronics Engineers Inc.
Pages1-4
Number of pages4
ISBN (Electronic)9781538643990
DOIs
Publication statusPublished - 28 Nov 2018
Event4th IEEE International Conference on Big Data Security on Cloud, BigDataSecurity 2018, 4th IEEE International Conference on High Performance and Smart Computing, HPSC 2018 and 3rd IEEE International Conference on Intelligent Data and Security, IDS 2018 - Omaha, United States
Duration: 3 May 20185 May 2018

Publication series

NameProceedings - 4th IEEE International Conference on Big Data Security on Cloud, BigDataSecurity 2018, 4th IEEE International Conference on High Performance and Smart Computing, HPSC 2018 and 3rd IEEE International Conference on Intelligent Data and Security, IDS 2018

Other

Other4th IEEE International Conference on Big Data Security on Cloud, BigDataSecurity 2018, 4th IEEE International Conference on High Performance and Smart Computing, HPSC 2018 and 3rd IEEE International Conference on Intelligent Data and Security, IDS 2018
CountryUnited States
CityOmaha
Period3/05/185/05/18

    Fingerprint

Keywords

  • Bloom filters
  • Jaccard coefficient
  • efficiency
  • multisets
  • security

Cite this

Forman, S., & Samanthula, B. K. (2018). Secure Similar Document Detection: Optimized Computation Using the Jaccard Coefficient. In Proceedings - 4th IEEE International Conference on Big Data Security on Cloud, BigDataSecurity 2018, 4th IEEE International Conference on High Performance and Smart Computing, HPSC 2018 and 3rd IEEE International Conference on Intelligent Data and Security, IDS 2018 (pp. 1-4). [8552273] (Proceedings - 4th IEEE International Conference on Big Data Security on Cloud, BigDataSecurity 2018, 4th IEEE International Conference on High Performance and Smart Computing, HPSC 2018 and 3rd IEEE International Conference on Intelligent Data and Security, IDS 2018). Institute of Electrical and Electronics Engineers Inc.. https://doi.org/10.1109/BDS/HPSC/IDS18.2018.00015