# Coupling Secret Sharing with Decentralized Server-Aided Encryption in Encrypted Deduplication
## 3 Design
### Discussion on Security  
Unlike the state-of-the-art decentralized server-aided encryption schemes, ECDedup does not change the underline encryption logic of the centralized server-aided encryption schemes. We only deploy a coding-based secret-sharing scheme atop the original encryption logic to share the coding matrix among multiple key servers to enable decentralized server-aided encryption, while the coding matrix is generated based on the content-based hash of the data chunk and the secrets within the key servers (same as the state-of-the-art centralized server-aided encryption schemes [2; 3; 4; 5]). Thus, the security of ECDedup is comparable with previous methods.  
Specifically, we analyze the security of our ECDedup in comparison with that of the state-of-the-art encrypted deduplication schemes from the following two aspects:  
**Security of encryption key:** Similar to the centralized encrypted deduplication schemes, ECDedup calculates the cryptographic hash of the chunk's content and sends it to the key server to derive the encryption key. With the help of the key server, ECDedup can defend against offline brute-force attacks. The difference between ECDedup and the centralized schemes lies on the client side, where ECDedup generates the corresponding coding matrix based on the cryptographic hash and shares the coding matrix among multiple key servers. In this way, only part of the coding information (i.e., vectors or elements) of the coding matrix is sent to each key server, such that a single key server cannot infer the complete encryption key. Meanwhile, the information sent to each key server is actually the short hash, which is more likely to incur many hash collision (i.e., multiple chunks are mapped to the same short hashes). Thus, the key server cannot readily guess a chunk from the short hashes [1; 4].  
In the centralized encrypted deduplication schemes, the security will be reduced to that of the original MLE when the centralized key server is compromised. Thus, compared with the centralized schemes, our ECDedup can provide a stronger security guarantee, since the compromise of a single or several key servers will not reduce the the security as analyzed above.  
**Data confidentiality:** [PERSON] [23] presented the confidentiality of the erasure-coded-based (e.g., RS codes) secret-sharing algorithm, which meets the following condition: if any sub-square matrix of the coding matrix is nonsingular, then it has confidentiality. For example, if a \((n,k)\) erasure-coded-based secret-sharing algorithm satisfies the condition, the adversary cannot reconstruct any part of the plaintext data (which is divided into \(k\) chunks) with less than \(k\) ciphertext chunks.  
ECDedup adopts the Cauchy matrix as the coding matrix, while any sub-square matrix of the Cauchy matrix remains a Cauchy matrix [24; 25] (i.e., nonsingular). According to the confidentiality guarantee provided by [PERSON] [23], an adversary cannot reconstruct any part of the original data without having \(k\) ciphertext chunks. Moreover, the coding matrix of ECDedup is generated via multiple key servers using an additional secret-sharing scheme. Taking the \((n,k)=(12,8)\) Cauchy matrix as an example (in Galois Field \(GF(2^{16})\)), the smallest sub-square matrix space can be up to \(S=2^{2\times k\times w}=2^{256}\), which is at the same  
Figure 6: Sliding-window-based matrix generation.  
level as that of the state-of-the-art encrypted deduplication storage systems [5, 14]. Note that for the compromised key server, the adversary only obtains part of coding information of the coding matrix, such that the adversary also needs to obtain the coding information of other key servers to infer the original data of the target ciphertext chunk.