SHARING A SECRET VIA LINEAR INTERPOLATION

• US 20100054458A1
• Filed: 08/29/2008
• Published: 03/04/2010
• Est. Priority Date: 08/29/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,675,877 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
• CPC Class Codes: H04L 9/0894 Escrow, recovery or storing of secret information, e.g. secret key escrow or cryptographic key storage
• CPC Class Codes: H04L 9/14 using a plurality of keys or algorithms

Abstract

A method and system distributes shares of a secret among cooperating entities using linear interpolation. In one embodiment, a linear equation is formed using the secret and random elements. The linear equation represents a K-dimensional secret hyperplane, where K is the number of shares to reconstruct the secret. Shares of the secrets are created, with each share containing a point on the secret hyperplane. The shares are then distributed to cooperating entities for secret sharing.

Claims

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

forming a linear equation using the secret and random elements, the linear equation representing a K-dimensional secret hyperplane, wherein K is the number of shares to reconstruct the secret;

forming the shares of the secret, with each share containing a point on the secret hyperplane; and

distributing the shares to a plurality of cooperating entities for secret sharing.

2. The method of claim 1, wherein forming a linear equation further comprises:

using the secret, or a sum of the secret and coefficients of the linear equation, as a constant term of the linear equation.

3. The method of claim 1, wherein forming a linear equation further comprises:

extending the length of the secret with random information to obtain an extended secret; and

grouping elements of the extended secret into a plurality of groups and using each group as a coefficient of the linear equation.

4. The method of claim 1, wherein forming a linear equation further comprises:

using a known value for a coefficient of the linear equation; and

generating (K−

1) random values as other coefficients of the linear equation.

5. The method of claim 1, wherein forming the shares of the secret further comprises:

generating (K−

1) random values for (K−

1) variables in the linear equation;

computing a value of a remaining variable; and

forming a K-element share by including the (K−

1) random values and the value of the remaining variable.

6. 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 to generate the shares of the secret for distribution among cooperating entities, the computing entity comprising;

a random value generator to generate random values; and

a share generator to use the secret and the random values to form a linear equation that represents a K-dimensional secret hyperplane, and to create the shares of the secret with each share containing a point on the secret hyperplane, wherein K is the number of the shares to reconstruct the secret.

7. The system of claim 6, wherein the secret is used as a constant term of the linear equation.

8. The system of claim 6, wherein a sum of the secret and coefficients of the linear equation is used as a constant term of the linear equation.

9. The system of claim 6, wherein one coefficient of the linear equation is set to a known value and other (K−

1) coefficients set to random values.

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

forming a linear equation using the secret and random elements, the linear equation representing a K-dimensional secret hyperplane, wherein K is the number of shares to reconstruct the secret;

forming the shares of the secret, with each share containing a point on the secret hyperplane; and

distributing the shares to a plurality of cooperating entities for secret sharing.

11. The computer readable medium of claim 10, wherein forming a linear equation further comprises:

using the secret, or a sum of the secret and coefficients of the linear equation, as a constant term of the linear equation component.

12. The computer readable medium of claim 10, wherein forming a linear equation further comprises:

extending the length of the secret with random information to obtain an extended secret; and

grouping elements of the extended secret into a plurality of groups and using each group as a coefficient of the linear equation.

13. The computer readable medium of claim 10, wherein forming the shares of the secret further comprises:

using a known value for a coefficient of the linear equation; and

generating (K−

1) random values as other coefficients of the linear equation

14. The computer readable medium of claim 10, wherein forming the shares of the secret further comprises:

generating (K−

1) random values for (K−

1) variables in the linear equation;

computing a value of a remaining variable; and

forming a K-element share by including the (K−

1) random values and the value of the remaining variable.

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

collecting K shares of the secret from cooperating entities, wherein K is the number of shares to reconstruct the secret;

constructing K linear equations with K unknowns using the K shares, the linear equations defining a K-dimensional secret hyperplane on which the secret is embedded;

reconstructing the secret hyperplane by solving for the K unknowns; and

extracting the secret from the secret hyperplane.

16. The method of claim 15, wherein reconstructing the secret hyperplane further comprises:

extracting the secret from a constant term of the linear equation, or a linear combination of coefficients and the constant term of the linear equation.

17. The method of claim 15, wherein each of the K shares contains K elements that represent a point on the secret hyperplane.

18. A system for reconstructing a secret, the system comprising:

a receiving interface to collect K shares of the secret from cooperating entities, wherein K is the number of shares to reconstruct the secret; and

a linear operator coupled to the receiving interface to use the K shares to construct K linear equations with K unknowns, the linear equations to define a K-dimensional secret hyperplane on which the secret is embedded, the linear operator to reconstruct the secret hyperplane with solved K unknowns and to extract the secret from the secret hyperplane.

19. The system of claim 18, wherein the linear operator is to extract the secret from a constant term of the linear equation, or from a linear combination of coefficients and the constant term of the linear equation.

20. The system of claim 18, wherein each of the K shares contains K elements that represent a point on the secret hyperplane.