SYSTEMS AND METHODS FOR QUORUM-BASED DATA RECOVERY

• US 20150378842A1
• Filed: 04/10/2015
• Published: 12/31/2015
• Est. Priority Date: 06/27/2014
• Status: Active Grant

• Current Assignee: PQ Solutions Limited
• Original Assignee: Andersen Cheng, Cen Jung Tjhai, Martin Tomlinson
• Inventors: TOMLINSON, Martin, TJHAI, Cen Jung, CHENG, Andersen
• Granted Patent: US 10,176,056 B2
• Time in Patent Office: Days
• US Class Current: 1/1
• 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 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, each equation 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 the 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.

2. The method of claim 1, 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.

3. The method of claim 1, wherein the number of quorum portions received is greater than the predefined minimum required to reconstruct the original data, and the method further comprising:

reconstructing candidate data from each combination of the minimum number of received plurality of quorum portions, using a series of reconstruction equations each associated with a single unknown value of the candidate data;

determining at least one candidate combination of received portions that produces at least one discrepancy between a data value of the reconstructed candidate data and a corresponding expected value; and

identifying at least one received quorum portion as containing incorrect data based on the determined at least one candidate combination of received portions.

4. The method of claim 3, wherein the expected value is a repeated sequence of data values in the original data.

5. The method of claim 3, wherein each candidate data comprises data identifying reconstructed original data and reconstructed auxiliary data, and wherein the at least one discrepancy is between a data value of the reconstructed auxiliary data and a corresponding expected value.

6. The method of claim 5, wherein the at least one discrepancy is between a calculated hash or checksum of the reconstructed original data or of a corresponding quorum portion of the reconstructed auxiliary data, and the corresponding hash or checksum value in the reconstructed auxiliary data

7. The method of claim 3, wherein a received quorum portion is identified as containing incorrect data by determining the or each common received portion in a plurality of candidate combinations of received portions.

16. The method of claim 1, wherein each quorum portion includes encoded control data that can be used to be indicate that the associated quorum portion contains correct or incorrect data values.

17. The method of claim 16, wherein each quorum portion is generated from data including said control data at respective defined positions in the original data, wherein corrupted data values are identified from discrepancies with the control data in the reconstructed original data.

18. The method of claim 17, wherein the control data is generated based on a cryptographic function of the data value of the associated quorum portion, wherein corrupted data values are identified from discrepancies between the reconstructed control data and recomputed control data values based on the cryptographic function of data values from the reconstructed original data.

19. The method of claim 1, wherein the original data comprises a portion of a data file or data stream, and wherein the data recovery process is repeated for each of a plurality of portions of the data file or data stream.

20. The method of claim 1, further comprising generating said plurality of quorum portions from original data, and distributing the plurality of quorum portions between a plurality of entities.

21. The method of claim 20, wherein the entities comprise one or more of:

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

22. The method of claim 20, wherein identified discrepancies in received quorum portions are used to identify the associated entity presenting quorum portions containing corrupted or erroneous values.

23. The method of claim 20, wherein one or more of said entities receives a greater proportion of said quorum portions.

24. The method of claim 1, 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.

25. The method of claim 24, wherein the additional data is associated with a current location and/or current time and/or current date and/or identity of the computing device

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

27. The method of claim 1, wherein at least one quorum portion includes metadata associated with validity of the quorum portion.

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

receiving at least a predetermined minimum number of quorum portions generated from original data, wherein each quorum portion comprises a respective partial encryption key, and at least one ciphertext portion generated by encrypting the original data using an associated encryption key formed from a defined combination of said partial encryption keys; and

decrypting the received ciphertext portions using an associated decryption key formed from the defined combination of received partial encryption keys, to recover the original data.

9. The method of claim 8, wherein the at least one ciphertext portion is generated by encrypting data comprising the original data and a hash of each partial encryption key.

10. The method of claim 9, wherein the received ciphertext portions are decrypted to recover the original data and hash of said partial encryption keys, and at least one received quorum portion is identified as containing incorrect data based on discrepancy between the recovered hash of the respective partial encryption key and a computed hash of the received respective partial encryption key.

11. The method of claim 8, wherein a plurality of ciphertext portions are generated for each quorum portion, by encrypting data comprising the original data and a hash of each partial encryption key using an associated encryption key formed from defined combinations of partial encryption keys.

12. The method of claim 11, further comprising, for each defined combination of received partial encryption keys, identifying and decrypting associated ciphertext portions using the combination of received partial encryption keys.

13. The method of claim 12, wherein the associated ciphertext portions are identified based on stored masking data defining the combinations of received partial encryption keys.

14. The method of claim 11, further comprising calculating and storing at least one modifier value derived from said generated ciphertext portions, wherein each received quorum portion includes one of said generated ciphertext portions, and wherein the remaining ciphertext portions are reconstructed ciphertext portions using the stored at least one modifier value.

15. The method of claim 11, further comprising receiving a greater number of quorum portions than the predefined minimum required to reconstruct the original data, wherein the reconstructed original data is recovered from a combination of received quorum portions that produces no discrepancies in any of the hash values of the partial encryption keys of said combination of received quorum portions.

28. A system comprising one or more processors configured to control access to stored encrypted data using a decryption key that is reconstructed from a predetermined minimum number of quorum portions, wherein a plurality of quorum portions are generated based on the decryption key, the number of quorum portions generated based on the total number of participants and the quorum number of portions required to reconstruct the decryption key, and wherein the quorum portions are distributed to said participants in determined proportions in order to control sets of participants required to provide respective quorum portions in order to reconstruct the decryption key.