Weak leakage-resilient client-side deduplication of encrypted data in cloud storage

Recently, Halevi et al. (CCS '11) proposed a cryptographic primitive called proofs of ownership (PoW) to enhance security of client-side deduplication in cloud storage. In a proof of ownership scheme, any owner of the same file F can prove to the cloud storage that he/she owns file F in a robust and efficient way, in the bounded leakage setting where a certain amount of efficiently-extractable information about file F is leaked. Following this work, we propose a secure client-side deduplication scheme, with the following advantages: our scheme protects data confidentiality (and some partial information) against both outside adversaries and honest-but-curious cloud storage server, while Halevi et al. trusts cloud storage server in data confidentiality; our scheme is proved secure w.r.t. any distribution with sufficient min-entropy, while Halevi et al. (the last and the most practical construction) is particular to a specific type of distribution (a generalization of "block-fixing" distribution) of input files. The cost of our improvements is that we adopt a weaker leakage setting: We allow a bounded amount one-time leakage of a target file before our scheme starts to execute, while Halevi et al. allows a bounded amount multi-time leakage of the target file before and after their scheme starts to execute. To the best of our knowledge, previous works on client-side deduplication prior Halevi et al. do not consider any leakage setting.