SHARING A SECRET USING POLYNOMIAL DIVISION OVER GF(Q)

• US 20100046739A1
• Filed: 08/22/2008
• Published: 02/25/2010
• Est. Priority Date: 08/22/2008
• 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,345,861 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 distributing a secret are described. In one embodiment, the secret is represented by a secret polynomial of degree d over GF(q) constructed with a prime or a power of a prime. The secret polynomial is then embedded into an extension polynomial of degree m that is greater than d. The extension polynomial is divided by n coprime divisor polynomials over GF(q), using arithmetic defined for polynomials over GF(q), to generate n shares of the secret. Each share includes one of the divisor polynomials and a corresponding remainder. These n shares are distributed among a plurality of cooperating entities for secret sharing.

Claims

1. A computer-implemented method for distributing a secret, the method comprising:

representing the secret as a secret polynomial of degree d over GF(q), q being a prime or a power of a prime;

embedding the secret polynomial into an extension polynomial of degree m that is greater than d; and

dividing the extension polynomial by n coprime divisor polynomials over GF(q), using arithmetic defined for polynomials over GF(q), to generate n shares of the secret for secret sharing among a plurality of cooperating entities, each share including one of the divisor polynomials and a corresponding remainder.

2. The method of claim 1, wherein the degree m of the extension polynomial is less than a lowest-degree product of any k of the divisor polynomials and is greater than a highest-degree product of any k−

1 of the divisor polynomials, k representing a minimum number of shares from which the secret can be reconstructed.

3. The method of claim 1, further comprising:

determining the degree of the divisor polynomials in view of the size of the secret 2^s, wherein s is the length of the secret represented as a binary bit string.

4. The method of claim 1, wherein the secret is to be reconstructed with any integer number of the shares in a range from a threshold number k to n.

5. The method of claim 1, wherein representing the secret as a secret polynomial further comprises:

converting the secret into a sequence of coefficients of the secret polynomial, each coefficient being associated with one of q printable characters used in a base-q coding scheme, wherein q is a prime number or a prime power less than 94.

6. The method of claim 1, wherein representing the secret as a secret polynomial further comprises:

converting the secret into a sequence of coefficients of the secret polynomial, each coefficient being associated with a predetermined number (g) of bits used in a binary coding scheme, where q is a smallest prime number or a smallest prime power greater than 2^g.

7. The method of claim 1, wherein representing the secret as a secret polynomial further comprises:

converting the secret into a sequence of coefficients of the secret polynomial, by repeatedly dividing the secret by q or by grouping a set number of bits of the secret for conversion.

8. A system for dividing a secret into a plurality of shares, the system comprising:

data storage to store the secret; and

a computing entity coupled to the data storage, the computing entity to include;

a secret converter to represent the secret as a secret polynomial of degree d over GF(q), q being a prime or a power of a prime;

an embedding unit to embed the secret polynomial into an extension polynomial of degree m that is greater than d; and

a remainder calculator to divide the extension polynomial by n coprime divisor polynomials over GFq(q), using arithmetic defined for polynomials over GFq(q), to generate n shares of the secret for secret sharing among a plurality of cooperating entities, each share to include one of the divisor polynomials and a corresponding remainder.

9. The system of claim 8, wherein the degree m of the extension polynomial is less than a lowest-degree product of any k of the divisor polynomials and is greater than a highest-degree product of any k−

1 of the divisor polynomials, k representing a minimum number of shares from which the secret can be reconstructed.

10. The system of claim 8, further comprising:

a divisor selector to determine the degree of the divisor polynomials in view of the size of the secret 2^s, wherein s is the length of the secret represented as a binary bit string.

11. The system of claim 8, wherein the computing entity operates with an array processor or embedded hardware.

12. The system of claim 8, wherein the computing entity is to represent the secret as a sequence of coefficients of the secret polynomial, each coefficient associated with one of q printable characters used in a base-q coding scheme, wherein q is a prime number or a prime power less than 94.

13. The system of claim 8, wherein the computing entity is to represent the secret as a sequence of coefficients of the secret polynomial, each coefficient associated with a predetermined number (g) of bits used in a binary coding scheme, where q is a smallest prime number or a smallest prime power greater than 2^g.

14. A computer readable storage medium including instructions that, when executed by a processing system, cause the processing system to perform a method comprising:

representing a secret as a secret polynomial of degree d over GF(q), q being a prime or a power of a prime;

embedding the secret polynomial into an extension polynomial of degree m that is greater than d; and

dividing the extension polynomial by n coprime divisor polynomials over GFq(q), using arithmetic defined for polynomials over GFq(q), to generate n shares of the secret for secret sharing among a plurality of cooperating entities, each share including one of the divisor polynomials and a corresponding remainder.

15. The computer readable medium of claim 14, wherein the degree m of the extension polynomial is less than a lowest-degree product of any k of the divisor polynomials and is greater than a highest-degree product of any k−

1 of the divisor polynomials, k representing a minimum number of shares from which the secret can be reconstructed.

16. The computer readable medium of claim 14, wherein the method further comprises:

determining the degree of the divisor polynomials in view of the size of the secret 2 s, wherein s is the length of the secret represented as a binary bit string.

17. The computer readable medium of claim 14, wherein the secret is to be reconstructed with any integer number of the shares in a range from a threshold number k to n.

18. The computer readable medium of claim 14, wherein the method further comprises:

converting the secret into a sequence of coefficients of the secret polynomial, each coefficient being associated with one of q printable characters used in a base-q coding scheme, wherein q is a prime number or a prime power less than 94.

19. The computer readable medium of claim 14, wherein the method further comprises:

converting the secret into a sequence of coefficients of the secret polynomial, each coefficient being associated with a predetermined number (g) of bits used in a binary coding scheme, where q is a smallest prime number or a smallest prime power greater than 2^g.

20. The computer readable medium of claim 14, wherein the method further comprises:

converting the secret into a sequence of coefficients of the secret polynomial, by repeated dividing the secret by q or by grouping a set number of bits of the secret for conversion.