Authenticated secret sharing
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.
1. A method comprising:
computing, by a processing device, an authentication code of a secret using a key;
constructing, by the processing device, a mathematical construct using the authentication code, the secret, the key, and a first number of random values, wherein the first number is three less than a threshold number of shares for reconstructing the secret; and
using, by the processing device, a second number of instances of the mathematical construct to generate the second number of 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 the second number of random evaluation points to obtain the second number of result values; and
generating the second number of shares of the secret, each share comprising one of the second number of evaluation points and a corresponding result value.
3. The method of claim 1 wherein the mathematical construct is a system of the second number of distinct linear equations over GF(q) having the threshold number of unknowns, q being a power of a prime number, each equation having a solution that comprises the authentication code, the secret and the key, and any set of the threshold number of equations is linearly independent, the method further comprising:
generating the second number of shares of the secret, each share comprising one of the second number of linear equations.
4. The method of claim 1 wherein the mathematical construct is a linear equation comprising 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 the second number of shares of the secret further comprises:
distributing more than one share to each cooperating entity, with any of a third number of cooperating entities being able to reconstruct the secret and any of a fourth number of cooperating entities not being able to reconstruct the secret, wherein the fourth number is one less than the third number.
9. The method of claim 1 , wherein generating the second number of shares of the secret further comprises:
distributing the second number of shares to the cooperating entities, without informing the cooperating entities of the number of shares necessary for reconstructing the secret.
10. A system comprising:
data storage to store the secret; and
a processing device coupled to the data storage, the processing device 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 a first number of random values, wherein the first number is three less than a threshold number of shares for reconstructing the secret, and to use a second number of instances of the mathematical construct to generate the second number of 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 the second number of random evaluation points to obtain the second number of result values, and to generate the second number of shares with each share comprising one of the second number of evaluation points and a corresponding result value.
12. The system of claim 10 , wherein the first circuitry comprises a hash unit to compute a hash value of the secret and the key.
13. A non-transitory computer readable storage medium comprising instructions that, when executed by a processing device, cause the processing device to perform operations comprising:
computing an authentication code of a secret using a key;
constructing, by the processing device a mathematical construct using the authentication code, the secret, the key, and a first number of random values, wherein the first number is three less than a threshold number of shares for reconstructing the secret; and
using a second number of instances of the mathematical construct to generate the second number of shares of the secret for distributed storage among cooperating entities.
14. The non-transitory computer readable storage medium of claim 13 , wherein the mathematical construct is a splitting polynomial and the operations further comprise:
evaluating the splitting polynomial at the second number of random evaluation points to obtain the second number of result values; and
generating the second number of shares of the secret, each share comprising one of the second number of evaluation points and a corresponding result value.
15. The non-transitory computer readable storage medium of claim 13 , wherein the mathematical construct is a system of the second number of distinct linear equations over GF(q) having the threshold number of unknowns, q being a power of a prime number, each equation having a solution that comprises the authentication code, the secret and the key, and any set of the threshold number of equations is linearly independent, the operations further comprising:
generating the second number of shares of the secret, each share comprising one of the second number of linear equations.
16. The non-transitory computer readable storage 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.