# Coupling Secret Sharing with Decentralized Server-Aided Encryption in Encrypted Deduplication
## 1 Introduction  
Outsourcing storage management to the cloud is common for businesses to save self-managing overheads of their massive data, and two major goals, security and storage efficiency, must be satisfied for practical outsourced storage. The outsourced data must be protected from unauthorized access via malicious clients or even the cloud providers, and the storage overhead of the outsourced data needs to be reduced to save outsourcing costs. To satisfy the above goals, encrypted deduplication that performs deduplication on encrypted data has been widely deployed in outsourced storage. Original data are often organized as chunks in deduplication and duplicate chunks are eliminated to save storagespace. For security, encrypted deduplication adds an encryption layer atop deduplication to encrypt the original plaintext chunks (from the same or different clients) into ciphertext chunks based on their content-derived keys (i.e., the cryptographic hash of their content). Thus, duplicate plaintext chunks can be encrypted using an identical key generated from their identical content, which ensures that their corresponding ciphertext chunks are also identical and thus can be deduplicated for storage efficiency. Although the content-derived key can be used to encrypt plaintext chunks to preserve deduplication capability on their ciphertext chunks, the security of the encryption remains vulnerable to offline brute-force attacks, as an adversary can enumerate all possible plaintext chunks to match the target ciphertext chunk. Existing encrypted deduplication approaches [1; 2; 3; 4; 5] often employ server-aided encryption to deploy a dedicated key server to manage key generation requests from clients. The encryption key of each chunk is derived based on both the secret key of the key server and the content-based key of the chunk itself, such that an adversary cannot feasibly derive the key without knowing the secret key. However, previous server-aided encryption schemes presume the centralized key-server-based setting, where only one single secret key (the secret key is held by a single key server [1] or shared by a group of key servers [7]) is used to managing all encryption keys, such that deduplication is only applicable over ciphertext chunks encrypted by the same secret key, and all key generation requests are centralized to the single key server (or the group of key servers). This would lead to scalability and security issues for a cloud storage service [8]. To address this issue, a new class of decentralized server-aided key management scheme is proposed to improve scalability via enabling multiple key servers with different secret keys to collectively manage encryption keys. Identical plaintext chunks are encrypted into different ciphertext chunks using distinct secret keys from multiple key servers. Then, it uses a complicated cryptographic strategy (e.g., computational Diffie-Hellman coupled with blind signature [8]) to achieve key exchange, such that these different ciphertext chunks encrypted from the identical plaintext chunks can be deduplicated in the cloud servers. However, the cryptographic strategy incurs a significant computational overhead (see Section 2.3), making it not applicable to the chunk-level deduplication, which is the current mainstream deduplication method [9]. Fortunately, we find that secret sharing, which is often used in the encrypted deduplication storage systems to share data among multiple cloud servers, can also be leveraged to share different secret keys among multiple key servers, so as to achieve efficient key management in decentralized server-aided encryption. Specifically, secret sharing first encrypts the data chunk and encodes the chunk via a specific coding matrix into multiple small-size shares (see Section 2.2), then distributes the shares to multiple cloud servers. Based on the secret sharing, we can share the chunk's encryption key to multiple key servers to collectively generate the server-aided encryption key.