Systems and methods for quorum-based data recovery

• US 10,678,658 B2
• Filed: 12/06/2018
• Issued: 06/09/2020
• Est. Priority Date: 06/27/2014
• Status: Active Grant

• Current Assignee: PQ Solutions Limited
• Original Assignee: PQ Solutions Limited
• Inventors: Tomlinson, Martin, Tjhai, Cen Jung, Cheng, Andersen
• Primary Examiner(s): Gracia, Gary S
• Application Number:
  US16/211,857
• Publication Number:
  US 20190114233A1
• Time in Patent Office: 551 Days
• Field of Search: 380 28, 380227, 713168, 713170, 713171, 713185
• CPC Class Codes: G06F 11/1469 Backup restoration techniques
• CPC Class Codes: G06F 21/40 by quorum, i.e. whereby two or more security principals are required
• CPC Class Codes: G06F 2201/84 Using snapshots, i.e. a logical point-in-time copy of the data
• CPC Class Codes: H04L 2209/24 Key scheduling, i.e. generating round keys or sub-keys for block encryption
• CPC Class Codes: H04L 9/085 Secret sharing or secret splitting, e.g. threshold schemes
• CPC Class Codes: H04L 9/14 using a plurality of keys or algorithms

Abstract

The present disclosure includes systems and methods for quorum-based data recovery, in which data is recovered provided at least a minimum number of quorum data portions are presented. In exemplary embodiments, a predetermined minimum number of versions of original data is received, and the original data is reconstructed from the received versions, wherein the original data cannot be reconstructed without loss unless a predetermined minimum number of versions is received. In other embodiments, erroneous or corrupted quorum data portions are detected and associated participants presenting said erroneous or corrupted quorum data portions are identified.

Claims

1. A computer-implemented method of quorum-based data recovery, comprising:

receiving, by a plurality of computing devices associated with respective users of available participants over a data network within the secured computing environment, at least a predetermined minimum number of quorum portions generated from original data, identifying a majority symbol at each position of the received quorum data which is the symbol with the greatest number of occurrences at a particular position across all of the received quorum data, wherein each quorum portion includes a corrupted data value at a respective defined position in the original data distributed in the sequence of symbols; and

reconstructing the original data from the received quorum portions, wherein the original data is reconstructed from a majority data value at each respective defined position of the received quorum portions, wherein the original data is a secret key for encrypting or decrypting data within the secured computing environment.

2. The method of claim 1, further comprising generating a plurality of quorum portions from said original data, wherein each quorum portion includes a corrupted data value at a respective defined position in the original data, and distributing the plurality of quorum portions to a plurality of entities.

3. The method of claim 2, wherein the entities comprise one or more of:

a computing device, an authentication token and a security dongle.

4. The method of claim 2, wherein the original data is an encryption or decryption key, an authentication key or a password.

5. The method of claim 2, further comprising encrypting the generated quorum portions using a common key.

6. The method of claim 5, further comprising decrypting the reconstructed data to recover the original data.

7. The method of claim 2, further comprising encrypting the generated quorum portions using distinct keys.

8. A system comprising one or more processors processing circuits configured to perform quorum-based data recovery by:

receiving, by a plurality of computing devices associated with respective users of available participants over a data network within the secured computing environment, at least a predetermined minimum number of quorum portions generated from original data, wherein each quorum portion comprises one or more data values each identifying a solution to a respective one of a series of equations that encode dependencies between data values of the original data, wherein each equation is associated with a single unknown dependent data value; and

determining reconstructed data from the received plurality of quorum portions, using a series of reconstruction equations each associated with a single unknown value of candidate data, wherein the reconstructed data includes data values corresponding to the original data and data values corresponding to the plurality of quorum portions generated from said original data, wherein the original data is a secret key for encrypting or decrypting data within the secured computing environment.

9. The system of claim 8, further comprising:

generating a plurality of quorum portions from said original data, by;

defining a quorum code including data values associated with original data to be encoded, and a predefined number of dependent data values;

determining each said dependent data value as a solution to a respective one of said series of equations that encode dependencies between data values of the original data; and

defining each quorum portion as one or more of said dependent data values; and

distributing the plurality of quorum portions between a plurality of entities.

10. The system of claim 9, wherein the entities comprise one or more of:

a computing device, an authentication token and a security dongle.

11. The system of claim 9, wherein the original data is an encryption or decryption key, an authentication key or a password.

12. The system of claim 9, further comprising encrypting the generated quorum portions using a common key.

13. The system of claim 12, further comprising decrypting the reconstructed data to recover the original data.

14. The system of claim 9, further comprising encrypting the generated quorum portions using distinct keys.

15. The system of claim 8, further comprising computing a set of intermediate equations, wherein the series of equations are defined by pointwise products of the intermediate equations to introduce a succession of zeros in positions of corresponding unknown variables.

16. The system of claim 8, wherein each quorum portion is received from a corresponding computing device, together with additional data associated with the computing device, and wherein the defined series of reconstruction relationships encode dependencies between data values of the received versions and the additional data.

17. The system of claim 16, wherein the additional data is associated with one or more of a current location, current time, current date, and identity of the computing device.

18. The system of claim 8, wherein the defined equations are based on Galois Field elements.

19. A non-transitory storage medium comprising machine-readable instructions stored

thereon for causing a computer system to perform a method of quorum-based data recovery by:

receiving, by a plurality of computing devices in the computer system associated with respective users of available participants over a data network within the secured computing environment, at least a predetermined minimum number of quorum portions generated from

original data, identifying a majority symbol at each position of the received quorum data which is the symbol with the greatest number of occurrences at a particular position across all of the received quorum data, wherein each quorum portion includes a corrupted data value at a respective defined position in the original data distributed in the sequence of symbols; and

reconstructing the original data from the received quorum portions, wherein the original

data is reconstructed from a majority data value at each respective defined position of the

received quorum portions, wherein the original data is a secret key for encrypting or decrypting data within the secured computing environment.