# Coupling Secret Sharing with Decentralized Server-Aided Encryption in Encrypted Deduplication
## 3 Design
### Coding-Based Secret Sharing  
**Design idea:** Our idea is that the coding matrix of the non-systematic codes can be leveraged to encrypt the plaintext chunks, such that we can achieve both encryption and encoding in a single encoding process (see Section 2.4). We also find that the coding matrix can naturally be decomposed into multiple vectors, allowing the encryption key (in this case the key is the coding matrix) to be shared, such that the server-aided encryption can be divided into multiple small encryption tasks which can be assigned to multiple key servers for parallel computation. This ensures that each key server only accesses the part of the matrix necessary for its computation.  
Figure 1: System architecture of ECDedup.  
Sharing the coding matrix among key serversBased on the idea illustrated above, we design our coding-based secret-sharing scheme. We first decompose the coding matrix into multiple vectors and then transfer each vector to each key server, respectively. The number of vectors generated from the coding matrix is based on the number of key servers.  
To protect the coding matrix from brute-force attacks, each key server leverages server-aided encryption to encrypt the received vector. We hard-code a unique secret for each server in the same way as state-of-the-art server-aided encryption [2; 3; 4; 5]. In this way, the coding matrix can be generated from the vectors encrypted based on different secrets stored in multiple key servers. This ensures the security of the coding matrix. Note that only with the coding matrix can the client decode the coded chunks into the original data chunks (see Section 2.4). Thus, the confidentiality of the outsourced data chunks can be guaranteed. If the secrets of all key server are simultaneously compromised, the security of ECDedup reduces to that of the original MLE (the same as the state-of-the-art server-aided encryption schemes [5]).  
Now we also need to carefully design the coding matrix, such that we can generate the same coding matrix for the identical data chunk to preserve deduplication capability. Here, we predefine an original matrix for the data chunk (the original matrix can be generated in various ways, as long as it ensures the deduplication of the chunk after encoding; we introduced a method of generation in Section 3.3). In ECDedup, the original matrix is divided into \(n\) vectors (\(n\) is the number of key server involved in this encoding).  
Figure 2 shows an example of our coding-based secret-sharing scheme with the coding parameters of \((n,k)=(4,3)\), which means that the number of key servers is 4 and the data chunk is divided into 3 shares (the same as CAONT-RS; see Section 2.2). Specifically, we outline the coding matrix into four steps: (Step 1) The client first generates the original matrix based on the content of plaintext chunks. (Step 2) Then, the original matrix is divided into \(n=4\) vectors \(V_{1}\), \(V_{2}\), \(V_{3}\) and \(V_{4}\), and each vector is sent to a different key server. (Step 3) Each key server generates a new vector based on the received vector and its own secret (e.g., \(V_{1}^{{}^{\prime}}=V_{1}\bigoplus Secret\ 1\), where \(\bigoplus\) denotes the encryption operator). (Step 4) The client receives the returned vector and generates the coding matrix. The coding matrix consists of 4 new vectors (i.e., \(V_{1}^{{}^{\prime}}\), \(V_{2}^{{}^{\prime}}\), \(V_{3}^{{}^{\prime}}\) and \(V_{4}^{{}^{\prime}}\)) generated by 4 key servers individually. To maintain decent performance, vectors from different matrices are packed into a batch and then sent to the corresponding key server.