An enhanced MinHash encryption scheme for encrypted deduplication

The encrypted deduplication can provide both storage savings and data confidentiality for cloud storage systems. Convergent encryption (CE) is a well-known solution for encrypted deduplication, but it brings huge computation and storage overheads for key management. MinHash encryption is an effective solution to this issue. It reduces the number of keys by grouping multiple consecutive chunks into segments and generating one key for each segment. However, MinHash encryption does not take full advantage of the segment similarity, which can be used to further reduce the overhead for key management. To this end, we augment MinHash encryption with Bloom filter and Locality Sensitivity Hash (LSH) to design an enhanced MinHash encryption scheme. Firstly, our scheme generates a sketch for each segment based on the Bloom filter, and projects sketches to the points in a hash table through LSH functions. Secondly, we detect the segment similarity by the distance between points, and similar segments are grouped into super-segments. Finally, we combine MinHash encryption and server-aided message-locked encryption to encrypt the super-segments for achieving encrypted deduplication. We conduct trace-driven experiments using a realworld dataset. Compared with MinHash encryption, our scheme has higher storage efficiency and better encryption performance.