Sharing a secret using polynomials

A system comprising:

• non-transitory data storage to store a cryptographic key as secret, wherein the cryptographic key is used to encrypt or decrypt data;
• and
• a distributor computing system coupled to the data storage, the distributor computing system comprising:
• a processing device;
• a polynomial constructor, executed by the processing device, to construct a sharing polynomial with coefficients in GF(2m), m being at least as large as an effective length of the secret, one or more of the coefficients being the secret;
• and
• a polynomial evaluator, executed by the processing device, to evaluate, at n random points, the sharing polynomial modulo a primitive polynomial of degree m using polynomial operations and modulo 2 arithmetic, and to create n shares of the secret, with each of the n shares comprising one of the random points expressed as a random bit string in GF(2m) and a corresponding evaluated result.

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

• obtaining a cryptographic key as a secret represented as a first polynomial over GF(2), wherein the cryptographic key is used to encrypt or decrypt data;
• constructing a sharing polynomial with coefficients in GF(2m), m being at least as large as an effective length of the secret, one or more of the coefficients being the secret;
• evaluating the sharing polynomial modulo a primitive polynomial of degree m at n random points, using polynomial operations and modulo 2 arithmetic to generate n shares, each of the n shares comprising one of the random points expressed as a random bit string in GF(2m) and a corresponding evaluated result;
• and
• distributing the n shares to n cooperating computing systems.

A method, implemented by a computing device programmed to perform the following, the method comprising:

• obtaining, by the computing device, k shares of a cryptographic key as a secret, each of the k shares comprising a pair of elements in GF(2m), m being at least as large as an effective length of the secret, wherein the cryptographic key is used to encrypt or decrypt data;
• constructing, by the computing device, an interpolating polynomial to interpolate the pairs of elements in the k shares;
• computing, by the computing device, one or more of coefficients of the interpolating polynomial with polynomial operations modulo a primitive polynomial of degree m, using modulo 2 arithmetic;
• and
• recovering, by the computing device, the secret from the one or more of coefficients of the interpolating polynomial, the secret represented as a polynomial over GF(2).

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

• obtaining k shares of a cryptographic key as a secret, each of the k shares comprising a pair of elements in GF(2m), m being at least as large as an effective length of the secret, wherein the cryptographic key is used to encrypt or decrypt data;
• constructing an interpolating polynomial using the pairs of elements in the k shares;
• computing one or more of coefficients of the interpolating polynomial with polynomial operations modulo a primitive polynomial of degree m, using modulo 2 arithmetic;
• and
• recovering the secret from the one or more of the coefficients, the secret represented as a polynomial over GF(2).