High-Performance and Secure Jaccard Similarity Estimation for Cloud Storage
Zequn Xie, Wenlong Tian, Jianfeng Lu, Weijun Xiao, Zhiyong Xu · 2025
Detecting similar data is crucial for optimizing file storage and transmission in HTTP protocols and Content Delivery Networks.Traditional MinHash methods encounter significant efficiency challenges due to their reliance on K-shingle structures, resulting in high computational costs and storage requirements.Additionally, these methods expose privacy risks in cloud environments, where sensitive information can be inferred from MinHash signatures.To address both efficiency and security concerns, we propose Horse-MinHash, which integrates a fast, content-defined feature extraction scheme with a non-interactive zero-knowledge proof-based similarity estimation method.Our approach significantly enhances computational efficiency while ensuring robust privacy protection by preventing plaintext exposure.Experimental results demonstrate that Horse-MinHash achieves lower mean squared error in Jaccard similarity estimation and reduces time overhead for average block sizes of 16KB or more, outperforming state-of-the-art methods.