Systems and methods for distributing and securing data

• US 8,155,322 B2
• Filed: 11/07/2007
• Issued: 04/10/2012
• Est. Priority Date: 11/07/2006
• Status: Active Grant

• Current Assignee: Security First Innovations, LLC
• Original Assignee: Security First Corp
• Inventors: Bellare, Mihir, Rogaway, Phillip
• Primary Examiner(s): Barron, Jr., Gilberto
• Assistant Examiner(s): Cribbs, Malcolm
• Application Number:
  US11/983,355
• Publication Number:
  US 20080137857A1
• Time in Patent Office: 1,616 Days
• Field of Search: 380 28- 30, 380277-286, 713/171, 713175-181
• US Class Current: 380/286
• CPC Class Codes: G06F 21/64 Protecting data integrity, e.g. using checksums, certificates or signatures
• CPC Class Codes: H04L 2209/24 Key scheduling, i.e. generating round keys or sub-keys for block encryption
• CPC Class Codes: H04L 2209/56 Financial cryptography, e.g. electronic payment or e-cash
• CPC Class Codes: H04L 2209/805 Lightweight hardware, e.g. radio-frequency identification [RFID] or sensor
• CPC Class Codes: H04L 9/0816 Key establishment, i.e. cryptographic processes or cryptographic protocols whereby a shared secret becomes available to two or more parties, for subsequent use
• 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
• CPC Class Codes: H04L 9/14 using a plurality of keys or algorithms
• CPC Class Codes: H04L 9/321 involving a third party or a trusted authority
• CPC Class Codes: H04L 9/3218 using proof of knowledge, e.g. Fiat-Shamir, GQ, Schnorr, ornon-interactive zero-knowledge proofs
• CPC Class Codes: H04L 9/3231 Biological data, e.g. fingerprint, voice or retina network architectures or network communication protocols for supporting authentication of entities using biometrical features in a packet data network H04L63/0861

Abstract

A robust computational secret sharing scheme that provides for the efficient distribution and subsequent recovery of a private data is disclosed. A cryptographic key may be randomly generated and then shared using a secret sharing algorithm to generate a collection of key shares. The private data may be encrypted using the key, resulting in a ciphertext. The ciphertext may then be broken into ciphertext fragments using an Information Dispersal Algorithm. Each key share and a corresponding ciphertext fragment are provided as input to a committal method of a probabilistic commitment scheme, resulting in a committal value and a decommittal value. The share for the robust computational secret sharing scheme may be obtained by combining the key share, the ciphertext fragment, the decommittal value, and the vector of committal values.

Claims

1. A method for recovering data from a collection of purported shares comprising:

receiving a designated purported share of the collection of purported shares, wherein the designated purported share is asserted to be valid;

separating each purported share into a content portion and a vector of checksums;

using the vector of checksums associated with the designated purported share to classify each share of the collection of purported shares as an actual share or as a bogus share; and

applying a recovery algorithm of a computational secret sharing scheme to the shares classified as actual shares to recover the data.

2. The method of claim 1, wherein the actual shares are produced by:

applying a sharing mechanism of a computational secret sharing scheme to the data to produce a collection of first shares;

generating a random or pseudo-random value;

computing a set of committal values and a set of decommittal values from the random or pseudo-random value and the collection of first shares;

producing each of the actual shares by combining a first share, a decommittal value, and at least one committal value of the set of committal values.

3. The method of claim 2, wherein producing each of the actual shares comprises combining a first share, a decommittal value, and the entire set of committal values.

4. The method of claim 2, wherein computing a set of committal values and a set of decommittal values comprises employing a probabilistic commitment scheme.

5. The method of claim 1, wherein the computational secret sharing scheme is selected from the group consisting of the Shamir, Blakley, and Krawczyk secret sharing schemes.

6. The method of claim 1, further comprising:

receiving the actual shares of the collection of purported shares.

7. The method of claim 6, wherein receiving the actual shares of the collection of purported shares comprises receiving the actual shares of the collection of purported shares over a plurality of communication channels.

8. The method of claim 7, wherein receiving the actual shares of the collection of purported shares over a plurality of communication channels comprises receiving each actual share over a different communication channel.

9. The method of claim 6, wherein receiving the actual shares of the collection of purported shares comprises receiving the actual shares of the collection of purported shares from different geographic locations.

10. The method of claim 6, wherein receiving the actual shares of the collection of purported shares comprises receiving the actual shares of the collection of purported shares from different physical locations on at least one data repository.

11. The method of claim 6, wherein receiving the actual shares of the collection of purported shares comprises receiving the actual shares of the collection of purported shares from a distributed file system.

12. The method of claim 6, wherein receiving the actual shares of the collection of purported shares comprises receiving the actual shares of the collection of purported shares from a plurality of logical storage devices.

13. The method of claim 1, wherein the actual shares are produced by:

applying a sharing mechanism of a computational secret sharing scheme to the data to produce a collection of first shares;

using a probabilistic commitment scheme to compute a set of committal values and a set of decommittal values from the collection of first shares;

producing the actual shares, wherein each of the actual shares comprises a first share of the collection of first shares, a decommittal value of the set of decommittal values, and the set of committal values.

14. The method of claim 1, wherein the actual shares are produced by:

generating a cryptographic key;

encrypting the data with the cryptographic key to create a ciphertext;

producing a collection of key shares by applying the computational secret sharing scheme to the cryptographic key;

producing a collection of ciphertext chunks by applying an information dispersal algorithm to the ciphertext;

computing committal values and decommittal values by applying a probabilistic commitment scheme to each of the key shares and ciphertext chunks;

producing the actual shares, wherein each actual share is a function of a key share, a ciphertext chunk, a decommittal value, and the committal values, whereby the data is recoverable from a predefined number of the actual shares.