Sharing a secret using polynomial division over GF(Q)
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.
1. A computer-implemented method comprising:
representing a secret as a secret polynomial having a first degree, over GF(q), q being a prime or a power of a prime;
embedding the secret polynomial into an extension polynomial having a second degree that is greater than the first degree; and
dividing, by a processing device, the extension polynomial by a first number of coprime divisor polynomials over GF(q), using arithmetic defined for polynomials over GF(q), to generate a second number of shares of the secret for secret sharing among a plurality of cooperating entities, wherein the first number is equal to the second number and wherein each share comprises one of the divisor polynomials and a corresponding remainder.
2. The method of claim 1 , wherein the second degree of the extension polynomial is less than a lowest-degree product of a third number of the divisor polynomials and is greater than a highest-degree product of one less than the third number of the divisor polynomials, the third number 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 between the third number and the first number.
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 of bits g 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 comprising:
data storage to store a secret; and
a processing device coupled to the data storage and configured to:
represent the secret as a secret polynomial having a first degree over GF(q), q being a prime or a power of a prime;
embed the secret polynomial into an extension polynomial having a second degree that is greater than the first degree; and
divide the extension polynomial by a first number of coprime divisor polynomials over GF(q), using arithmetic defined for polynomials over GF(q), to generate a second number shares of the secret for secret sharing among a plurality of cooperating entities, wherein the first number is equal to the second number and wherein each share comprises one of the divisor polynomials and a corresponding remainder.
9. The system of claim 8 , wherein the second degree of the extension polynomial is less than a lowest-degree product of a third number of the divisor polynomials and is greater than a highest-degree product of one less than the third number of the divisor polynomials, the third number representing a minimum number of shares from which the secret can be reconstructed.
10. The system of claim 8 ,
wherein the processing device is further configured 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 processing device operates with an array processor or embedded hardware.
12. The system of claim 8 , wherein the processing device 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 processing device is to represent the secret as a sequence of coefficients of the secret polynomial, each coefficient associated with a predetermined number of bits g used in a binary coding scheme, where q is a smallest prime number or a smallest prime power greater than 2 g .
14. A non-transitory computer readable storage medium including instructions that, when executed by a processing device, cause the processing device to perform a method comprising:
representing a secret as a secret polynomial having a first degree over GF(q), q being a prime or a power of a prime;
embedding the secret polynomial into an extension polynomial having a second degree that is greater than the first degree; and
dividing, by the processing device, the extension polynomial by a first number of coprime divisor polynomials over GF(q), using arithmetic defined for polynomials over GF(q), to generate a second number of shares of the secret for secret sharing among a plurality of cooperating entities, wherein the first number is equal to the second number and wherein each share comprises one of the divisor polynomials and a corresponding remainder.
15. The non-transitory computer readable medium of claim 14 , wherein the second degree of the extension polynomial is less than a lowest-degree product of a third number of the divisor polynomials and is greater than a highest-degree product of one less than the third number of the divisor polynomials, the third number representing a minimum number of shares from which the secret can be reconstructed.
16. The non-transitory 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 non-transitory computer readable medium of claim 14 , wherein the secret is to be reconstructed with any integer number of the shares in a range between the third number and the first number.
18. The non-transitory 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 non-transitory 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 of bits g used in a binary coding scheme, where q is a smallest prime number or a smallest prime power greater than 2 g .
20. The non-transitory 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.