Paper 1998/025

Secure Distributed Storage and Retrieval

Juan A. Garay, Rosario Gennaro, Charanjit Jutla, and Tal Rabin


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 recovery of the information is possible in the presence of up to t inactive servers. An enhanced mechanism to enable construction in the presence of malicious faults, which can intentionally modify their pieces of the information, was later presented by Krawczyk. Yet, these methods assume that the malicious faults occur only at reconstruction time. <P> In this paper we address the more general problem of secure storage and retrieval of information (SSRI), and guarantee that also the process of storing the information is correct even when some of the servers fail. Our protocols achieve this while maintaining the (asymptotical) space optimality of the above methods. <P> We also consider SSRI with the added requirement of confidentiality, by which no party except for the rightful owner of the information is able to learn anything about it. This is achieved through novel applications of cryptographic techniques, such as the distributed generation of receipts, distributed key management via threshold cryptography, and ``blinding.'' <P> An interesting byproduct of our scheme is the construction of a secret sharing scheme with shorter shares size in the amortized sense. An immediate practical application of our work is a system for the secure deposit of sensitive 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.

Available format(s)
Publication info
Published elsewhere. Appeared in the THEORY OF CRYPTOGRAPHY LIBRARY and has been included in the ePrint Archive.
Information securityinformation dispersaldistributed storagethreshold cryptography.
Contact author(s)
garay @ research bell-labs com
1998-12-10: received
Short URL
Creative Commons Attribution


      author = {Juan A.  Garay and Rosario Gennaro and Charanjit Jutla and Tal Rabin},
      title = {Secure Distributed Storage and Retrieval},
      howpublished = {Cryptology ePrint Archive, Paper 1998/025},
      year = {1998},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.