Cloud storage providers rely heavily on data deduplication to minimize infrastructure costs. By storing only a single copy of identical files or data chunks across millions of users, systems can achieve massive storage reductions. As highlighted by R. Mashinistov et al. et al. in The HSF Conditions Database Reference Implementation, content-addressable storage naturally facilitates this optimization by using a data payload's checksum to define its storage path.
However, a fundamental tension arises when users encrypt their data before uploading it. Standard probabilistic encryption schemes introduce unique randomness (such as initialization vectors or user-specific keys) so that encrypting the same plaintext twice results in completely different ciphertexts. As observed by Chuan Qin 0009 et al. et al. in The Design and Implementation of a Rekeying-aware Encrypted Deduplication Storage System, Feng Xiang et al. et al. in Image Deduplication Based on Hashing and Clustering in Cloud Storage, and Yuzhao Cui et al. et al. in Attribute-Based Equality Test Over Encrypted Data Without Random Oracles, this ciphertext divergence completely blinds the cloud provider. Because the server cannot distinguish between two identical files encrypted under different keys, it is forced to store both, destroying the benefits of deduplication. This conflict spans across various domains, from medical record systems (Huiqi Zhao et al. et al. in Feasibility study on security deduplication of medical cloud privacy data) to edge-caching wireless networks, where user-specific encryption prevents the reuse of cached content (Wanli Wen in Enhancing Physical Layer Security of Random Caching in Large-Scale Multi-Antenna Heterogeneous Wireless Networks).
Secure data deduplication protocols resolve this conflict by forcing ciphertexts to "converge" deterministically based on the underlying data content, while simultaneously protecting data from unauthorized access and side-channel leaks.
Convergent Encryption: Aligning the Ciphertexts
To allow deduplication on encrypted data, the encryption process must be deterministic across different users. The primary mechanism for achieving this is convergent encryption (or message-locked encryption).
Standard Encryption:
Plaintext (M) + Random Key (K_rand) ──> Unique Ciphertext (C_A)
Plaintext (M) + Random Key (K_bob) ──> Unique Ciphertext (C_B) [No Deduplication]
Convergent Encryption:
Plaintext (M) ──> Hash Function H(M) ──> Key (K_conv)
Plaintext (M) + Key (K_conv) ──────────> Identical Ciphertext (C) [Deduplication Possible]
Instead of selecting a random cryptographic key, the client derives the key directly from the content of the data itself, typically by computing a cryptographic hash of the plaintext ($K = H(M)$). As detailed by Huiqi Zhao et al. et al. in Feasibility study on security deduplication of medical cloud privacy data, when two independent users encrypt the exact same file, they will compute the identical key and generate the identical ciphertext. The cloud provider can then easily identify and deduplicate the redundant data blocks by matching their ciphertext hashes, without ever needing to know the decryption key or the underlying plaintext (Shirole Chetan Ramdas et al. et al. in A Review on Data De-duplication using Blockchain and Advanced Security using Cloud Computing).
To prevent a single compromised storage node from exploiting this determinism, advanced architectures distribute these keys across chunks. For example, Lu Shen et al. et al. in CloudS: A Multi-Cloud Storage System with Multi-Level Security introduce a circular hash-based encryption method. Here, a data chunk's hash serves as its encryption key, but that key is stored inside a different data chunk. This creates an interdependent chain, ensuring that an attacker must compromise multiple storage locations to reconstruct the keys and decrypt the files.
Proofs of Ownership: Preventing Unauthorized Access
While convergent encryption allows the server to detect duplicates, it introduces a dangerous side channel. If the server simply accepts a file's hash as a request to download or link to an existing file, a malicious user who merely guesses or steals a short file hash could gain full access to a file they do not actually possess.
To counteract this, secure deduplication architectures implement Proofs of Ownership (PoW). As formalized by Wee Keong Ng in Private data deduplication protocols in cloud storage, a private deduplication protocol requires the client to interactively prove to the server that they hold the entire original file, rather than just its hash. This is achieved using cryptographic commitments and erasure codes, ensuring the server verifies ownership without gaining any insight into the underlying data content.
As noted by Dapeng Wu et al. et al. in Editorial: Multimedia Transmission and Process in Heterogeneous Network and Xianbin Wang et al. et al. in Mobile cloud computing in 5G: Emerging trends, issues, and challenges [Guest Editorial], these proofs ensure that storage efficiency does not bypass role-based access control or user privacy. Furthermore, to defend against brute-force dictionary attacks where a malicious server attempts to guess predictable files, Jian Liu et al. et al. in Secure Deduplication of Encrypted Data: Refined Model and New Constructions combine Password Authenticated Key Exchange (PAKE) with ciphertext transformations, allowing secure deduplication across different administrative domains without relying on a trusted third party (Baoqi Huang et al. et al. in Editorial: sensing, Service and Security in Mobile Internet (MobilWare 2020)).
Convergent Dispersal: Deduplication in Multi-Cloud Systems
In multi-cloud storage environments, data reliability is typically achieved via secret sharing schemes, which split a file into multiple encrypted shares distributed across different cloud vendors. However, traditional secret sharing relies on choosing random polynomials. This means that even if two users split the exact same file, the random inputs ensure that the resulting shares are entirely different, blocking cross-user deduplication at the cloud level.
Traditional Secret Sharing:
Plaintext (M) + Random Polynomials ──> Unique Shares (S_1, S_2, S_3) [No Cross-User Deduplication]
Convergent Dispersal:
Plaintext (M) ──> Deterministic Hash Key ──> Identical Shares (S_1, S_2, S_3) [Deduplication Enabled]
To solve this, Chuan Qin et al. et al. developed a technique called convergent dispersal in CDStore: Toward Reliable, Secure, and Cost-Efficient Cloud Storage via Convergent Dispersal. Instead of utilizing random coefficients, the dispersal algorithm derives its parameters deterministically from a cryptographic hash of the data content itself. Because the secret sharing process becomes a deterministic function of the data, identical files uploaded by different users generate identical shares across the target clouds, enabling multi-cloud systems to deduplicate data seamlessly while maintaining fault tolerance and confidentiality.
Advanced Frontiers: Rekeying and Oblivious Storage
Modern research in secure deduplication addresses operational and advanced privacy constraints, such as dynamic access control and metadata leakage.
Dynamic Rekeying
In enterprise storage, administrators frequently rotate encryption keys or revoke user access rights. In a standard encrypted deduplication system, changing a file's key requires decrypting and re-encrypting the entire payload, which alters the ciphertext and breaks all existing deduplication links. To overcome this, Chuan Qin 0009 et al. et al. designed REED, a system presented in The Design and Implementation of a Rekeying-aware Encrypted Deduplication Storage System. REED employs a deterministic All-Or-Nothing Transform (AONT). The data is processed such that the large data payload is transformed into a deduplicable format, while access control is managed via a tiny, separate file-level secret key. Administrators can rotate keys or revoke access almost instantly by updating only the small key component, preserving the deduplication status of the underlying data blocks.
Mitigating Volume and Access Pattern Leakage
Even when data content is securely encrypted, a curious cloud provider can infer sensitive information by observing access patterns or "volume leakage"—the frequency and size of duplicate data blocks.
To achieve true data blindness, Wenlong Tian et al. et al. introduced PEO-Store in PEO-Store: Practical and Economical Oblivious Store with Peer-to-Peer Delegation. By integrating non-interactive zero-knowledge proofs (NIZKPs) into a peer-to-peer delegation layer, PEO-Store allows clients to identify and deduplicate redundant chunks across different users without exposing access patterns or content to the storage provider. Similarly, in database contexts, Dongli Liu et al. et al. developed d-DSE, detailed in d-DSE: Distinct Dynamic Searchable Encryption Resisting Volume Leakage in Encrypted Databases. This framework mitigates volume leakage by isolating and retrieving only distinct, unique values during searchable encryption queries, preventing adversaries from exploiting data redundancy patterns.
Key Foundational Work
Private data deduplication protocols in cloud storage (2012) — contributed 3 concept elements to this direction.
Reconciling End-to-End Confidentiality and Data Reduction In Cloud Storage (2014) — contributed 2 concept elements to this direction.