Extending a secret bit string to safeguard the secret
A method and system extends a secret bit string to safeguard the secret. In one embodiment, the method comprises adding a secret bit string of length s to a product of two random bit strings using arithmetic defined for polynomials over GF(2) to produce an extended bit string. The extended bit string has a length m that is longer than s. A total of n shares are generated from the extended bit string, of which at least k shares are needed to reconstruct the secret bit string. The n shares are distributed to a plurality of cooperating computing entities for secret sharing.
1. A method comprising:
creating a plurality of moduli, wherein the plurality of moduli comprises a plurality of random bit strings;
determining, by a computer system, a bit length to use to construct an extended secret bit string, wherein the bit length of the extended secret bit string is at least one bit shorter than a product of a first number of the plurality of moduli and at least one bit longer than a product of a second number of the plurality of moduli, and wherein the first number is a number of shares to reconstruct a secret bit string, and the second number is the first number minus one;
generating, by the computing system, a first bit string comprising a bit length at least one bit longer than a number of bits in the secret bit string, the first bit string corresponding to a first polynomial and the secret bit string corresponding to a second polynomial;
generating a second bit string comprising the bit length of the extended bit string minus the bit length of the first bit string, wherein the second bit string corresponds to a third polynomial;
determining a product of the first bit string and the second bit string as polynomials to form the extended secret bit string, the extended secret bit string corresponding to a fourth polynomial;
adding the secret bit string to the product; and
generating a plurality of shares to distribute from the extended secret bit string.
2. The method of claim 1 , wherein each of the plurality of shares comprises a modulus and a remainder.
3. The method of claim 1 , wherein the first bit string is a random bit string.
4. The method of claim 1 , wherein the first bit string and the second bit string are pairwise coprime in GF(2).
5. The method of claim 1 , wherein the first bit string is an irreducible polynomial over GF(2).
6. The method of claim 1 , wherein the second bit string is a random bit string generated from a cryptographic source.
7. A system comprising:
a memory;
data storage to store a secret bit string; and
a processing device coupled to the data storage and the memory to:
create a plurality of moduli, wherein the plurality of moduli comprises a plurality of random bit strings;
determine a bit length to use to construct an extended secret bit string, wherein the bit length of the extended secret bit string is at least one bit shorter than a product of a first number of the plurality of moduli and at least one bit longer than a product of a second number of the plurality of moduli, and wherein the first number is a number of shares to reconstruct a secret bit string, and the second number is the first number minus one;
generate a first bit string comprising a bit length at least one bit longer than a number of bits in the secret bit string, the first bit string corresponding to a first polynomial and the secret bit string corresponding to a second polynomial;
generate a second bit string comprising the bit length of the extended bit string minus the bit length of the first bit string, wherein the second bit string corresponds to a third polynomial;
determine a product of the first bit string and the second bit string as polynomials to form the extended secret bit string, the extended secret bit string corresponding to a fourth polynomial;
adding the secret bit string to the product; and
generate a plurality of shares to distribute from the extended bit string.
8. The system of claim 7 , wherein each of the plurality of shares comprises a modulus and a remainder.
9. The system of claim 7 , wherein the first bit string is a random bit string.
10. The system of claim 7 , wherein the first bit string and the second bit string are pairwise coprime in GF(2).
11. The system of claim 7 , wherein the first bit string is an irreducible polynomial over GF(2).
12. A non-transitory computer readable storage medium including instructions that, when executed by a processing device, cause the processing device to perform operations comprising:
creating a plurality of moduli, wherein the plurality of moduli comprises a plurality of random bit strings;
determining, by the processing device, a bit length to use to construct an extended secret bit string, wherein the bit length of the extended secret bit string is at least one bit shorter than a product of a first number of the plurality of moduli and at least one bit longer than a product of a second number of the plurality of moduli, and wherein the first number is a number of shares to reconstruct a secret bit string, and the second number is the first number minus one;
generating, by the processing device, a first bit string comprising a bit length at least one bit longer than a number of bits in the secret bit string, the first bit string corresponding to a first polynomial and the secret bit string corresponding to a second polynomial;
generating a second bit string comprising the bit length of the extended bit string minus the bit length of the first bit string, wherein the second bit string corresponds to a third polynomial;
determining a product of the first bit string and the second bit string as polynomials to form the extended secret bit string, the extended secret bit string corresponding to a fourth polynomial;
adding the secret bit string to the product; and
generating a plurality of shares to distribute from the extended secret bit string.
13. The non-transitory computer readable medium of claim 12 , wherein each of the plurality of shares comprises a modulus and a remainder.
14. The non-transitory computer readable medium of claim 12 , wherein the first bit string is a random bit string.
15. The non-transitory computer readable medium of claim 12 , wherein the first bit string and the second bit string are pairwise coprime in GF(2).
16. The non-transitory computer readable medium of claim 12 , wherein the first bit string is an irreducible polynomial over GF(2).
17. A method comprising:
receiving a first bit string comprising a bit length at least one bit longer than a number of bits in a secret bit string;
receiving, by a processing device, an extended secret bit string calculated from the first bit string, the secret bit string, and a second bit string, wherein a bit length of the extended secret bit string is at least one bit shorter than a product of a first number of a plurality of moduli and at least one bit longer than a product of a second number of the plurality of moduli, and wherein the first number is a number of shares to reconstruct the secret bit string and the second number is the first number minus one;
dividing, by the processing device, the extended secret bit string by the first bit string; and
determining, by the processing device, a remainder from dividing the extended secret bit string by the first bit string, wherein the reminder is identified as the secret bit string.
18. The method of claim 17 , wherein the extended bit string is generated from a plurality of shares, each share comprising a modulus and a remainder.
19. The method of claim 17 , wherein the first bit string corresponds to an irreducible polynomial over GF(2).
20. A non-transitory computer readable storage medium including instructions that, when executed by a processing device, cause the processing device to perform operations comprising:
receiving a first bit string comprising a bit length at least one big longer than a number of bits in a secret bit string;
receiving, by the processing device, an extended secret bit string calculated from the first bit string, the secret bit string, and a second bit string, wherein a bit length of the extended secret bit string is at least one bit shorter than a product of a first number of a plurality of moduli and at least one bit longer than a product of a second number of the plurality of moduli, and wherein the first number is a number of shares to reconstruct the secret bit string and the second number is the first number minus one;
dividing, by the processing device, the extended bit string by the first bit string; and
determining, by the processing device, a remainder from dividing the extended secret bit string by the first bit string, wherein the reminder is identified as the secret bit string.
21. The non-transitory computer readable medium of claim 20 , wherein the extended bit string is generated from a plurality of shares, each share comprises a modulus and a remainder.
22. The non-transitory computer readable medium of claim 20 , wherein the first bit string corresponds to an irreducible polynomial over GF(2).