High-Performance and Secure Jaccard Similarity Estimation for Cloud Storage

Abstract

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. CCS Concepts Security and privacy File system security; Management and querying of encrypted data.