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