Secure Generalized Deduplication via Multi-Key Revealing Encryption

Daniel E. Lucani, Lars Nielsen, Claudio Orlandi, Elena Pagnin, Rasmus Vestergaard

TL;DR

This paper introduces Multi-Key Revealing Encryption (MKRE), a novel cryptographic primitive that enables secure generalized deduplication of encrypted data across multiple users. This allows cloud storage providers to reduce storage costs by identifying and storing similar data chunks, while still preserving user privacy.

What Problem Does This Paper Address?

Cloud storage providers (CSPs) offer cost-effective data storage by employing compression techniques like deduplication. Deduplication works by identifying and storing only one copy of identical data chunks. Generalized deduplication extends this to "similar" chunks, offering even greater compression. However, a naive implementation of generalized deduplication requires CSPs to access data in cleartext, compromising user privacy. Existing encryption schemes that enable secure deduplication typically only support identical data. This paper addresses the challenge of enabling generalized deduplication on encrypted data without sacrificing user privacy, allowing CSPs to compress data across users while ensuring that only the CSP knows which data is similar, and nothing else.

Methods

The core contribution is the Multi-Key Revealing Encryption (MKRE) primitive. MKRE extends the concept of Revealing Encryption (RE) to a multi-user setting, allowing computations on ciphertexts encrypted with different keys. Specifically, for generalized deduplication, MKRE enables a third party (the CSP) to determine if two ciphertexts correspond to "similar" plaintexts, based on a predefined function, without learning anything else about the data.

The authors propose a generic compiler for MKRE that combines three cryptographic building blocks:

  • Message-Locked Encryption (MLE): Used to derive a key from the data's base.
  • Deterministic Secret Key Encryption (DetE): Used to encrypt the derived key.
  • Randomized Secret Key Encryption (RandE): Used to encrypt the data's deviation.

For generalized deduplication, a chunk is split into a "base" (representing common information) and a "deviation" (representing unique information). The MKRE scheme encrypts these parts separately. The Reveal function in MKRE compares the encrypted bases to determine similarity.

The security of their construction is proven in the random oracle model, which they argue is necessary to handle deterministic cryptographic primitives and user corruption.

Datasets

The paper uses a publicly available dataset of 69 high-resolution .tiff images from Plant Labs Inc., totaling approximately 3.5 GB of data. Each image is about 50 MB. This dataset is used to evaluate the performance of their MKRE-based generalized deduplication.

Key Insights and Ideas

  • Bridging the Gap: MKRE successfully bridges the gap between the need for data compression (deduplication) and the requirement for data privacy in cloud storage.
  • Generalized Deduplication on Encrypted Data: The ability to perform generalized deduplication on encrypted data is a significant step towards more efficient and private cloud storage.
  • Revealing Encryption for Similarity: The core idea of MKRE is to reveal only similarity information between ciphertexts, not the data itself. This is crucial for enabling generalized deduplication.
  • Random Oracle Model Necessity: The authors argue that the random oracle model is essential for formally modeling deterministic encryption and handling user corruption in their MKRE scheme, providing a more intuitive security definition.
  • Practical Trade-offs: The implementation demonstrates that the privacy overhead (in terms of compression ratio and throughput) is minimal compared to unencrypted generalized deduplication.

Key Results

  • Compression Ratio: Their MKRE construction achieves a compression ratio of 87% for 1KB file chunks and 82.2% for 8KB chunks. This is only a slight decrease (at most 3%) compared to generalized deduplication on unencrypted data.
  • Throughput: The system's throughput is impacted by MKRE, with a maximum drop of 6.9% for 8KB chunks. This is considered acceptable, especially given that the system is not fully optimized.
  • Security: The proposed MKRE construction is proven simulation secure in the random oracle model.

Limitations and Future Work

  • Random Oracle Model: The security proof relies on the random oracle model, which is an idealized model. While argued as necessary, it means the concrete implementation might not perfectly match the theoretical security guarantees.
  • Information Leakage: MKRE for generalized deduplication inherently leaks information about the distribution of similar data chunks to the CSP. This could potentially impact the security of the system if the CSP performs frequency analysis on deduplication patterns.
  • Centralized vs. Ad-hoc: The paper discusses an ad-hoc approach where users generate keys independently. They suggest a centralized approach as a future direction to mitigate potential dictionary attacks on the base encryption.
  • Other Applications: The authors suggest exploring other applications of MKRE beyond generalized deduplication as a direction for future research.

Summary updated

Abstract

Cloud Storage Providers (CSPs) offer solutions to relieve users from locally storing vast amounts of data, including personal and sensitive ones. While users may desire to retain some privacy on the data they outsource, CSPs are interested in reducing the total storage space by employing compression techniques such as deduplication. We propose a new cryptographic primitive that simultaneously realizes both requirements: Multi-Key Revealing Encryption (MKRE). The goal of MKRE is to disclose the result of a pre-defined function over multiple ciphertexts, even if the ciphertexts were generated using different keys, while revealing nothing else about the data. We present a formal model and a security definition for MKRE and provide a construction of MKRE for generalized deduplication that only uses symmetric key primitives in a black-box way. Our construction allows (a) cloud providers to reduce the storage space by using generalized deduplication to compress encrypted data across users, and (b) each user to maintain a certain privacy level for the outsourced information. Our scheme can be proven secure in the random oracle model (and we argue that this is a necessary evil). We develop a proof-of-concept implementation of our solution. For a test data set, our MKRE construction achieves secure generalized deduplication with a compression ratio of 87% for 1 KB file chunks and 82.2% for 8 KB chunks. Finally, our experiments show that, compared to generalized deduplication setup with un-encrypted files, adding privacy via MKRE introduces a compression overhead of less than $$3\%$$ and reduces the storage throughput by at most $$6.9\%$$ .
BibTeX
@article{lucani2020secure,
  author = {Daniel E. Lucani and Lars Nielsen and Claudio Orlandi and Elena Pagnin and Rasmus Vestergaard},
  title = {{Secure Generalized Deduplication via Multi-Key Revealing Encryption}},
  journal = {IACR Cryptol. ePrint Arch.},
  year = {2020},
  doi = {10.1007/978-3-030-57990-6\_15},
}
Figure