Secure Erasure Codes With Partial Reconstructibility

We design p-reconstructible mu-secure [n, k] erasure coding schemes (0 <= mu < k, 1 <= p <= k - mu, p vertical bar (k - mu)), which encode k - mu information symbols into n coded symbols and moreover, satisfy the k-out-of-n property and the following two properties: (P1) strongly mu-secure - an adversary that accesses at most mu coded symbols gains no information about the information symbols; (P2) p-reconstructible - a legitimate user can reconstruct each predetermined group of p information symbols by accessing a predetermined group of mu + p coded symbols. The scheme is perfectly p-reconstructible mu-secure if apart from (P1)-(P2), it also satisfies the following additional property: (P3) weakly (mu + p - 1)-secure - an adversary that accesses at most mu+ p- 1 coded symbols cannot reconstruct any single information symbol. In contrast with most related work in the literature, our codes guarantee partial reconstructibility due to (P2): once the user accesses p more coded symbols than the threshold mu, it can reconstruct a specific group of p information symbols. We provide an explicit construction of p-reconstructible mu-secure coding schemes for all mu and p over any field of size at least n + 1. We also establish a randomized construction for perfectly p-reconstructible mu-secure coding schemes for all mu and p satisfying k >= 2(mu + p) - 1 over any field of size at least n + k + k(3)/4.