Secure generalized deduplication via multi-key revealing encryption

TY - GEN

T1 - Secure generalized deduplication via multi-key revealing encryption

AU - Lucani Rötter, Daniel Enrique

AU - Nielsen, Lars

AU - Orlandi, Claudio

AU - Pagnin, Elena

AU - Vestergaard, Rasmus

PY - 2020

Y1 - 2020

N2 - 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 1 KB file chunks and 82.2% for 8 KB 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\%$$.

AB - 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 1 KB file chunks and 82.2% for 8 KB 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\%$$.

KW - Private cloud storage

KW - Revealing encryption

KW - Secure deduplication

UR - http://www.scopus.com/inward/record.url?scp=85091163821&partnerID=8YFLogxK

U2 - 10.1007/978-3-030-57990-6_15

DO - 10.1007/978-3-030-57990-6_15

M3 - Article in proceedings

AN - SCOPUS:85091163821

SN - 9783030579890

T3 - Lecture Notes in Computer Science

SP - 298

EP - 318

BT - Security and Cryptography for Networks

A2 - Galdi, Clemente

A2 - Kolesnikov, Vladimir

PB - Springer

CY - Cham

T2 - 12th International Conference on Security and Cryptography for Networks, SCN 2020

Y2 - 14 September 2020 through 16 September 2020

ER -