Efficient and Scalable Privacy-Preserving Similar Document Detection
Xiaojie Yu, Xiaojun Chen, Jinqiao Shi, Liyan Shen, Dakui Wang · 2017
Similar document detection has been well studied for many applications, such as file management systems, plagiarism and double submission detection. Traditional detection algorithms are challenged by the privacy-preserving problems. Recently, privacy-preserving similar document detection between two parties gains more attention. However, most of the existing works mainly focus on computing similarity between two documents, and they are inefficient with O(n2) computation complexity when processing secure comparison between two n-document sets. Focusing on this problem, this paper presents a new efficient and scalable privacy-preserving similar document detection protocol based on oblivious multi-garbled Bloom filter intersection and MinHash algorithm. Experimental evaluation shows that when processing large document sets, our protocol still remains linear computation complexity with the scale of document sets increasing and achieves overwhelming computational performance improvement against other major approaches.