(from   : 2  reviewed in   : 1 )

Setup

• \(N = pq\) is the RSA modulus (\(p, q\) are primes)
• \(g\) is a generator of \(QR_N\) (\(QR_N\) is the set of quadratic residues modulo \(N\))
• Public key \(pk = (N, g, e)\), secret key \(sk = (d, v, x)\), \(v, x \in_R Z_N\) and \(ed = 1 \mod (p-1)(q-1)\)
• \(\pi\) is a pseudo-random permutation, \(f_x\) is a pseudo-random function keyed with the secret key \(x\), and \(H\) is a hash function
• File \(F = {b_1, b_2, \ldots , b_m}\)
• \(E_K\) is an encryption algorithm under a key \(K\)

Data Owner:

• Obtains an encrypted file \(\tilde{F}\) by encrypting the original file \(F\) using the encryption key \(K: \tilde{F} = {\tilde{b}_1, \tilde{b}_2, \ldots, \tilde{b}_m}\), where \(\tilde{b}_j = E_K(b_j)\), \(1 \leq j \leq m\).
• Uses the encrypted file \(\tilde{F}\) to create a set of tags \(\{T_j\}_{1\leq j\leq m}\) for all copies used in the verification process: \(T_j = (H(v||j) \cdot g^{\tilde{b}_j} )^d \mod N\)
• Generates \(n\) distinct replicas \(\{\hat{F}_i\}_{1\leq i\leq n}\), \(\hat{F}_i = \{\hat{b}_{i,1},\hat{b}_{i,2}, \ldots, \hat{b}_{i,m}\}\), using random masking: \(\{\) \(for (i = 1 \) to \(n)\) do \(\{\) \(for (j = 1\) to \(m)\) do \(\{\)1. Computes a random value \(r_{i,j} = f_x(i||j)\); 2. Computes the replicas block \(\hat{b}_{i,j} =\tilde{b}_j + r_{i,j}\) //(added as large integers in \(Z)\}\}\}.\);
• Data owner sends the specific replica \(\hat{F}_i\) to a specific server \(S_i, 1 \leq i \leq n\).