# Coupling Secret Sharing with Decentralized Server-Aided Encryption in Encrypted Deduplication
## 3 Design
### Optimizing Matrix Generation  
While ECDedup achieves data security and storage efficiency via server-aided encryption based on the coding-based secret sharing (see Section 3.2) and the content-based coding matrix (see Section 3.3), there remain two issues that need to be optimized: (i) decentralized server-aided matrix generation may make the generated coding matrix not invertible; and (ii) poor scalability for the matrix generation. To address these issues, we design the following two methods:  
**Method 1: Element-based matrix generation:** As stated in Section 3.3, the elements \(x_{i}\) and \(y_{j}\) of the coding matrix can be generated from the content-based hash of the data chunk. However, the matrix after encryption cannot be guaranteed to be invertible, such that it requires additional calculations to ensure its invertibility (see Section 3.3). Thus, we propose an element-based matrix generation to couple the server-aided encryption and the generation of elements, and we further accelerate the matrix generation process via pipelining the generation of the elements. Specifically, the element-based matrix generation has three steps: (Step 1) The client first generates the set of elements \(\{y_{i}\}\) based on the hash value of the data chunk (see Section 3.3). (Step 2) The client then shares \(\{y_{i}\}\) among the key servers and each key servergenerates the elements \(y^{\prime}_{i}\) based on the received element and the key server's secret. (Step 3) The client receives \(y^{\prime}_{i}\) from all key servers and generates the set of elements \(\{x_{i}\}\) based on the hash value of the data chunk and \(\{y^{\prime}_{i}\}\). This makes \(\{x_{i}\}\) and \(\{y^{\prime}_{i}\}\) automatically satisfy the definition of Cauchy matrix, which ensures that the generated matrix is invertible. (Step 4) The client finally generates the coding matrix based on the elements \(\{x_{i}\}\) and \(\{y^{\prime}_{i}\}\)  
Figure 4 shows the difference between original matrix generation and element-based matrix generation. In the original matrix generation, the client first generates the set of elements \(\{x_{i}\}\) and \(\{y_{i}\}\) based on the hash value of the data chunk. Then, the client generates the original coding matrix using \(\{x_{i}\}\) and \(\{y_{i}\}\) and share the original matrix among multiple key servers to generate the encrypted coding matrix. However, in the element-based matrix generation, the client only needs to send \(\{y_{i}\}\) to the key servers, which reduces the communication overhead. Moreover, the matrix directly generated by \(\{x_{i}\}\) and \(\{y_{i}\}\) in the element-based matrix generation can benefit from the acceleration schemes that are hard-coded in the SIMD computation libraries [21] for RS codes, while the matrix handled by Algorithm 1 cannot be accelerated during encoding or decoding. We can further improve the efficiency of the matrix generation by pipelining the matrix generation of multiple data chunks. Figure 5 shows the pipeline of matrix generation and server-aided encryption, where \(C_{1},C_{2},\cdots,C_{n}\) are the data chunks to be encoded. ECDedup divides the matrix generation process into two stages: (i) generate \(\{y_{i}\}\) and (ii) generate \(\{x_{i}\}\). Since both of the above two stages and the server-aided encryption can be performed chunk-by-chunk, they can be also pipelined in a chunk-by-chunk manner. For example, we can generate the elements \(\{y_{i}\}\) of the chunk \(C_{1}\). When \(\{y_{i}\}\) of \(C_{1}\) is sent to the key servers for encryption, the client can generate \(\{y_{i}\}\) of \(C_{2}\) in parallel. **Method 2: Rolling-based matrix generation:** To support large \((n,k)\) values, which are often deployed in storage systems to save storage costs [22], we design the rolling-based matrix generation scheme. We leverage a fixed-size sliding window to generate the elements \(x_{i}\) and \(y_{i}\) based on the hash value of the data chunk. The sliding window moves \(1\) bits each time, and we record the \(w\) bits as an element (as in Section 3.3).