Secure distributed storage and retrieval

In his well-known Information Dispersal Algorithm paper, Rabin showed a way to distribute information in n pieces among n servers in such a way that r ecovery of the information is possible in the presence of up to t inactive servers. An enhanced mechanism to enable construction in the presence of ma licious faults, which can intentionally modify their pieces of the informat ion, was later presented by Krawczyk. Yet, these methods assume that the ma licious faults occur only at reconstruction time. In this paper we address the more general problem of secure storage and ret rieval of information (SSRI), and guarantee that also the process of storin g the information is correct even when some of the servers fail. Our protoc ols achieve this while maintaining the (asymptotical) space optimality of t he above methods. We also consider SSRI with the added requirement of confidentiality, by whi ch no party except for the rightful owner of the information is able to lea rn anything about it. This is achieved through novel applications of crypto graphic techniques, such as the distributed generation of receipts, distrib uted key management via threshold cryptography, and "blinding". An interesting byproduct of our scheme is the construction of a secret shar ing scheme with shorter shares size in the amortized sense. An immediate pr actical application of our work is a system for the secure deposit of sensi tive data. We also extend SSRI to a "proactive" setting, where an adversary may corrupt all the servers during the lifetime of the system, but only a fraction during any given time interval. (C) 2000 Elsevier Science B.V. All rights reserved.