From A First Course in Linear Algebra
Version 2.99
© 2004.
Licensed under the GNU Free Documentation License.
http://linear.ups.edu/
This Section is a Draft, Subject to Changes
In this section we will see how to use solutions to systems of equations to share a secret among a group of people. We will be able to break a secret up into, say 10 pieces, so as to distribute the secret among 10 people. But rather than requiring all 10 people to collaborate on restoring the secret, we can design the split so that any smaller group, of say just 4 of these people, can collaborate and restore the secret. The numbers 10 and 4 here are arbitrary, we can choose them to be anything.
Suppose we have a secret,
Suppose you wish to give parts of your secret to
We will describe the split, with no motivation. The explanation of how the secret
recovery is handled will explain our choices here. Choose a large prime number,
Compute the pairs r(i))
Now suppose that m of these people get together, in the event you are unable to act, or perhaps without your permission. Suppose they pool all of their pairs, or even just turn them over to one member of the group. What do they now know collectively? Suppose that
where, of course, {a}_{0} = S is the secret. A single pair, (i,\kern 1.95872pt r(i)), results in a linear equation whose unknowns are the m coefficients of r(x). With m pairs revealed, we now have m equations in m variables. Furthermore, the coefficient matrix of this system is a Vandermonde matrix (Definition VM). With our inputs to the polynomial all different (we used 1,\kern 1.95872pt 2,\kern 1.95872pt 3,\kern 1.95872pt \mathop{\mathop{…}},\kern 1.95872pt n), the Vandermonde matrix is nonsingular (Theorem NVM). Thus by Theorem NMUS there is a unique solution for the coefficients of r(x). We only desire the constant term — the other coefficients (the randomly chosen ones) are of no interest, they were used to mask the secret as it was split into parts.
A few practical considerations. If certain individuals in your group are more important, or more trustworthy, you can give them more than one part. You could split a secret into 30 parts, giving 5 Vice-Presidents each 4 parts and give 10 department heads each 1 part. Then you might require 12 parts to be present. This way three Vice-Presidents could recover the secret, or 4 department heads could stand-in for a Vice-President. Furthermore, the 10 department heads could not recover the secret without having at least one Vice-President present.
The inputs do not have to be consecutive integers, starting at 1. Any set of different integers will suffice. Why make it any easier for an attacker? Mix it up and choose the inputs randomly as well, just keep them different.
Why do all this arithmetic over {ℤ}_{p}? If we worked with polynomials having real number coefficients, properties of polynomials as continuous functions might give an attacker the ability to compute the secret with a reasonable amount of computing time. For example, the magnitude of the output is going to dominated by the term of r(x) having degree m − 1. Suppose an attacker had a few of the pairs, but not a full set of m of them. Or even worse, suppose some group of fewer than m of your trusted acquaintances were to conspire against you. It might be possible to guess a limited range of values for the coefficient of the largest term. With a limited range of values here, the next term might fall to a similar analysis. And so on. However, modular arithmetic is in some ways very unpredictable looking and as high powers “wrap-around” this sort of analysis will be frustrated. And we know it is no harder to do linear algebra in {ℤ}_{p} than in ℂ.
OK, here’s a non-trivial example.
Example SS6W
Sharing a secret 6 ways
Let’s return to the CEO and his six Vice-Presidents. Suppose the
password for the company’s accounts is a sequence of 5 two-digit
numbers, which we will concatenate into a 10-digit number, in this case
S = 0603725962. For a prime
p we choose the 11-digit
prime number p = 22801761379. From
the requirement that m = 3
Vice-Presidents are needed to recover the secret, we need a second-degree polynomial
and so need two more coefficients, which we will construct at random between
1 and
p. The
resulting polynomial is
We will now build six pairs of inputs and outputs, where we will choose the inputs at random (not allowing duplicates) and we do all our arithmetic modulo p,
VP | x | r(x)
|
Finance | 20220406046 | 7205699654 |
Human Resources | 8862377358 | 17357568951 |
Marketing | 13747127957 | 18503158079 |
Legal | 15835120319 | 14060705999 |
Research | 6530855859 | 5628836054 |
Manufacturing | 9222703664 | 2608052019 |
The two numbers of each row of the table are then given to the indicated Vice-President. Done. The secret has been split six ways, and any three VP’s can jointly recover the secret.
Let’s test the recovery process, especially since it contains the relevant linear algebra. Suppose we write the unknown polynomial as r(x) = {a}_{0} + {a}_{1}x + {a}_{2}{x}^{2} and the VP’s for Finance, Marketing and Legal all get together to recover the secret. The equations we arrive at are,
So they have a linear system, ℒS\kern -1.95872pt \left (A,\kern 1.95872pt b\right ) with
With a Vandermonde matrix as the coefficient matrix, they know there is a solution, and it is unique. By Theorem SNCM (or through row-reducing the augmented matrix) they arrive at the solution,
So the CEO’s password is the secret S = {a}_{0} = 603725962 = 0603725962 (as expected). ⊠