# Coupling Secret Sharing with Decentralized Server-Aided Encryption in Encrypted Deduplication
## 3 Design
### Content-Based Coding Matrix  
After we share the coding matrix among key servers to enable the decentralized server-aided encryption, we need to consider how to design the content-based coding matrix to generate the identical coding matrix for the identical data chunk, so as to achieve storage efficiency. Figure 2: Sharing the coding matrix among the key servers. **Insight:** We observe that the Cauchy matrix, which is used in RS codes to encode data chunks, can be generated in a customized manner. Thus, we can generate the coding matrix based on the Cauchy matrix to obtain the identical coding matrix for the identical data chunk. Equation (1) shows the definition of the Cauchy matrix. We consider a \((n,k)\) RS code, and the corresponding Cauchy matrix used for encoding in the \((n,k)\) RS code is an \(n\times k\) matrix. Let \(X=\{x_{1},x_{2},\cdots,x_{n}\}\), \(Y=\{y_{1},y_{2},\cdots,y_{k}\}\) be two disjointed sets of elements of Galois Field \(GF(2^{\text{\tiny{\tiny{\tiny{\tiny{\tiny{\tiny{\tiny{\tiny{\tiny{\tiny{\tiny{\tiny{\tiny{ \tiny{\tiny{\tiny{\tiny{\tiny{\tiny{\tiny{\tiny{\tiny{\tiny{\tiny{\tiny{  }}}}}}}}}}}}}}})}\) [20] (i.e., the size of each element is \(w\) bits, \(w=8\) or \(16\)) such that: (i) \(\forall i\in\{1,2,\cdots,n\},j\in\{1,2,\cdots,k\}\), \(x_{i}+y_{j}\
eq 0\); (ii) \(\forall i,j\in\{1,2,\cdots,n\}\), \(x_{i}\
eq x_{j}(i\
eq j)\) and (iii) \(\forall i,j\in\{1,2,\cdots,k\}\), \(y_{i}\
eq y_{j}(i\
eq j)\). Then, the Cauchy matrix \(G\) can be defined as:  
\[G= \begin{pmatrix}\frac{1}{x_{1}+y_{1}}&\frac{1}{x_{1}+y_{2}}&\cdots&\frac{1}{ x_{1}+y_{k}}\\ \frac{1}{x_{2}+y_{1}}&\frac{1}{x_{2}+y_{2}}&\cdots&\frac{1}{x_{2}+y_{k}}\\ \vdots&\vdots&\ddots&\vdots\\ \frac{1}{x_{n}+y_{1}}&\frac{1}{x_{n}+y_{1}}&\cdots&\frac{1}{x_{n}+y_{k}}\\ \end{pmatrix} . \tag{1}\]  
**Design idea:** Based on the above observation, we propose a content-based coding matrix generation scheme to generate the identical coding matrix for the identical chunk, so as to preserve deduplication capability while encoding original data chunk in ECDedup. Our idea is that the Cauchy matrix leveraged in the encoding can be deterministically generated based on the chunk's hash (which is derived based on the chunk's content). For each chunk, ECDedup first generates a hash \(h\) using an (optionally salted) hash function \(H\) (e.g., SHA-256); then, we generate the elements \(x_{i}\) and \(y_{j}\) of the Cauchy matrix based on the hash \(h\). **Fixed-size sampling:** To efficiently generate the coding matrix based on the hash value, we directly sample every \(w\) bits from the begining to the end of the hash value \(h\) to generate each element in two sets, \(X\) and \(Y\), of the Cauchy matrix. For example, for generating a \(n\times k\) coding matrix, we choose \(n+k\) elements sampled from \(h\) to generate \(\{x_{1},x_{2},\cdots,x_{n}\}\) and \(\{y_{1},y_{2},\cdots,y_{k}\}\). Figure 3 shows an example of sampling elements in Galois Field \(GF(2^{8})\) on a 256-bit hash value generated using SHA-256. Note that the elements must satisfy the definition of the Cauchy matrix above. If not, we will continue sampling elements backwards until they satisfy the definition. **Server-aided encryption:** We then share the original content-based coding matrix with the key servers via the coding-based secret-sharing scheme (see Section 3.2). For each key server, it receives a vector \(V_{i}\) from the client and calculates the corresponding vector \(V_{i}^{{}^{\prime}}\) based on its secret:  
\[V_{i}^{{}^{\prime}}=E(Hash(Secret_{i}\|V_{i}),c) \tag{2}\]  
where \(Hash\) is a cryptographic hash function (e.g., SHA-256), and \(E\) is an encryption function (e.g., AES-256) that encrypts a constant-value string \(c\) (with the same size as \(V_{l}\)) using hash as the encryption key to align the result to the size of the vector. The coding matrix is then generated based on the vectors \(V_{i}^{{}^{\prime}}\) received from all key servers (see Section 3.2).