Embedding a secret in a bit string for safeguarding the secret

• US 20090060175A1
• Filed: 08/29/2007
• Published: 03/05/2009
• Est. Priority Date: 08/29/2007
• Status: Active Grant

• Current Assignee: Red Hat, Inc. (International Business Machines Corporation)
• Original Assignee: Red Hat, Inc. (International Business Machines Corporation)
• Inventors: Schneider, James P.
• Granted Patent: US 8,068,606 B2
• Time in Patent Office: Days
• US Class Current: 380/28
• CPC Class Codes: H04L 9/085 Secret sharing or secret splitting, e.g. threshold schemes

Abstract

A method and system for embedding a secret in a bit string for safeguarding the secret. In one embodiment, the method comprises computing the length of the overall bit string as a function of q and t, where q and t are determined from the length of the secret. The method further comprises generating a plurality of information pieces based on q and t, the information pieces including a transformed secret and information for extracting the secret from the overall bit string. The method further comprises concatenating the plurality of information pieces to form the overall bit string.

Claims

1. A computer-implemented method of embedding a secret of s bits in an overall bit string for safeguarding the secret, the method comprising:

computing the length of the overall bit string as a function of q and t, q and t determined from the length of the secret;

generating a plurality of information pieces based on q and t, the information pieces including a transformed secret and information for extracting the secret from the overall bit string; and

concatenating the plurality of information pieces to form the overall bit string.

2. The method as recited in claim 1, wherein q and t are integers satisfying:

2q−

q−

1>

=s, t<

q and 2t>

=q+1.

3. The method as recited in claim 1, wherein the length of the overall bit string is at least 2(t+q+2t+2q+1) bits.

4. The method as recited in claim 1, wherein the plurality of information pieces include a leading portion and a trailing portion of the overall bit string, each of the leading portion and the trailing portion formed by a random bit string of a variable length.

5. The method as recited in claim 1, further comprising:

concatenating a first random bit string of q bits and a second random number of p bits with the secret to form an augmented secret, p being an integer value of the first random bit string; and

performing a bitwise XOR operation on the augmented secret and a third random bit string to generate a transformed secret.

6. The method as recited in claim 1, wherein generating the plurality of information pieces comprises:

generating a first random bit string of t bits in length;

interpreting the t bits as an integer w;

generating a second random bit string of w bits in length; and

concatenating the first random bit string with the second random bit string to form a leading portion of the overall bit string.

7. The method as recited in claim 1, wherein generating the plurality of information pieces further comprises:

generating a first random bit string of t bits in length;

interpreting the t bits as an integer v;

generating a second random bit string of (v+q+1) bits in length; and

concatenating the second random bit string with the first random bit string to form a trailing portion of the overall bit string.

8. The method as recited in claim 1, wherein generating the plurality of information pieces further comprises:

concatenating a first random bit string of q bits and a second random number of p bits with the secret to form an augmented secret, p being an integer value of the first random bit string;

encoding the length of the augmented secret in a third bit string of (q+1) bits; and

concatenate the third bit string with a trailing portion of the overall bit string.

9. The method as recited in claim 1, further comprising:

padding the overall bit string to a predetermined length with a random bit string.

10. A system for safeguarding a secret, the system comprising:

a bit string embedding unit to embed the secret of length s and information for extracting the secret from an overall bit string, the bit string embedding unit to concatenate a plurality of information pieces to form the overall bit string, the bit string embedding unit further comprises;

a parameter calculator to determine q and t based on the length of the secret; and

a plurality of partial bit string units, each partial bit string unit to form one of the plurality of information pieces using at least one of q or t; and

data storage coupled to the bit string embedding unit to store the secret.

11. The system as recited in claim 10, wherein q and t are integers satisfying:

2q−

q−

1>

=s, t<

q and 2t>

=q+1.

12. The system as recited in claim 10, wherein the plurality of partial bit string units comprises:

a first partial bit string unit to generate a first random bit string of t bits and a second random bit string of (v+q+1) bits, v being an integer value of the first random bit string, and to concatenate the second random bit string with the first random bit string to form a trailing portion of the overall bit string.

13. The system as recited in claim 10, wherein the plurality of partial bit string units further comprises:

a second partial bit string unit to concatenate a first random bit string of q bits and a second random number of p bits with the secret to form an augmented secret, p being an integer value of the first random bit string, and to encode the length of the augmented secret in a third bit string of (q+1) bits.

14. The system as recited in claim 13, wherein the plurality of partial bit string units further comprises:

a fourth partial bit string unit coupled to the second partial bit string unit to generate a fourth random bit string of s′

bits, s′

being the length of the augmented secret; and

a fifth partial bit string unit coupled to the second partial bit string unit and the fourth partial bit string unit to perform a bitwise XOR operation on the augmented secret and the fourth random bit string.

15. The system as recited in claim 10, wherein the plurality of partial bit string units further comprises:

a third partial bit string unit to generate a first random bit string of t bits and a second random bit string of w bits, w being an integer value of the first random bit string, and to concatenate the first random bit string with the second random bit string to form a leading portion of the overall bit string.

16. The system as recited in claim 10, wherein the plurality of partial bit string units comprises:

a sixth partial bit string unit to generate a random bit string to pad the length of the overall bit string to at least 2(t+q+2t+2q+1) bits.

17. An article of manufacture, comprising:

a machine-accessible storage medium including data that, when accessed by a machine, cause the machine to perform a method of embedding a secret of s bits in an overall bit string for safeguarding the secret, the method comprising;

computing a length of an overall bit string as a function of q and t, q and t determined from the length of the secret;

generating a plurality of information pieces based on q and t, the information pieces including a transformed secret and information for extracting the secret from the overall bit string; and

concatenating the plurality of information pieces to form the overall bit string.

18. The article of manufacture of claim 17, wherein q and t are integers satisfying:

2q−

q−

1>

=s, t<

q and 2t>

=q+1.

19. The article of manufacture of claim 17, wherein the plurality of information pieces include a leading portion and a trailing portion of the overall bit string, each of the leading portion and the trailing portion formed by a random bit string of a variable length.

20. The article of manufacture of claim 17, wherein the method further comprises:

concatenating a first random bit string of q bits and a second random number of p bits with the secret to form an augmented secret, p being an integer value of the first random bit string; and

performing a bitwise XOR operation on the augmented secret and a third random bit string to compute the transformed secret.

21. A computer-implemented method for extracting a secret from an overall bit string, the method comprising:

determining parameters q and t from the length of the overall bit string;

removing a leading portion and a trailing portion from the overall bit string, the lengths of the leading portion and the trailing portion determined from the first t bits and the last t bits of the overall bit string, respectively;

determining the length of an augmented secret from remaining bits of the overall bit string;

determining the augmented secret, based on the length of the augmented secret, from the remaining bits; and

removing redundant bits from the augmented secret to obtain the secret, the redundant bits determined from a first q bits of the augmented secret.

22. The method as recited in claim 21, wherein the length of the overall bit string is at least 2(t+q+2t+2q+1) bits, t<

q and 2t>

=q+1.

23. The method as recited in claim 21, wherein determining the length of an augmented secret comprises:

extracting last 2(q+1) bits from the remaining bits of the overall bit string;

dividing the last 2(q+1) bits into a first (q+1) bits and a second (q+1) bits; and

performing a bitwise XOR operation between the first (q+1) bits and the second (q+1) bits to compute the length of the augmented secret.

24. The method as recited in claim 21, wherein determining the augmented secret based on the length of the augmented secret comprises:

extracting first 2s′

bits of the remaining bits, s′

being the length of the augmented secret;

dividing the first 2s′

bits into a first s′

bits and a second s′

bits; and

performing a bitwise XOR operation between the first s′

bits and the second s′

bits to compute the augmented secret.

25. The method as recited in claim 21, wherein removing redundant bits from the augmented secret comprises:

extracting first q bits from the augmented secret;

interpreting the first q bits as an integer p; and

removing the first (q+p) bits from the augmented secret to obtain the secret embedded in the overall bit string.

26. An article of manufacture, comprising:

a machine-accessible storage medium including data that, when accessed by a machine, cause the machine to perform a method for extracting a secret from an overall bit string, the method comprising;

determining parameters q and t from the length of the overall bit string;

removing a leading portion and a trailing portion from the overall bit string, the lengths of the leading portion and the trailing portion determined from the first t bits and the last t bits of the overall bit string, respectively;

determining the length of an augmented secret from remaining bits of the overall bit string;

determining the augmented secret, based on the length of the augmented secret, from the remaining bits; and

removing redundant bits from the augmented secret to obtain the secret, the redundant bits determined from a first q bits of the augmented secret.

27. The article of manufacture of claim 26, wherein the length of the overall bit string is at least 2(t+q+2t+2q+1) bits, t<

q and 2t>

=q+1.

28. The article of manufacture of claim 26, wherein determining the length of an augmented secret comprises:

extracting last 2(q+1) bits from the remaining bits of the overall bit string;

dividing the last 2(q+1) bits into a first (q+1) bits and a second (q+1) bits; and

performing a bitwise XOR operation between the first (q+1) bits and the second (q+1) bits to compute the length of the augmented secret.

29. The article of manufacture of claim 26, wherein determining the augmented secret based on the length of the augmented secret comprises:

extracting first 2s′

bits of the remaining bits, s′

being the length of the augmented secret;

dividing the first 2s′

bits into a first s′

bits and a second s′

bits; and

performing a bitwise XOR operation between the first s′

bits and the second s′

bits to compute the augmented secret.