AUTHENTICATED SECRET SHARING

• US 20100217986A1
• Filed: 02/26/2009
• Published: 08/26/2010
• Est. Priority Date: 02/26/2009
• 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,713,329 B2
• Time in Patent Office: Days
• US Class Current: 713/171
• CPC Class Codes: H04L 9/085 Secret sharing or secret splitting, e.g. threshold schemes
• CPC Class Codes: H04L 9/3242 involving keyed hash functions, e.g. message authentication codes [MACs], CBC-MAC or HMAC

Abstract

A method and system distributes N shares of a secret among cooperating entities by forming a mathematical construct that has an embedded internal structure to allow authentication of a reconstructed secret. The mathematical construct can be a splitting polynomial constructed using the secret, a key and a message authentication code (MAC) as coefficients. The splitting polynomial is evaluated at N random evaluation points to obtain N result values. N shares of the secret are generated and distributed among the cooperating entities for storage. A reconstructed secret can be authenticated by computing the MAC of the reconstructed secret and verifying a relationship among the coefficients of a reconstructed splitting polynomial using the MAC. If the coefficients do not satisfy the relationship, one or more additional shares of the secret can be used to reconstruct the splitting polynomial and the secret.

Claims

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

computing, by a computing system, an authentication code of a secret using a key;

constructing, by the computing system, a mathematical construct using the authentication code, the secret, the key, and (K−

3) random values, wherein K being a threshold number of shares for reconstructing the secret; and

using, by the computing system, N instances of the mathematical construct to generate N shares of the secret for distributed storage among cooperating entities.

2. The method of claim 1 wherein the mathematical construct is a splitting polynomial, the method further comprising:

evaluating the splitting polynomial at N random evaluation points to obtain N result values; and

generating the N shares of the secret, each share including one of the N evaluation points and a corresponding result value.

3. The method of claim 1 wherein the mathematical construct is a system of N distinct linear equations over GF(q) having K unknowns, q being a power of a prime number, each equation having a solution that includes the authentication code, the secret and the key, and any set of K equations is linearly independent, the method further comprising:

generating the N shares of the secret, each share including one of the N linear equations.

4. The method of claim 1 wherein the mathematical construct is a linear equation having the authentication code, the secret and the key as coefficients.

5. The method of claim 1 wherein the mathematical construct is a set of simultaneous modular equations over a finite field, the authentication code, the secret and the key embedded in set of simultaneous modular equations.

6. The method of claim 1 wherein the mathematical construct is a set of multiplicative inverses in a ring defined by a composite of integers.

7. The method of claim 1, wherein computing an authentication code further comprises:

computing the authentication code using a random number as the key and a hash function.

8. The method of claim 1, wherein generating N shares of the secret further comprises:

distributing more than one share to each cooperating entity, with any R cooperating entities being able to reconstructing the secret and any (R−

1) cooperating entities cannot reconstruct the secret.

9. The method of claim 1, wherein generating N shares of the secret further comprises:

distributing the N shares to the cooperating entities, without informing the cooperating entities of the number of shares necessary for reconstructing the secret.

10. A system for distributing a secret comprising:

data storage to store the secret; and

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

first circuitry to generate an authentication code of the secret based on a key; and

second circuitry to construct a mathematical construct using the authentication code, the secret, the key, and (K−

3) random values, wherein K being a threshold number of shares for reconstructing the secret, and to use N instances of the mathematical construct to generate N shares of the secret for distributed storage among cooperating entities.

11. The system of claim 10, wherein the mathematical construct is a splitting polynomial that has at least the authentication code, the secret, and the key as coefficients, the second circuitry to evaluate the splitting polynomial at N random evaluation points to obtain N result values, and to generate the N shares with each share to include one of the N evaluation points and a corresponding result value.

12. The system of claim 10, wherein the first circuitry includes a hash unit to compute a hash value of the secret and the key.

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

computing an authentication code of a secret using a key;

constructing a mathematical construct using the authentication code, the secret, the key, and (K−

3) random values, wherein K being a threshold number of shares for reconstructing the secret; and

using N instances of the mathematical construct to generate N shares of the secret for distributed storage among cooperating entities.

14. The computer readable medium of claim 13, wherein the mathematical construct is a splitting polynomial and the method further comprises:

evaluating the splitting polynomial at N random evaluation points to obtain N result values; and

generating the N shares of the secret, each share including one of the N evaluation points and a corresponding result value.

15. The computer readable medium of claim 13, wherein the mathematical construct is a system of N distinct linear equations over GF(q) having K unknowns, q being a power of a prime number, each equation having a solution that includes the authentication code, the secret and the key, and any set of K equations is linearly independent, the method further comprising:

generating the N shares of the secret, each share including one of the N linear equations.

16. The computer readable medium of claim 13, wherein computing an authentication code further comprises:

computing the authentication code using a random number as the key and a hash function.

17. A computer-implemented method for reconstructing a secret, the method comprising:

collecting, by a computing system, shares of a secret from a plurality of cooperating entities, each share including an evaluation point of a splitting polynomial and a corresponding result value of the splitting polynomial;

reconstructing, by the computing system, the splitting polynomial using the shares;

extracting, by the computing system, the secret from the splitting polynomial; and

authenticating, by the computing system, the secret by computing a message authentication code (MAC) of the extracted secret and verifying a relationship among coefficients of the splitting polynomial using the MAC.

18. The method of claim 17, wherein authenticating the secret further comprises:

in response to a determination that the coefficients do not satisfy the relationship, using one or more additional shares of the secret to reconstruct the splitting polynomial.

19. The method of claim 17, wherein authenticating the secret further comprises:

in response to a determination that that the coefficients do not satisfy the relationship, determining an additional number of shares for reconstructing the splitting polynomial, wherein the additional number satisfies a condition that any R cooperating entities can reconstruct the secret and any (R−

1) cooperating entity cannot reconstruct the secret.

20. The method of claim 17, wherein reconstructing a splitting polynomial further comprises:

computing interpolating polynomials using the evaluation points; and

computing a linear combination of the interpolating polynomials using the result values.

21. A computer-implemented method for reconstructing a secret, the method comprising:

collecting shares of a secret from a plurality of cooperating entities, each share including a representation of a linear equation that has a solution including the secret, a key, and a message authentication code (MAC) of the secret;

solving the linear equations in the collected shares to obtain an extracted secret; and

authenticating the extracted secret by computing the MAC of the extracted secret.