Paper 2020/799

Secure Generalized Deduplication via Multi-Key Revealing Encryption

Daniel E. Lucani, Lars Nielsen, Claudio Orlandi, Elena Pagnin, and Rasmus Vestergaard


Cloud Storage Providers (CSPs) offer solutions to relieve users from locally storing vast amounts of data, including personal and sensitive ones. While users may desire to retain some privacy on the data they outsource, CSPs are interested in reducing the total storage space by employing compression techniques such as deduplication. We propose a new cryptographic primitive that simultaneously realizes both requirements: Multi-Key Revealing Encryption (MKRE). The goal of MKRE is to disclose the result of a pre-defined function over multiple ciphertexts, even if the ciphertexts were generated using different keys, while revealing nothing else about the data. We present a formal model and a security definition for MKRE and provide a construction of MKRE for generalized deduplication that only uses symmetric key primitives in a black-box way. Our construction allows (a) cloud providers to reduce the storage space by using generalized deduplication to compress encrypted data across users, and (b) each user to maintain a certain privacy level for the outsourced information. Our scheme can be proven secure in the random oracle model (and we argue that this is a necessary evil). We develop a proof-of-concept implementation of our solution. For a test data set, our MKRE construction achieves secure generalized deduplication with a compression ratio of 87% for 1KB file chunks and 82.2% for 8KB chunks. Finally, our experiments show that, compared to generalized deduplication setup with un-encrypted files, adding privacy via MKRE introduces a compression overhead of less than 3% and reduces the storage throughput by at most 6.9%.

Note: Accepted for presentation at SCN 2020. This is the full version of the paper, which contains two appendices in addition to the version in the proceedings.

Available format(s)
Publication info
Published elsewhere. MAJOR revision.12th Conference on Security and Cryptography for Networks (SCN 2020)
private cloud storagesecure deduplicationrevealing encryptionsecret-key cryptography
Contact author(s)
daniel lucani @ eng au dk
lani @ eng au dk
orlandi @ cs au dk
elena pagnin @ eit lth se
rv @ eng au dk
2020-06-27: received
Short URL
Creative Commons Attribution


      author = {Daniel E.  Lucani and Lars Nielsen and Claudio Orlandi and Elena Pagnin and Rasmus Vestergaard},
      title = {Secure Generalized Deduplication via Multi-Key Revealing Encryption},
      howpublished = {Cryptology ePrint Archive, Paper 2020/799},
      year = {2020},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.