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

• US 5,991,414 A
• Filed: 09/12/1997
• Issued: 11/23/1999
• Est. Priority Date: 09/12/1997
• Status: Expired due to Fees

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Jutla, Charanjit Singh, Gennaro, Rosario, Garay, Juan Alberto, Rabin, Tal D.
• Primary Examiner(s): CANGIALOSI, SALVATORE A
• Application Number:
  US08/928,982
• Time in Patent Office: 802 Days
• Field of Search: 380/21, 380/25, 380/30, 340/825.31, 340/825.34
• 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 and retrieval with confidentiality 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 an encrypted file from the user and a file encrypting key encrypted under a public key of the user to the storage system via the gateway server;

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

receiving by the gateway server a partial signature from each of the servers in the storage system receiving the parts of the dispersed file;

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

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, the user request including an encryption under the user'"'"'s public key of a user generated random number temporarily stored by the user, the random number serving as a blinding factor;

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, computing by each server a partial decryption of their respective share of the requested file encrypting key multiplied by the encrypted blinding factor using a threshold decryption algorithm;

sending by each server in the storage system the computed partial decryption 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 encrypted file using an information dispersal algorithm;

determining by the gateway server the file-encrypting key multiplied by the blinding factor;

sending the reconstituted file and the product of the encrypting key multiplied by the blinding factor to the user;

obtaining the file-encrypting key by the user by dividing out the blinding factor;

receiving from the user an authenticated acknowledgment message;

forwarding by the gateway server an acknowledgment message to all servers in the storage system; and

echoing by the servers the acknowledgment message.

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 ##EQU10## 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 1, wherein said step of distributing is transparent to the user.

5. The computer implemented method as recited in claim 4, 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.

6. The computer implemented method as recited in claim 5, 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 file 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.

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. The computer implemented method for the secure distributed storage and retrieval of information recited in claim 1 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.

12. A secure distributed 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 depositing an encrypted file from the user and a file encrypting key encrypted under a public key of the user to the storage system via the gateway server, the gateway server distributing the file among a plurality of storage elements attached to servers within said storage system, the gateway server receiving a partial signature from each of the servers receiving parts of the distributed file, the gateway server generating an authenticated proof that the storage system received and correctly stored the file, the proof being provided even when at least one of said servers malfunctions due to a malicious fault, the gateway server responding to a user request for a previously stored file by forwarding the request to all servers in the storage system, the user request including an encryption under the user'"'"'s public key of a user generated random number temporarily stored by the user, the random number serving as a blinding factor, each server checking to determine if the user making the request has permission to access the requested file, each server computing a partial decryption of their respective share of the requested file encrypting key multiplied by the encrypted blinding factor using a threshold decryption algorithm if the user making the request has permission to access the requested file, each server sending the computed partial decryption 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 encrypted file using an information dispersal algorithm, the gateway server determining the file-encrypting key multiplied by the blinding factor, sending the reconstituted file and the product of the encrypting key multiplied by the blinding factor to said computer, obtaining the file-encrypting key by the user by dividing out the blinding factor, receiving from said computer an authenticated acknowledgment message, and forwarding an acknowledgment message to all servers in the storage system, and the servers echoing the acknowledgment message.

13. The storage and retrieval system recited in claim 12 wherein the network is the Internet.

14. The storage and retrieval system recited in claim 12 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.