PROJECTS: n of m

Scott A Crosby crosby at qwes.math.cmu.edu
Fri Sep 10 07:20:00 CEST 1999

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