Granted Patent B2

US 9,846,615 · App. 14/556,703 · Granted Dec 19, 2017

Inventors: Douglas R. de la Torre (Kirkland, WA); David W. Young (North Bend, WA)

Assignee: INTERNATIONAL BUSINESS MACHINES CORPORATION

G06F11/1412G06F11/1076G06F11/1402G06F17/30371G06F21/602H03M7/30H03M13/29H04L9/3247G06F2201/80H04L2209/30Y10S707/99942Y10S707/99943

Abstract

Claims (108)

1. A method of deshredding data for execution by a device that includes one or more processors and one or more memory devices, the method comprises:

retrieving, from storage units, at least a decode threshold number of encoded data elements of a set of encoded data elements representing at least a first piece of data, wherein a separate piece of data was also encoded into the set of encoded data elements, the separate piece of data including one or more tags with information describing how the encoded data elements were created, the one or more tags used to indicate which of one or more functions should be performed in various stages of deshredding to reconstruct the at least first piece of data, the information including identifiers for the one or more functions performed on the data, the functions including any of: compression, encryption or signature generation and wherein the decode threshold number of encoded data elements corresponds to a minimum number of encoded data elements that are needed to recover the separate piece of data, and wherein no one storage unit of the storage units stores a sufficient number of encoded data elements to recover the separate piece of data and wherein the separate piece of data was encoded by one or more shredders and subsequently stored by the storage units;

performing a second inverse redundancy function on the at least the decode threshold number of encoded data elements to produce data elements, wherein the data elements include one or more inputs of data of a set of inputs of data and one or more first redundancy data elements;

performing a first inverse redundancy function on the data elements to recover the set of inputs of data;

combining the set of inputs of data into the separate piece of data; and

wherein the separate piece of data is used in one or more of: data decompression, data decryption or signature verification.

2. The method of claim 1 further comprises:

the first inverse redundancy function corresponding to an inverse of a first redundancy function that includes exclusively ORing at least two inputs of data of the set of inputs of data to produce a first redundancy element of the one or more first redundancy elements; and

the second inverse redundancy function corresponding to an inverse of a second redundancy function that includes exclusively ORing at least two data elements of the set of data elements to produce an encoded data element of the set of encoded data elements.

3. The method of claim 2 further comprises:

the first redundancy function including passing through an input of data of the sets of inputs of data as a second redundancy element of the one or more first redundancy elements; and

the second redundancy function including passing through a particular data element of the sets of data elements to produce a second encoded data element of the set of encoded data elements or exclusive ORing the particular data element with zero to produce the second encoded data element.

4. The method of claim 1 further comprises:

the first inverse redundancy function corresponding to an inverse of a first redundancy function;

the second inverse redundancy function corresponding to an inverse of a second redundancy function; and

a matrix model that defines coefficients for exclusive ORing operations of the first and second redundancy functions.

5. The method of claim 1 further comprises:

the first inverse redundancy function corresponding to an inverse of a first redundancy function that includes systematic encoding to produce the one or more first redundancy data elements from at least some inputs of data; and

the second inverse redundancy function corresponding to an inverse of a second redundancy function that includes non-systematic encoding to produce the set of encoded data elements from the at least some data elements.

6. The method of claim 1 , wherein the retrieving the at least the decode threshold number of encoded data elements comprises:

retrieving a first encoded data element of the at least the decode threshold number of encoded data elements from a first storage unit of the storage units;

retrieving a second encoded data element of the at least the decode threshold number of encoded data elements from a second storage unit of the storage units; and

retrieving a third encoded data element of the at least the decode threshold number of encoded data elements from a third storage unit of the storage units.

7. The method of claim 1 , wherein the retrieving the at least the decode threshold number of encoded data elements comprises:

retrieving first and second encoded data elements of the at least the decode threshold number of encoded data elements from a first storage unit of the storage units;

retrieving a third encoded data element of the at least the decode threshold number of encoded data elements from a second storage unit of the storage units; and

retrieving a fourth encoded data element of the at least the decode threshold number of encoded data elements from a third storage unit of the storage units.

8. The method of claim 1 further comprises:

retrieving, from the storage units, another at least the decode threshold number of encoded data elements of a second set of encoded data elements, wherein a second separate piece of data was encoded into the second set of encoded data elements;

performing the second inverse redundancy function on the other at least the decode threshold number of encoded data elements to produce second data elements;

performing the first inverse redundancy function on the second data elements to recover a second set of inputs of data;

combining the second set of inputs of data into the second separate piece of data; and

combining the separate piece of data and the second separate piece of data into data.

9. A device for deshredding data comprises:

a network interface;

one or more memory devices; and

one or more processors interoperably coupled to the network interface and the one or more memory devices, the one or more processors are operable to:

retrieve, from storage units via the network interface, at least a decode threshold number of encoded data elements of a set of encoded data elements representing at least a first piece of data, wherein a separate piece of data was also encoded into the set of encoded data elements, the separate piece of data including one or more tags with information describing how the encoded data elements were created, the one or more tags used to indicate which of one or a plurality of functions should be performed in various stages of deshredding to reconstruct the at least first piece of data, the information including identifiers for the one or a plurality of functions performed on the data and, for the plurality of functions, an order in which the plurality of functions were performed, the functions including any of: compression, encryption or signature verification and wherein the decode threshold number of encoded data elements corresponds to a minimum number of encoded data elements that are needed to recover the separate piece of data, and wherein no one storage unit of the storage units stores a sufficient number of encoded data elements to recover the separate piece of data and wherein the separate piece of data was encoded by one or more shredders and subsequently stored by the storage units;

perform a second inverse redundancy function on the at least the decode threshold number of encoded data elements to produce data elements, wherein the data elements include one or more inputs of data of a set of inputs of data and one or more first redundancy data elements;

perform a first inverse redundancy function on the data elements to recover the set of inputs of data;

combine the set of inputs of data into the separate piece of data; and

wherein the separate piece of data is used in one or more of: data decompression, data decryption or signature verification.

10. The device of claim 9 further comprises:

the first inverse redundancy function corresponding to an inverse of a first redundancy function that includes exclusively ORing at least two inputs of data of the set of inputs of data to produce a first redundancy element of the one or more first redundancy elements; and

the second inverse redundancy function corresponding to an inverse of a second redundancy function that includes exclusively ORing at least two data elements of the set of data elements to produce an encoded data element of the set of encoded data elements.

11. The device of claim 10 further comprises:

the first redundancy function including passing through an input of data of the sets of inputs of data as a second redundancy element of the one or more first redundancy elements; and

the second redundancy function including passing through a particular data element of the sets of data elements to produce a second encoded data element of the set of encoded data elements or exclusive ORing the particular data element with zero to produce the second encoded data element.

12. The device of claim 9 further comprises:

the first inverse redundancy function corresponding to an inverse of a first redundancy function;

the second inverse redundancy function corresponding to an inverse of a second redundancy function; and

a matrix model that defines coefficients for exclusive ORing operations of the first and second redundancy functions.

13. The device of claim 9 further comprises:

the first inverse redundancy function corresponding to an inverse of a first redundancy function that includes systematic encoding to produce the one or more first redundancy data elements from at least some inputs of data; and

the second inverse redundancy function corresponding to an inverse of a second redundancy function that includes non-systematic encoding to produce the set of encoded data elements from the at least some data elements.

14. The device of claim 9 , wherein the one or more processors is further operable to retrieve the at least the decode threshold number of encoded data elements by:

retrieving a first encoded data element of the at least the decode threshold number of encoded data elements from a first storage unit of the storage units;

retrieving a second encoded data element of the at least the decode threshold number of encoded data elements from a second storage unit of the storage units; and

retrieving a third encoded data element of the at least the decode threshold number of encoded data elements from a third storage unit of the storage units.

15. The device of claim 9 , wherein the one or more processors is further operable to retrieve the at least the decode threshold number of encoded data elements by:

retrieving first and second encoded data elements of the at least the decode threshold number of encoded data elements from a first storage unit of the storage units;

retrieving a third encoded data element of the at least the decode threshold number of encoded data elements from a second storage unit of the storage units; and

retrieving a fourth encoded data element of the at least the decode threshold number of encoded data elements from a third storage unit of the storage units.

16. The device of claim 9 , wherein the one or more processors is further operable to:

retrieve, via the network interface from the storage units, another at least the decode threshold number of encoded data elements of a second set of encoded data elements, wherein a second separate piece of data was encoded into the second set of encoded data elements;

perform the second inverse redundancy function on the other at least the decode threshold number of encoded data elements to produce second data elements;

perform the first inverse redundancy function on the second data elements to recover a second set of inputs of data;

combine the second set of inputs of data into the second separate piece of data; and

combine the separate piece of data and the second separate piece of data into data.

17. One or more memory devices comprises:

a first memory section that stores operational instructions that, when executed by a processor of a device, causes the device to:

retrieve, from storage units, at least a decode threshold number of encoded data elements of a set of encoded data elements, wherein a separate piece of data was encoded into the set of encoded data elements, the separate piece of data including one or more tags with information describing how the encoded data elements were created, the one or more tags used to indicate which of one or more functions should be performed in various stages of deshredding, the information including at least an identifier for a signature generation function performed on the data and wherein the decode threshold number of encoded data elements corresponds to a minimum number of encoded data elements that are needed to recover the separate piece of data, and wherein no one storage unit of the storage units stores a sufficient number of encoded data elements to recover the separate piece of data and wherein the separate piece of data was encoded by one or more shredders and subsequently stored by the storage units;

a second memory section that stores operational instructions that, when executed by the processor of the device, causes the device to:

perform a second inverse redundancy function on the at least the decode threshold number of encoded data elements to produce data elements, wherein the data elements include one or more inputs of data of a set of inputs of data and one or more first redundancy data elements; and

perform a first inverse redundancy function on the data elements to recover the set of inputs of data; and

a third memory section that stores operational instructions that, when executed by the processor of the device, causes the device to:

combine the set of inputs of data into the separate piece of data; and

wherein the separate piece of data is used for signature verification.

18. The one or more memory devices of claim 17 further comprises:

the first inverse redundancy function corresponding to an inverse of a first redundancy function that includes exclusively ORing at least two inputs of data of the set of inputs of data to produce a first redundancy element of the one or more first redundancy elements; and

the second inverse redundancy function corresponding to an inverse of a second redundancy function that includes exclusively ORing at least two data elements of the set of data elements to produce an encoded data element of the set of encoded data elements.

19. The one or more memory devices of claim 17 further comprises:

the first redundancy function including passing through an input of data of the sets of inputs of data as a second redundancy element of the one or more first redundancy elements; and

the second redundancy function including passing through a particular data element of the sets of data elements to produce a second encoded data element of the set of encoded data elements or exclusive ORing the particular data element with zero to produce the second encoded data element.

20. The one or more memory devices of claim 19 further comprises:

the first inverse redundancy function corresponding to an inverse of a first redundancy function;

the second inverse redundancy function corresponding to an inverse of a second redundancy function; and

a matrix model that defines coefficients for exclusive ORing operations of the first and second redundancy functions.

21. The one or more memory devices of claim 17 further comprises:

the first inverse redundancy function corresponding to an inverse of a first redundancy function that includes systematic encoding to produce the one or more first redundancy data elements from at least some inputs of data; and

the second inverse redundancy function corresponding to an inverse of a second redundancy function that includes non-systematic encoding to produce the set of encoded data elements from the at least some data elements.

22. The one or more memory devices of claim 17 , wherein the first memory section further stores operational instructions that, when executed by the processor of the device, causes the device to retrieve the at least the decode threshold number of encoded data elements by:

retrieving a first encoded data element of the at least the decode threshold number of encoded data elements from a first storage unit of the storage units;

retrieving a second encoded data element of the at least the decode threshold number of encoded data elements from a second storage unit of the storage units; and

retrieving a third encoded data element of the at least the decode threshold number of encoded data elements from a third storage unit of the storage units.

23. The one or more memory devices of claim 17 , wherein the first memory section further stores operational instructions that, when executed by the processor of the device, causes the device to retrieve the at least the decode threshold number of encoded data elements by:

retrieving first and second encoded data elements of the at least the decode threshold number of encoded data elements from a first storage unit of the storage units;

retrieving a third encoded data element of the at least the decode threshold number of encoded data elements from a second storage unit of the storage units; and

retrieving a fourth encoded data element of the at least the decode threshold number of encoded data elements from a third storage unit of the storage units.

24. The one or more memory devices of claim 17 further comprises:

the first memory section further stores operational instructions that, when executed by the processor of the device, causes the device to:

retrieve, from the storage units, another at least the decode threshold number of encoded data elements of a second set of encoded data elements, wherein a second separate piece of data was encoded into the second set of encoded data elements;

the second memory section further stores operational instructions that, when executed by the processor of the device, causes the device to:

perform the second inverse redundancy function on the other at least the decode threshold number of encoded data elements to produce second data elements; and

perform the first inverse redundancy function on the second data elements to recover a second set of inputs of data;

the third memory section further stores operational instructions that, when executed by the processor of the device, causes the device to:

combine the second set of inputs of data into the second separate piece of data; and

combine the separate piece of data and the second separate piece of data into data.

Assignments (8)

Continuity (6)