AUTHENTICATED SECRET SHARING
First Claim
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.
1 Assignment
0 Petitions
Accused Products
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.
-
Citations
21 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; andusing, by the computing system, N instances of the mathematical construct to generate N shares of the secret for distributed storage among cooperating entities. - View Dependent Claims (2, 3, 4, 5, 6, 7, 8, 9)
-
-
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. - View Dependent Claims (11, 12)
-
-
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; andusing N instances of the mathematical construct to generate N shares of the secret for distributed storage among cooperating entities. - View Dependent Claims (14, 15, 16)
-
-
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. - View Dependent Claims (18, 19, 20)
-
-
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.
-
Specification