Sharing a secret via linear interpolation

1. A method comprising:

creating, by a processing device, a plurality of shares for a secret, wherein the secret is embedded on a multi-dimensional secret hyperplane that is defined by a linear equation,

forming, by the processing device, a full-rank matrix comprising a plurality of rows, each row being different and non-parallel to a first vector formed by coefficients of the linear equation;

generating, by the processing device, a plurality of sub-shares from one of the plurality of shares using a second vector created from the full-rank matrix and the first vector, wherein each of the plurality of sub-shares comprises one of the rows in the full-rank matrix and a corresponding component of the second vector; and

distributing, by the processing device, the plurality of sub-shares.

2. The method of claim 1 , further comprising:

forming the linear equation using at least one of the secret or a sum of the secret and coefficients of the linear equation as a constant term of the linear equation.

3. The method of claim 2 , wherein forming the linear equation further comprises:

extending the length of the secret with random information to obtain an extended secret; and

grouping elements of the extended secret into a plurality of groups and using each group as a coefficient of the linear equation.

4. The method of claim 2 , wherein forming the linear equation further comprises:

using a known value for a coefficient of the linear equation; and

generating random values as other coefficients of the linear equation.

5. The method of claim 1 , wherein creating the plurality of shares comprises, for each share:

generating random values for variables in the linear equation;

computing a value of a remaining variable; and

forming the share using the random values and the value of the remaining variable.

6. A system comprising:

a memory;

a processing device coupled to the memory and configured to create a plurality of shares for a secret, wherein the secret is embedded on a multi-dimensional secret hyperplane that is defined by a linear equation;

form, by the processing device, a full-rank matrix comprising a plurality of rows, each row being different and non-parallel to a first vector formed by coefficients of the linear equation;

generate, by the processing device, a plurality of sub-shares from one of the plurality of shares using a second vector created from the full-rank matrix and the first vector, wherein each of the plurality of sub-shares comprises one of the rows in the full-rank matrix and a corresponding component of the second vector; and

distribute, by the processing device, the plurality of sub-shares.

7. The system of claim 6 , wherein the secret is used as a constant term of the linear equation.

8. The system of claim 6 , wherein a sum of the secret and coefficients of the linear equation is used as a constant term of the linear equation.

9. The system of claim 6 , wherein one coefficient of the linear equation is set to a known value and other coefficients set to random values.

10. 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:

creating, by the processing device, a plurality of shares for a secret, wherein the secret is embedded on a multi-dimensional secret hyperplane;

forming, by the processing device, a full-rank matrix comprising a plurality of rows, each row being different and non-parallel to a first vector formed by coefficients of the linear equation;

generating, by the processing device, a plurality of sub-shares from one of the plurality of shares using a second vector created from the full-rank matrix and the first vector, wherein each of the plurality of sub-shares comprises one of the rows in the full-rank matrix and a corresponding component of the second vector; and

distributing, by the processing device, the plurality of sub-shares.

11. The non-transitory computer readable medium of claim 10 , further comprising:

forming the linear equation using at least one of the secret or a sum of the secret and coefficients of the linear equation as a constant term of the linear equation.

12. The non-transitory computer readable medium of claim 11 , wherein forming the linear equation further comprises:

extending the length of the secret with random information to obtain an extended secret; and

grouping elements of the extended secret into a plurality of groups and using each group as a coefficient of the linear equation.

13. The non-transitory computer readable medium of claim 11 , wherein forming the linear equation further comprises:

using a known value for a coefficient of the linear equation; and

generating random values as other coefficients of the linear equation.

14. The non-transitory computer readable medium of claim 10 , wherein creating the plurality of shares comprises, for each share:

generating random values for variables in the linear equation;

computing a value of a remaining variable; and

forming the share using the random values and the value of the remaining variable.

15. A method comprising:

creating, by a processing device, a plurality of shares for a secret, wherein the secret is embedded on a multi-dimensional hyperplane that is defined by a linear equation;

creating, by the processing device, an identity matrix comprising identity elements as diagonal elements, zeros below the diagonal elements, and random elements above the diagonal elements;

generating, by the processing device, a full-rank matrix comprising a plurality of rows, and embedding the identity matrix in the plurality of rows, each row being different and non-parallel to a first vector formed by coefficients of the linear equation;

generating, by the processing device, a plurality of sub-shares from one of the plurality of shares using a second vector created from the full-rank matrix and the first vector, wherein each of the plurality of sub-shares comprises one of the rows in the full-rank matrix and a corresponding component of the second vector; and

distributing, by the processing device, the plurality of sub-shares.

16. The method of claim 15 , wherein generating the full-rank matrix comprises:

multiplying a target row by a non-zero random element of GF(2 m ) to produce a scaled target row; and

for each row lower than the target row, adding a random multiple of the scaled target row to the row.

17. A system comprising:

a memory;

a processing device coupled to the memory and configured to;

create, by the processing device, a plurality of shares for a secret, wherein the secret is embedded on a multi-dimensional secret hyperplane that is defined by a linear equation;

creating, by the processing device, an identity matrix comprising identity elements as diagonal elements, zeros below the diagonal elements, and random elements above the diagonal elements;

generating, by the processing device, a full-rank matrix comprising a plurality of rows, and embedding the identity matrix in the plurality of rows, each row being different and non-parallel to a first vector formed by coefficients of the linear equation;

generating, by the processing device, a plurality of sub-shares from one of the plurality of shares using a second vector created from the full-rank matrix and the first vector, wherein each of the plurality of sub-shares comprises one of the rows in the full-rank matrix and a corresponding component of the second vector; and

distributing, by the processing device, the plurality of sub-shares.

18. The system of claim 17 , wherein generating the full-rank matrix comprises:

multiplying a target row by a non-zero random element of GF(2 m ) to produce a scaled target row; and

for each row lower than the target row, adding a random multiple of the scaled target row to the row.