Tapping the potential: Secure chunk-based deduplication of encrypted data for cloud backup

We, in this work, investigate the problem of designing a secure chunk-based deduplication scheme in the enterprise backup storage setting. Most of the existing works focus on realizing file-level encrypted data deduplication or key/metadata management. Little attention is drawn to the practical chunk-level deduplication system. In particular, we identify that the information contained in a small-sized chunk is more susceptible to the brute-force attack compared with file-based deduplication. We propose a randomized oblivious key generation mechanism based on the inner workings of the backup service. In contrast with the current work that compromising one client will eventually expose all the clients' storage, our scheme offers a counter-intuitive property of achieving security against multiclient compromise with minimal deduplication performance loss. In addition, we enforce a per-backup rate-limiting policy to slow down the online brute-force attack. We show that the proposed scheme is provably secure in the malicious model. We also calibrate the system design by taking into account the practical deduplication requirements to accomplish a comparable plaintext deduplication performance. Our experiment on the real-world dataset shows its efficiency, effectiveness, and practicality.