Method and apparatus for secure data storage using distributed databases

• US 6,363,481 B1
• Filed: 08/03/1998
• Issued: 03/26/2002
• Est. Priority Date: 08/03/1998
• Status: Expired due to Term

• Current Assignee: RPX Clearinghouse LLC (RPX Corporation)
• Original Assignee: Nortel Networks Limited (Nortel Networks Corporation)
• Inventors: Hardjono, Thomas P.
• Primary Examiner(s): HAYES, GAIL O
• Assistant Examiner(s): Tucker, Chris
• Application Number:
  US09/128,350
• Time in Patent Office: 1,331 Days
• Field of Search: 713/193, 713/165, 380/277, 380/278, 380/286
• US Class Current: 713/165
• CPC Class Codes: G06F 21/6227 where protection concerns the structure of data, e.g. records, types, queries
• CPC Class Codes: H04L 9/085 Secret sharing or secret splitting, e.g. threshold schemes
• CPC Class Codes: H04L 9/0894 Escrow, recovery or storing of secret information, e.g. secret key escrow or cryptographic key storage

Abstract

A method and apparatus for secure data storage using distributed databases generates a first plurality of shares, using a first threshold scheme, based on a block of data, with at least a subset of the first plurality of shares being needed to re-create the block of data. The first plurality of shares are then distributed to a plurality of distributed databases.

Claims

1. A method comprising:

establishing a password associated with a received block of data, the password for use in later re-creation of the block of data;

encrypting, using an encryption key, the block of data;

generating, using a first threshold scheme, a first plurality of shares based on the block of data, at least a subset of the first plurality of shares is needed to re-create the block of data;

distributing the first plurality of shares to a plurality of distributed databases;

generating, using a second threshold scheme, a second plurality of shares based on the encryption key, at least a subset of the second plurality of shares is needed to re-create the encryption key; and

distributing the second plurality of shares to the plurality of distributed databases.

2. The method of claim 1, wherein the distributing comprises distributing the first plurality of shares to the plurality of databases each located in different ones of a plurality of distributed servers.

3. The method of claim 1, wherein the establishing of the password includes storing the password in an authentication database.

4. The method of claim 1, further comprising:

receiving a request to retrieve the block of data, the request including a submitted password;

comparing the submitted password to the password;

accessing at least a subset of the plurality of databases to retrieve a second plurality of shares if the submitted password matches the password; and

re-creating the block of data using the second plurality of shares.

5. The method of claim 4, wherein the number of shares in the subset is equal to the number of shares in the second plurality of shares.

6. The method of claim 1, wherein the number of shares in the subset is less than the number of shares in the first plurality of shares.

7. The method of claim 1, further comprising:

returning, to a source of the block of data, a password corresponding to the block of data.

8. An apparatus comprising:

a storage controller to encrypt, using an encryption key, the block of data prior to providing the block of data to a share generator;

a share generator coupled to the storage controller, the share generator to generate, using a first threshold scheme, a first plurality of shares based on a block of data, at least a subset of the first plurality of shares is needed to re-create the block of data, the share generator to further generate, using a second threshold scheme, a second plurality of shares based on the encryption key, at least a subset of the second plurality of shares is needed to re-create the encryption key;

a verification controller coupled to the share generator, the verification controller to establish a password to control subsequent re-creation of the block of data; and

a share distributor coupled to the share generator, the share distributor to distribute the first plurality of shares to a plurality of distributed databases and to distribute the second plurality of shares to the plurality of distributed databases.

9. The apparatus of claim 8 further comprising an authentication database coupled to the verification controller, the authentication database to store the password along with an identifier to identify the block of data corresponding to the password.

10. The apparatus of claim 9 further comprising a storage controller coupled to the verification controller and the share generator, the storage controller commmunicates with the verification controller to establish the password and to return the password to a source of the block of data.

11. The apparatus of claim 8, further comprising:

data recovery logic coupled to the share distributor and the verification controller, the data recovery logic to re-create the block of data using the second plurality of shares if the verification circuit confirms that a password submitted with a request for re-creation of the block of data matches the password; and

wherein the share distributor is to access at least a subset of the plurality of databases to retrieve a second plurality of shares.

12. The apparatus of claim 11, wherein a number of shares in the subset of the first plurality of shares is equal to a number of shares in the second plurality of shares.

13. The apparatus of claim 8, wherein a number of shares in the subset of the first plurality of shares is less than a number of shares in the first plurality of shares.

14. A machine-readable medium having stored thereon a plurality of instructions, designed to be executed by a processor, for implementing a function to (i) establish a password associated with a block of data for use in authenticating that subsequent re-creation of the block of data is proper, (ii) to encrypt, using an encryption key, the block of data prior to a first plurality of shares being generated, (iii) generate, using a first threshold scheme, a first plurality of shares based on a block of data, wherein at least a subset of the first plurality of shares is needed to re-create the block of data, (iv) to generate, using a second threshold scheme, a second plurality of shares based on the encryption key, at least a subset of the second plurality of shares is needed to re-create the encryption key, and (v) to distribute the first plurality of shares to a plurality of distributed databases and to distribute the second plurality of shares to the plurality of distributed databases.

15. The machine-readable medium of claim 14, wherein the plurality of instructions for implementing the function to distribute comprises a plurality of instructions for implementing a function to distribute the first plurality of shares to the plurality of databases each located in different ones of a plurality of distributed servers.

16. The machine-readable medium of claim 15, wherein the plurality of instructions for implementing the function to distribute comprises a plurality of instructions for implementing a function to store the password in an authentication database.

17. The machine-readable medium of claim 14, wherein the plurality of instructions are further for implementing a function (i) to receive a request to retrieve the block of data, the request including a submitted password, (ii) comparing the submitted password to the password, (iii) to access at least a subset of the plurality of databases to retrieve a second plurality of shares if the submitted password matches the password, and to re-create the block of data using the second plurality of shares.

18. The machine-readable medium of claim 17, wherein the number of shares in the subset is equal to the number of shares in the second plurality of shares.

19. The machine-readable medium of claim 14, wherein the number of shares in the subset is less than the number of shares in the first plurality of shares.

20. An apparatus comprising:

means for generating, using a first threshold scheme, a first plurality of shares based on a block of data in which at least a subset of the first plurality of shares is needed to re-create the block of data and also for generating, using a second threshold scheme, a second plurality of shares based on an encryption key, at least a subset of the second plurality of shares is needed to re-create the encryption key;

means for encrypting, using the encryption key, the block of data prior to the first plurality of shares being generated by the means for generating;

means for establishing a password to control re-creation of the block of data, the means for establishing the password being coupled to the means for generating; and

means for distributing the first plurality of shares to a plurality of distributed databases and for distributing is also for distributing the second plurality of shares to the plurality of distributed databases, the means for distributing being coupled to the means for generating.

21. The apparatus of claim 20, further comprising:

means for receiving a request to retrieve the block of data, the request including a password from a requestor, the means for receiving the request being coupled to the means for generating;

means for re-creating the block of data using the second plurality of shares; and

wherein the means for distributing is also for accessing at least a subset of the plurality of databases to retrieve the second plurality of shares.