Counteracting Side Channels in Cross-user Client-side Deduplicated Cloud Storage

Client-side data deduplication enables cloud storage services to reduce storage-space and bandwidth consumption, resulting in reduced operating cost and a high level of user satisfaction. However, duplicate checks (i.e., the corresponding message exchange) generate a side channel, exposing the file existence status to attackers. In particular, the binary response from a duplicate check reveals file existence information. This can be exploited to launch further attacks, such as learning sensitive file content and establishing a covert channel. As current solutions provide only weaker privacy or rely on unreasonable assumptions, we propose RAndom REsponse (RARE) to achieve stronger privacy. The underlying principle is that the uploading user simultaneously sends a duplication request for two chunks. The cloud receiving the request returns a carefully designed randomized duplication response to preserve the deduplication gain and minimize privacy leakage. By proposing multiple chunk uploading and chunk re-arrangement strategies, we optimize the design of RARE to significantly reduce the communication burden without compromising privacy. We also study the impact of different implementations of multiple chunk uploading on the deduplication gain, further reducing communication cost. The analytical results confirm that formal privacy is ensured, whereas experiment results demonstrate that RARE preserves both privacy and the deduplication benefit.