Iterative data secret-sharing transformation

• US 9,497,175 B2
• Filed: 05/06/2015
• Issued: 11/15/2016
• Est. Priority Date: 05/14/2010
• Status: Active Grant

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Jennas, Paul A. II, Peipelman, Jason L., Rhoades, Joshua M., Ward, Matthew J.
• Primary Examiner(s): Zecher, Dede
• Assistant Examiner(s): CHIANG, JASON
• Application Number:
  US14/705,913
• Publication Number:
  US 20150237024A1
• Time in Patent Office: 559 Days
• US Class Current: 1/1
• CPC Class Codes: H04L 2209/34 Encoding or coding, e.g. Huffman coding or error correction
• CPC Class Codes: H04L 63/0485 Networking architectures for enhanced packet encryption processing, e.g. offloading of IPsec packet processing or efficient security association look-up
• CPC Class Codes: H04L 9/065 Encryption by serially and continuously modifying data stream elements, e.g. stream cipher systems, RC4, SEAL or A5/3
• CPC Class Codes: H04L 9/0827 involving distinctive intermediate devices or communication paths network architectures or network communication protocols using different networks H04L63/18
• CPC Class Codes: H04L 9/085 Secret sharing or secret splitting, e.g. threshold schemes

Abstract

Provided are a method, system, and article of manufacture for iterative data secret-sharing transformation and reconversion. In one aspect, data secret-sharing transformation and reconversion is provided in which each bit of an input stream of bits of data is split, on a bit by bit basis, into a pair of secret-sharing bits, and the secret-sharing bits of each pair of secret-sharing bits are separated into separate streams of secret-sharing bits. In this manner, one secret-sharing bit of each pair of secret-sharing bits may be placed in one stream of secret-sharing bits and the other secret-sharing bit of each pair may be placed in another stream of secret-sharing bits different from the one stream of secret-sharing bits. Confidentiality of the original input stream may be protected in the event one but not both streams of secret-sharing bits is obtained by unauthorized personnel. In another aspect, for an input stream of N bits, each received bit of the N bits of the input stream of data, may be interatively split, on a bit by bit basis, into a pair of secret-sharing bits, to generate as few as N+1 secret-sharing bits from the input stream of bits N bits. Other features and aspects may be realized, depending upon the particular application.

Claims

1. A method, comprising:

receiving an input stream of bits of data;

secret-sharing transforming the received bits of the input stream of data, said secret-sharing transforming including splitting each received bit of the bits of the input stream of data, on a bit by bit basis, into a pair of secret-sharing bits; and

separating the secret-sharing bits of each pair of secret-sharing bits into separate streams of secret-sharing bits so that one secret-sharing bit of each pair of secret-sharing bits is in one stream of secret-sharing bits and the other secret-sharing bit of each pair is in another stream of secret-sharing bits different from the one stream of secret-sharing bits and wherein a secret sharing bit is shared by adjacent pairs of secret sharing bits;

wherein the splitting is a function of the exclusive-OR function such that a first received bit of the input stream of bits is equal to the exclusive-OR function of a first associated pair of secret-sharing bits, one secret-sharing bit being in the one stream of secret-sharing bits, and the other secret-sharing bit of the first associated pair being in the other stream of secret-sharing bits, and a second received bit of the input stream of bits is equal to the exclusive-OR function of a second associated pair of secret-sharing bits, one secret-sharing bit of the second associated pair being in the one stream of secret-sharing bits of data, and the other secret-sharing bit of the second associated pair being in the other stream of secret-sharing bits, and wherein one bit is shared between the first associated pair of secret-sharing bits and the second associated pair of secret-sharing bits so that the total number of secret-sharing bits of the first and second associated pairs of secret-sharing bits is three secret-sharing bits and wherein the separating of the three secret-sharing bits of the first and second associated pairs of secret-sharing bits, includes placing the shared secret-sharing bit in one stream of secret-sharing bits, and placing the other two secret-sharing bits of the three secret-sharing bits in one or more streams of secret-sharing bits different from the one stream of the shared secret-sharing bit; and

wherein the input stream of bits has N bits, and wherein the splitting of each received bit of the N bits of the input stream of data, on a bit by bit basis, into a pair of secret-sharing bits, is performed iteratively, to generate a total of N+1 secret-sharing bits from the input stream of bits N bits.

2. The method of claim 1, wherein the separating the streams of secret-sharing bits includes:

storing the plurality of streams of secret-sharing bits of data on separate storage media at separate locations so that the secret sharing bits of each of said pairs of secret sharing bits are stored on different storage media at different locations.

3. The method of claim 1, wherein the separating the streams of secret-sharing bits includes:

transmitting the plurality of streams of secret-sharing bits of data in separate communication channels so that the secret sharing bits of each of said pairs of secret sharing bits are transmitted in different transmission channels.

4. The method of claim 1 wherein each received bit of the input stream of bits of data is equal to the exclusive-OR function of the associated pair of secret-sharing bits.

5. The method of claim 1 further comprising:

receiving the streams of secret-sharing bits; and

reconverting the received streams of secret-sharing bits as a first restored stream of bits of data, said reconverting including recombining the one stream of secret-sharing bits and the other stream of secret-sharing bits of data, on a bit by bit basis, wherein each recombined bit of the restored stream of bits of data is equal to the exclusive-OR function of an associated pair of secret-sharing bits, one secret-sharing bit from the one stream of secret-sharing bits, and the other secret-sharing bit from the other stream of secret-sharing bits.

6. The method of claim 4 wherein a first received bit of the input stream of bits of data has a value of 0 and wherein said splitting includes assigning either the values 0, 0 to the associated pair of secret-sharing bits of the one and the other streams of secret-sharing bits, respectively, or the values 1, 1 to the associated pair of secret-sharing bits of the one and the other streams of secret-sharing bits, respectively, as a function of a randomization function.

7. The method of claim 4 wherein a first received bit of the input stream of bits of data has a value of 1 and wherein said splitting includes assigning either the values 0, 1 to the associated pair of secret-sharing bits of the one and the other streams of secret-sharing bits, respectively, or the values 1, 0 to the associated pair of secret-sharing bits of the one and the other streams of secret-sharing bits, respectively, as a function of a randomization function.

8. A computer program product comprising a non-transitory computer readable storage medium storing computer readable program code that, when executed on a processor of a computer, causes the computer to perform operations, comprising:

receiving an input stream of bits of data;

secret-sharing transforming the received bits of the input stream of data, said secret-sharing transforming including splitting each received bit of the bits of the input stream of data, on a bit by bit basis, into a pair of secret-sharing bits; and

separating the secret-sharing bits of each pair of secret-sharing bits into a plurality of separate streams of secret-sharing bits so that one secret-sharing bit of each pair of secret-sharing bits is in one stream of secret-sharing bits and the other secret-sharing bit of each pair is in another stream of secret-sharing bits different from the one stream of secret-sharing bits and wherein a secret sharing bit is shared by adjacent pairs of secret sharing bits;

wherein the splitting is a function of the exclusive-OR function such that a first received bit of the input stream of bits is equal to the exclusive-OR function of a first associated pair of secret-sharing bits, one secret-sharing bit being in the one stream of secret-sharing bits, and the other secret-sharing bit of the first associated pair being in the other stream of secret-sharing bits, and a second received bit of the input stream of bits is equal to the exclusive-OR function of a second associated pair of secret-sharing bits, one secret-sharing bit of the second associated pair being in the one stream of secret-sharing bits of data, and the other secret-sharing bit of the second associated pair being in the other stream of secret-sharing bits, and wherein one bit is shared between the first associated pair of secret-sharing bits and the second associated pair of secret-sharing bits so that the total number of secret-sharing bits of the first and second associated pairs of secret-sharing bits is three secret-sharing bits and wherein the separating of the three secret-sharing bits of the first and second associated pairs of secret-sharing bits, includes placing the shared secret-sharing bit in one stream of secret-sharing bits, and placing the other two secret-sharing bits of the three secret-sharing bits in one or more streams of secret-sharing bits different from the one stream of the shared secret-sharing bit; and

wherein the input stream of bits has N bits, and wherein the splitting of each received bit of the N bits of the input stream of data, on a bit by bit basis, into a pair of secret-sharing bits, is performed iteratively, to generate a total of N+1 secret-sharing bits from the input stream of N bits.

9. The computer program product of claim 8, wherein the separating the streams of secret-sharing bits includes:

storing the plurality of streams of secret-sharing bits of data on separate storage media at separate locations so that the secret sharing bits of each of said pairs of secret sharing bits are stored on different storage media at different locations.

10. The computer program product of claim 8, wherein the separating the streams of secret-sharing bits includes:

transmitting the plurality of streams of secret-sharing bits of data in separate communication channels so that the secret sharing bits of each of said pairs of secret sharing bits are transmitted in different transmission channels.

11. The computer program product of claim 8 wherein each received bit of the input stream of bits of data is equal to the exclusive-OR function of the associated pair of secret-sharing bits.

12. The computer program product of claim 8 further comprising:

receiving the streams of secret-sharing bits; and

reconverting the received streams of secret-sharing bits as a first restored stream of bits of data, said reconverting including recombining the one stream of secret-sharing bits and the other stream of secret-sharing bits of data, on a bit by bit basis, wherein each recombined bit of the restored stream of bits of data is equal to the exclusive-OR function of an associated pair of secret-sharing bits, one secret-sharing bit from the one stream of secret-sharing bits, and the other secret-sharing bit from the other stream of secret-sharing bits.

13. The computer program product of claim 11 wherein a first received bit of the input stream of bits of data has a value of 0 and wherein said splitting includes assigning either the values 0, 0 to the associated pair of secret-sharing bits of the one and the other streams of secret-sharing bits, respectively, or the values 1, 1 to the associated pair of secret-sharing bits of the one and the other streams of secret-sharing bits, respectively, as a function of a randomization function.

14. The computer program product of claim 11 wherein a first received bit of the input stream of bits of data has a value of 1 and wherein said splitting includes assigning either the values 0, 1 to the associated pair of secret-sharing bits of the one and the other streams of secret-sharing bits, respectively, or the values 1, 0 to the associated pair of secret-sharing bits of the one and the other streams of secret-sharing bits, respectively, as a function of a randomization function.

15. A system, comprising:

a processing unit having a data input configured to receive an input stream of bits of data, and adapted to transform for secret-sharing the received bits of the input stream of data, said processing unit including a data splitter adapted to split each received bit of the bits of the input stream of data, on a bit by bit basis, into a pair of secret-sharing bits, and a data separator adapted to separate the secret-sharing bits of each pair of secret-sharing bits into separate streams of secret-sharing bits so that one secret-sharing bit of each pair of secret-sharing bits is in one stream of secret-sharing bits and the other secret-sharing bit of each pair is in another stream of secret-sharing bits different from the one stream of secret-sharing bits and wherein a secret sharing bit is shared by adjacent pairs of secret sharing bits;

wherein the processing unit is adapted to perform an exclusive-OR function and wherein the splitting is a function of the exclusive-OR function such that a first received bit of the input stream of bits is equal to the exclusive-OR function of a first associated pair of secret-sharing bits, one secret-sharing bit being in the one stream of secret-sharing bits, and the other secret-sharing bit of the first associated pair being in the other stream of secret-sharing bits, and a second received bit of the input stream of bits is equal to the exclusive-OR function of a second associated pair of secret-sharing bits, one secret-sharing bit of the second associated pair being in the one stream of secret-sharing bits of data, and the other secret-sharing bit of the second associated pair being in the other stream of secret-sharing bits, and wherein one bit is shared between the first associated pair of secret-sharing bits and the second associated pair of secret-sharing bits so that the total number of secret-sharing bits of the first and second associated pairs of secret-sharing bits is three secret-sharing bits and wherein the separating of the three secret-sharing bits of the first and second associated pairs of secret-sharing bits, includes placing the shared secret-sharing bit in one stream of secret-sharing bits, and placing the other two secret-sharing bits of the three secret-sharing bits in one or more streams of secret-sharing bits different from the one stream of the shared secret-sharing bit; and

wherein the input stream of bits has N bits, and wherein the splitting of each received bit of the N bits of the input stream of data, on a bit by bit basis, into a pair of secret-sharing bits, is performed iteratively, to generate a total of N+1 secret-sharing bits from the input stream of N bits.

16. The system of claim 15, further comprising:

a plurality of separate storage media at separate locations, wherein the processing unit separator is adapted to store the plurality of streams of secret-sharing bits of data on said separate storage media at separate locations so that the secret sharing bits of each of said pairs of secret sharing bits are stored on different storage media at different locations.

17. The system of claim 15 for use with a plurality of separate communication channels, the system further comprising a data transmission unit having said data input and said processing unit, wherein said processing unit separator is adapted to:

transmit the plurality of streams of secret-sharing bits of data in said separate communication channels so that the secret sharing bits of each of said pairs of secret sharing bits are transmitted in different transmission channels.

18. The system of claim 15 wherein the processing unit has a data input configured to receive the streams of secret-sharing bits, and is adapted to reconvert the received streams of secret-sharing bits as a first restored stream of bits of data, said processing unit include a data recombinor adapted to recombine the one stream of secret-sharing bits and the other stream of secret-sharing bits of data, on a bit by bit basis, wherein each recombined bit of the restored stream of bits of data is equal to the exclusive-OR function of an associated pair of secret-sharing bits, one secret-sharing bit from the one stream of secret-sharing bits, and the other secret-sharing bit from the other stream of secret-sharing bits.