ENCRYPTION KEY FRAGMENT DISTRIBUTION

• US 20120243687A1
• Filed: 03/24/2011
• Published: 09/27/2012
• Est. Priority Date: 03/24/2011
• Status: Active Grant

• Current Assignee: Hewlett Packard Enterprise Development LP (Hewlett-Packard Enterprise Company)
• Original Assignee: Hewlett-Packard Development Company, L.P. (HP Inc.)
• Inventors: Swaminathan, Ram, Stephenson, Bryan, Li, Jun, Singhai, Sharad
• Granted Patent: US 8,538,029 B2
• Time in Patent Office: Days
• US Class Current: 380/277
• CPC Class Codes: H04L 9/085 Secret sharing or secret splitting, e.g. threshold schemes

Abstract

An encryption key may be fragmented into n encryption key fragments such that k<n fragments are sufficient for reconstructing the encryption key. The encryption key fragments may be distributed across data stores located within first and second geographic regions. For example, at least k of the encryption key fragments may be distributed across data stores realized at N different availability zones within the first geographic region such that less than k of the encryption key fragments are distributed to each of the N availability zones within the first geographic region. Similarly, at least k of the encryption key fragments may be distributed across data stores realized at M different availability zones within the second geographic region such that less than k of the encryption key fragments are distributed to each of the M availability zones within the second geographic region.

Claims

1. A computer-implemented method for distributing encryption key fragments across data stores located within a first geographic region and data stores located within a second geographic region that is different than and physically separated from the first geographic region, the method comprising:

fragmenting an encryption key into a number, n, of encryption key fragments such that a number, k<

n, of the encryption key fragments is sufficient for reconstructing the encryption key;

distributing at least k of the encryption key fragments across data stores realized at N different availability zones within the first geographic region such that less than k of the encryption key fragments are distributed to each of the N availability zones within the first geographic region; and

distributing at least k of the encryption key fragments across data stores realized at M different availability zones within the second geographic region such that less than k of the encryption key fragments are distributed to each of the M availability zones within the second geographic region.

2. The method of claim 1 wherein:

distributing at least k of the encryption key fragments across the data stores realized at the N different availability zones within the first geographic region includes distributing encryption key fragments across the data stores realized at the N different availability zones such that at least k encryption key fragments collectively are distributed to the data stores realized at any combination of N-x availability zones within the first geographic region, where x is a predetermined number of availability zone failures within the first geographic region to be withstood; and

distributing at least k of the encryption key fragments across the data stores realized at the M different availability zones within the second geographic region includes distributing encryption key fragments across the data stores realized at the M different availability zones such that at least k encryption key fragments collectively are distributed to the data stores realized at any combination of M-y availability zones within the second geographic region, where y is a predetermined number of availability zone failures within the second geographic region to be withstood.

3. The method of claim 1 wherein:

fragmenting the encryption key into n encryption key fragments such that k of the encryption key fragments are sufficient for reconstructing the encryption key includes fragmenting the encryption key into n encryption key fragments such that n≧

2k;

distributing at least k of the encryption key fragments across the data stores realized at the N different availability zones within the first geographic region includes distributing a first subset of at least k of the encryption key fragments across the data stores realized at the N different availability zones within the first geographic region; and

distributing at least k of the encryption key fragments across the data stores realized at the M different availability zones within the second geographic region includes distributing a second subset of at least k of the encryption key fragments that is different and disjoint from the first subset of encryption key fragments across the data stores realized at the M different availability zones within the second geographic region.

4. The method of claim 1 wherein:

distributing at least k of the encryption key fragments across data stores realized at N different availability zones within the first geographic region includes distributing the at least k encryption key fragments across N data stores realized by N corresponding computing systems, each of the N computing systems being isolated from the other of the N computing systems; and

distributing at least k of the encryption key fragments across data stores realized at M different availability zones within the second geographic region includes distributing the at least k encryption key fragments across M data stores realized by M corresponding computing systems, each of the M computing systems being isolated from the other of the M computing systems.

5. The method of claim 1 wherein:

distributing at least k of the encryption key fragments across data stores realized at N different availability zones within the first geographic region includes balancing distribution of the at least k encryption key fragments across the data stores realized at the N different availability zones; and

distributing at least k of the encryption key fragments across data stores realized at M different availability zones within the second geographic region includes balancing distribution of the at least k encryption key fragments across the data stores realized at the M different availability zones.

6. The method of claim 1 wherein:

distributing at least k of the encryption key fragments across data stores realized at N different availability zones within the first geographic region includes, for each of multiple of the k encryption key fragments;

deterministically identifying a particular data store realized at one of the N different availability zones within the first geographic region at which to store the encryption key fragment, and

distributing the encryption key fragment to the particular data store realized at one of the N different availability zones; and

distributing at least k of the encryption key fragments across data stores realized at M different availability zones within the second geographic region includes, for each of multiple of the k encryption key fragments;

deterministically identifying a particular data store realized at one of the M different availability zones within the second geographic region at which to store the encryption key fragment, and

distributing the encryption key fragment to the particular data store realized at one of the M different availability zones.

7. The method of claim 1 further comprising:

encrypting a data object using the encryption key; and

accessing an identifier associated with the encrypted data object, wherein;

distributing at least k of the encryption key fragments across data stores realized at N different availability zones within the first geographic region includes;

accessing, for each of the data stores at the N different availability zones to which the at least k encryption key fragments are to be distributed, an identifier for the data store,

performing, for each of the data stores at the N different availability zones to which the at least k encryption key fragments are to be distributed, a hashing algorithm on a combination of the identifier associated with the encrypted data object and the identifier for the data store that yields a result, and

transmitting, to each of the data stores at the N different availability zones to which the at least k encryption key fragments are to be distributed, a request to store one or more of the k encryption key fragments as well as the result of performing the hashing algorithm for the data store; and

distributing at least k of the encryption key fragments across data stores realized at M different availability zones within the second geographic region includes;

accessing, for each of the data stores at the M different availability zones to which the at least k encryption key fragments are to be distributed, an identifier for the data store,

performing, for each of the data stores at the M different availability zones to which the at least k encryption key fragments are to be distributed, a hashing algorithm on a combination of the identifier associated with the encrypted data object and the identifier for the data store that yields a result, and

transmitting, to each of the data stores at the M different availability zones to which the at least k encryption key fragments are to be distributed, a request to store one or more of the k encryption key fragments as well as the result of performing the hashing algorithm for the data store.

8. An encryption key fragment storage system comprising:

computer hardware systems implementing N≧

2 different data stores at N corresponding different availability zones located within a first geographic region;

computer hardware systems implementing M≧

2 different data stores at M corresponding different availability zones located within a second geographic region that is different from and physically separated from the first geographic region;

an encryption key fragment distributor to;

access a number, n, of fragments of an encryption key;

where a number, k<

n, of the encryption key fragments is sufficient for reconstructing the encryption key;

distribute at least k of the encryption key fragments across the N data stores at the N availability zones within the first geographic region such that less than k of the encryption key fragments are distributed to each of the N availability zones within the first geographic region; and

distribute at least k of the encryption key fragments across the M data stores at the M availability zones within the second geographic region such that less than k of the encryption key fragments are distributed to each of the M availability zones within the second geographic region.

9. The system of claim 8 wherein:

the computer hardware systems implementing the N different data stores at the N availability zones located within the first geographic region are isolated from each other; and

the computer hardware systems implementing the M different data stores at the M availability zones located within the second geographic region are isolated from each other.

10. The system of claim 8 wherein the encryption key fragment distributor is further configured to:

balance distribution of the at least k encryption key fragments across the N data stores at the N availability zones; and

balance distribution of the at least k encryption key fragments across the M data stores at the M availability zones

11. The system of claim 8 wherein:

is the encryption key fragment distributor is configured to distribute at least k of the encryption key fragments across the N data stores at the N different availability zones within the first geographic region by, for each of multiple of the k encryption key fragments;

deterministically identifying a particular data store at one of the N availability zones within the first geographic region at which to store the encryption key fragment, and

distributing the encryption key fragment to the particular data store realized at one of the N different availability zones; and

the encryption key fragment distributor is configured to distribute at least k of the encryption key fragments across the M data stores at the M different availability zones within the second geographic region by, for each of multiple of the k encryption key fragments;

deterministically identifying a particular data store at one of the M availability zones within the second geographic region at which to store the encryption key fragment, and

distributing the encryption key fragment to the particular data store realized at one of the M different availability zones.

12. A non-transitory computer-readable storage medium storing instructions that, when executed by a computing system, cause the computing system to:

access a number, n, of fragments of an encryption key where a number, k<

n, of the encryption key fragments is sufficient for reconstructing the encryption key;

distribute a first set of at least k of the encryption key fragments across N≧

2 different data stores realized at N corresponding different availability zones within a first geographic region such that no more than k−

1 unique encryption key fragments are distributed to each of the availability zones within the first geographic region; and

is distribute a second set of at least k of the encryption key fragments across M≧

2 different data stores realized at M corresponding different availability zones within a second geographic region that is different than and physically separated from the first geographic region such that no more than k−

1 unique encryption key fragments are distributed to each of the availability zones within the second geographic region.

13. The computer readable storage medium of claim 12 wherein:

the instructions that, when executed by a computing system, cause the computing system to distribute a first set of encryption key fragments across N data stores realized at N different availability zones within the first geographic region include instructions that, when executed by a computing system, cause the computing system to distribute the first set of encryption key fragments across N data stores realized at N corresponding computing systems, each of the N computing systems being isolated from the other of the N computing systems; and

the instructions that, when executed by a computing system, cause the computing system to distribute a second set of encryption key fragments across M data stores realized at M different availability zones within the second geographic region include instructions that, when executed by a computing system, cause the computing system to distribute the second set of encryption key fragments across M data stores realized at M corresponding computing systems, each of the M computing systems being isolated from the other of the M computing systems.

14. The computer readable storage medium of claim 13 wherein:

the instructions that, when executed by a computing system, cause the computing system to distribute a first set of encryption key fragments across N data stores realized at N different availability zones within the first geographic region include instructions that, when executed by a computing system, cause the computing system to balance distribution of the first set of encryption key fragments across the N data stores realized at the N different availability zones; and

the instructions that, when executed by a computing system, cause the computing system to distribute a second set of encryption key fragments across M data stores realized at M different availability zones within the second geographic region include instructions that, when executed by a computing system, cause the computing system to balance distribution of the second set of encryption key fragments across the M data stores realized at the M different availability zones.

15. The computer readable storage medium of claim 12 wherein:

the instructions that, when executed by a computing device, cause the computing device to distribute a first set of encryption key fragments across N data stores realized at N different availability zones within the first geographic region include instructions that, when executed by a computing device, cause the computing device to, for each of multiple of the first set of encryption key fragments;

deterministically identify a particular data store realized at one of the N different availability zones within the first geographic region at which to store the encryption key fragment, and

distribute the encryption key fragment to the particular data store realized at one of the N different availability zones; and

the instructions that, when executed by a computing device, cause the computing device to distribute a second set of encryption key fragments across M data stores realized at M different availability zones within the second geographic region include instructions that, when executed by a computing device, cause the computing device to, for each of multiple of the second set of encryption key fragments;

deterministically identify a particular data store realized at one of the M different availability zones within the second geographic region at which to store the encryption key fragment, and

distribute the encryption key fragment to the particular data store realized at one of the M different availability zones.