# Size of Parameters in Polynomial Key-Splitting Algorithm

I've seen the elegant way of splitting a key among different people so that only a certain number need to be present to re-compute the key, yet nobody has enough information to re-compute the key on their own. For example, if I want to split $K$ between 4 people, such that any 3 can re-compute the key, I first form a polynomial $y(x)=ax^2+bx+K$. Then I compute and distribute 4 pairs of the form $(x_i, f(x_i))$, one to each of the people.

It seems like $a, b, x$ should certainly be chosen with a cryptographically secure RNG, but is there any advice on how big they should be? Should they be as big as $K$? Big enough so that the term is about the same size as $K$ (which would make $a\approx K/x_i^2$, where $\approx$ means of the same order of magnitude)? As big as I can make them to the point that time to re-compute the key becomes an issue?

• In this setting one usually works over a finite field that has to be big enough for storing $K$. – j.p. May 27 '13 at 17:03
• @jug So I would take everything $\bmod \,2^n$ for example, where $n$ is the size of $K$? – 0xFE May 27 '13 at 22:28
• @jug Is there a security reason for using a finite field, because the row reduction seems easier without a finite field. – 0xFE May 28 '13 at 1:30
• Yes, because that allows one to select an element uniformly. $\:$ – user991 May 28 '13 at 2:54

All of this arithmetic must be done modulo $p$ (for some prime $p$ that is large enough so that it'll be larger than any conceivable $K$ you might ever want to use). You need to pick $p$ in advance.

Once you've picked $p$, then you choose $a$ and $b$ uniformly at random from the set of integers modulo $p$, i.e., uniformly at random from the set $\{0,1,2,\dots,p-1\}$.

The values $x_i$ can be, so long as they are distinct. A simple choice is to set $x_i=i$, i.e., $x_1=1$, $x_2=2$, $x_3=3$, $x_4=4$. That suffices.

(Working modulo $2^n$ is not secure. You need to work modulo a prime $p$.)

(Technically, you can work in any finite field; working modulo $p$ is just one way to get a finite field. However, if you don't know what a finite field is, you can ignore this remark. I'm adding this remark only to keep my fellow cryptographers happy.)

• No, it just needs to be done in a finite field (as jug stated). $\:$ – user991 May 28 '13 at 2:52
• @RickyDemer, yes, I know, but at the level of understanding that this question-er is prepared for, I think my answer is simplest. (And I'm not aware of any significant reason why using $GF(p^n)$ is better than $GF(p)$, in practice.) – D.W. May 28 '13 at 3:05
• @D.W. I know a little bit about finite fields, and I think I know where I went wrong: $GF(p)$ is the same as working $\bmod\,p$, but $GF(p^n)$ is not the same as working $\bmod\,p^n$, right? This means that while two is prime, $\bmod\,2^n$ is not actually a finite field. – 0xFE May 28 '13 at 4:03
• @0xFE, yes, that's correct. – D.W. May 28 '13 at 4:07