PROJECTS: n of m

[Scott A Crosby]

I'm not on the development list, so CC me any replies.

You don't seem to have discussed this on the mailing list archive, so
here it is. 

There is a very elegant way of implementing n of m using polynomials, I've
heard that pgp uses it.

You know the old axiom: 2 points determine a line, 3 points determine a
parabola? You can use this technique to encode a secret and split it up
among $m$ people so that it requires $n$ to decode it.


Given a secret $N$, where $N$ is bounded to be under some prime $p$,
compute the following module $p$

create a random polynomial $P(x) = \sum_{i=1}^{n-1} a_i x^i + N$, where
$a_{n-1}$ is not zero. Pick any tuple, random or deterministic, $x_1, ...,
x_m$ with no duplicates. Hand out the pairs $(x_i, P(x_i))$ to the n
people. 

I have now taken the secret and encoded it as the y-intercept of some
polynomial of degree $n-1$, this means that from any $n$ points determine
the polynomial, and the y-intercept uniquely. I have also distributed the
secret between $m$ people.

Let the pairs be: $(x_i,y_i)$, then the polynomial may be generated as:


P(x) = \sum_{i=1}^n  y_i * 
       ((x-x_1) * (x-x_2) ... (x-x_{i-1}) (x-x_{i+1}) ....
                                               (x-x_{n-1}) (x-x_n)) 
                                  /
       ((x_i-x_1) * (x_i- x_2) ... (x_i-x_{i-1}) (x_i-x_{i+1}) ....
                                    (x_i-x_{n-1}) (x_i-x_n))


Evaluate P(0) to regenerate the secret $N$ from the $n$ pairs. 




This is just a suggestion for how to implement that functionality. Other
than that, nice program, gpg is great!

Scott