Method and apparatus for the secure distributed storage and retrieval of information

• US 6,192,472 B1
• Filed: 06/23/1999
• Issued: 02/20/2001
• Est. Priority Date: 09/12/1997
• Status: Expired due to Fees

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Garay, Juan Alberto, Rabin, Tal D., Jutla, Charanjit Singh, Gennaro, Rosario
• Primary Examiner(s): Beausoliel, Jr., Robert W.
• Assistant Examiner(s): Elisca, Pierre Eddy
• Application Number:
  US09/338,797
• Time in Patent Office: 608 Days
• Field of Search: 713/165, 713/152, 713/168, 713/153, 713/180, 713/181, 713/193, 709/201, 380/25, 380/30, 380/282, 707/202
• US Class Current: 713/165
• CPC Class Codes: H04L 9/085 Secret sharing or secret splitting, e.g. threshold schemes
• CPC Class Codes: H04L 9/302 involving the integer factorization problem, e.g. RSA or quadratic sieve [QS] schemes
• CPC Class Codes: H04L 9/3257 using blind signatures
• CPC Class Codes: Y10S 707/99953 Recoverability

Abstract

A solution to the general problem of Secure Storage and Retrieval of Information (SSRI) guarantees that also the process of storing the information is correct even when some processors fail. A user interacts with the storage system by depositing a file and receiving a proof that the deposit was correctly executed. The user interacts with a single distinguished processor called the gateway. The mechanism enables storage in the presence of both inactive and maliciously active faults, while maintaining (asymptotical) space optimailty. This mechanism is enhanced with the added requirement of confidentiality of information; i.e., that a collusion of processors should not be able to learn anything about the information. Also, in this case space optimality is preserved.

Claims

1. A computer implemented method for the secure distributed storage of information from a user into a storage system including a plurality of servers comprising:

designating one server of said plurality of servers as a gateway server for the user;

depositing a file from said user to said storage system via the gateway server;

distributing by the gateway server said file among said plurality of servers within said storage system;

receiving by the gateway server an acknowledgment from each of the servers in the storage system receiving parts of the dispersed file; and

generating by the gateway server an authenticated proof that said storage system received and correctly stored the file, said proof being provided even when at least one of said servers malfunctions due to a failure.

2. The computer implemented method as recited in claim 1, wherein there exists a first number n of said servers, and wherein there exists a second number t of said servers that have malfunctioned, where t is less than n, and wherein each said servers receives a share of the file F, each said share having an element size of at least $\frac{}{}$

F

n-t

plus a quantity of q, in which q depends upon n and a security parameter s.

3. The computer implemented method recited in claim 2, wherein said security parameter s is equal to the logarithm base two of an acceptable probability of failure of the system.

4. The computer implemented method as recited in claim 3, wherein a proactive security protocol is implemented in which all servers may be corrupted during a lifetime of the storage system but only t servers are corrupted during any given time period.

5. The computer implemented method as recited in claim 4, wherein the proactive security protocol includes the steps of:

broadcasting by each server hashes of file shares;

taking a majority vote by each server among the received hashes of file shares to identify correct hashes;

checking by each server to determine if hashes of file shares stored by the server are correct;

if hashes of files shares stored by a server are corrupted, replacing by the server corrupted hashes with correct hashes;

then checking by each server its share of the stored file against a correct hash of the file;

if a server'"'"'s share of the stored file has been modified, broadcasting by the server a message asking other servers to reconstruct the file share; and

then taking a majority vote among received response from other servers to identify a correct file share.

6. The computer implemented method as recited in claim 1, wherein said step of distributing is transparent to the user.

7. The computer implemented method as recited in claim 1, wherein each user of the storage system may interact with a different server designated as the gateway for the user for a given transaction whereby a single gateway does not become a single point of failure for the storage system.

8. The computer implemented method as recited in claim 1, wherein said storage of information takes place in a successful manner despite the presence of at least a malfunctioning server due to a malicious fault.

9. The computer implemented method as recited in claim 1, wherein said authenticated proof is obtained by generating a receipt for a deposit of said file through an application of distributed digital signatures such that said receipt is only issued when said file has been successfully stored.

10. The computer implemented method as recited in claim 9, wherein said step of generating a receipt is performed even when one or more of the servers malfunctions due to a failure.

11. A computer implemented method for the secure distributed storage and retrieval of information of a user in a storage system including a plurality of servers comprising:

for a given transaction, designating one server of said plurality of servers as a gateway server for the user;

depositing a file from the user to the storage system via the gateway server;

distributing by the gateway server by dispersing the file among a plurality of servers within said storage system;

receiving by the gateway server an acknowledgment from each of the servers in the storage system receiving parts of the dispersed file;

generating by the gateway server an authenticated proof that said storage system received and correctly stored the file, said proof being provided even when at least one of said servers malfunctions due to a failure;

responding by the gateway server to a user request for a previously stored file by forwarding the request to all servers in the storage system;

checking by each server to determine if the user making the request has permission to access the requested file;

if the user making the request has permission to access the requested file, sending by each server in the storage system their respective shares of the stored file and hashes of all shares to the gateway server;

determining by the gateway server good shares from a majority of hashes received from other servers and reconstituting the file using an information dispersal algorithm; and

sending the reconstituted file to the user.

12. The computer implemented method as recited in claim 11, wherein there exists a first number n of said servers, and wherein there exists a second number t of said servers that may have malfunctioned, where t is less than n, and wherein each said servers receives a share of the file F, each said share having an element size of at least $\frac{}{}$

F

n-t

plus a quantity of q, in which q depends upon n and a security parameter s.

13. The computer implemented method recited in claim 12, wherein said security parameter s is equal to the logarithm base two of an acceptable probability of failure of the system.

14. The computer implemented method as recited in claim 13, wherein an proactive security protocol is implemented in which all servers may be corrupted during a lifetime of the storage system but only t servers are corrupted during any given time period.

15. The computer implemented method as recited in claim 14, wherein the proactive security protocol includes the steps of:

broadcasting by each server hashes of file shares;

taking a majority vote by each server among the receive hashes of file shares to identify correct hashes;

checking by each server to determine if hashes of file shares stored by the server are correct;

if hashes of files shares stored by a server are corrupted, replacing by the server corrupted hashes with correct hashes;

then checking by each server its share of the stored file against a correct hash of the file;

if a server'"'"'s share of the stored file has been modified, broadcasting by the server a message asking other servers to reconstruct the file share; and

then taking a majority vote among received response from other servers to identify a correct file share.

16. The computer implemented method as recited in claim 13, wherein said step of distributing is transparent to the user.

17. The computer implemented method as recited in claim 13, wherein each user of the storage system may interact with a different server designated as the gateway for the user for a given transaction whereby a single gateway does not become a single point failure for the storage system.

18. The computer implemented method as recited in claim 17, wherein said storage of information takes place in a successful manner despite the presence of a malfunctioning server due to a malicious fault.

19. The computer implemented method as recited in claim 17, wherein said authenticated proof is obtained by generating a receipt for a deposit of said file through an application of distributed digital signatures such that said receipt is only issued when said file has been successfully stored.

20. The computer implemented method as recited in claim 19, wherein said step of generating a receipt is performed even when one or more of the servers malfunctions due to a failure.

21. The computer implemented method for the secure distributed storage and retrieval of information recited in claim 13 wherein the step of designating one server of said plurality of servers as a gateway server for the user includes designating any one of said plurality of servers as the gateway for purposes of file storage and any one of said plurality of servers as the gateway for purposes of file retrieval, the designated gateway servers for file storage and retrieval not necessarily being the same server from transaction to transaction.

22. A storage system for the secure distributed storage and retrieval of information from a user comprising a plurality of servers connected in a network, one of said servers being designated as a gateway server for the user for a given transaction, the gateway server receiving a file from the user to be stored in the storage system, the gateway server distributing the file by dispersing among a plurality of servers within said storage system, the gateway server receiving an acknowledgment from each of the servers in the storage system receiving parts of the dispersed file, and the gateway server generating an authenticated proof that the storage system received and correctly stored the file, said proof being provided even when at least one of said servers malfunctions due to a failure.

23. The storage system recited in claim 22 wherein the gateway server responds to a user request for a previously stored file by forwarding the request to all servers in the storage system, each server in the storage system checking to determine if the user making the request has permission to access the requested file and if the user making the request has permission to access the requested file, each server sending their respective shares of the stored file and hashes of all shares to the gateway server, the gateway server determining good shares from a majority of hashes received from other servers and reconstituting the file using an information dispersal algorithm and sending the reconstituted file to the user.

24. The storage system recited in claim 23 wherein the network is the Internet.

25. The storage system recited in claim 23 wherein any one of said plurality of servers may be designated as the gateway for purposes of file storage and any one of said plurality of servers may be designated as the gateway for purposes of file retrieval, the designated gateway servers for file storage and retrieval not necessarily being the same server from transaction to transaction.

26. A storage system comprising:

a plurality of servers connected in a communication network having a protocol which enables information files to be stored distributively throughout the network of servers and information files to be retrieved by any single server in the network using a retrieval protocol, one of said servers being designated as a gateway server for a user of the storage system; and

a computer capable of accessing the gateway server by a communication link established with said network, said computer depositing a file from the user to said storage system via the gateway server, the gateway server distributing said file among said plurality of servers within said storage system, the gateway server receiving an acknowledgment from each of the servers in the storage system receiving parts of the dispersed file, and the gateway server generating an authenticated proof that said storage system received and correctly stored the file, said proof being provided even when at least one of said servers malfunctions due to a failure and retrieve said distributively stored information or input information to be distributively stored on said network of servers.

27. The storage system recited in claim 26 wherein the network is the Internet.

28. The storage system recited in claim 26 wherein any one of said plurality of servers may be designated as the gateway for purposes of file storage.

29. A storage and retrieval system comprising:

a plurality of servers connected in a communication network having a protocol which enables information files to be stored distributively throughout the network of servers and information files to be retrieved by any single server in the network using a retrieval protocol, one of said servers being designated as a gateway server for a user of the storage and retrieval system for a given transaction; and

a computer capable of accessing the gateway server by a communication link established with said network, said computer depositing a file from the user to the storage and retrieval system via the designated gateway server, the designated gateway server distributing the file among a plurality of servers within said storage and retrieval system, the gateway server receiving an acknowledgment from each of the servers in the storage system receiving parts of the dispersed file, the gateway server generating an authenticated proof that said storage system received and correctly stored the file, said proof being provided even when at least one of said servers malfunctions due to a failure, the gateway server responding to a user request for a previously stored file by forwarding the request to all servers in the storage system, each server checking to determine if the user making the request has permission to access the requested file, each server sending their respective shares of the stored file and hashes of all shares to the gateway server if the user making the request has permission to access the requested file, the gateway server determining good shares from a majority of hashes received from other servers and reconstituting the file using an information dispersal algorithm and sending the reconstituted file to said computer.

30. The storage and retrieval system recited in claim 29 wherein the network is the Internet.

31. The storage and retrieval system recited in claim 29 wherein any one of said plurality of servers may be designated as the gateway for purposes of file storage and any one of said plurality of servers may be designated as the gateway for purposes of file retrieval, the designated gateway servers for file storage and retrieval not necessarily being the same server from transaction to transaction.