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?

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

  • $\begingroup$ No, it just needs to be done in a finite field (as jug stated). $\:$ $\endgroup$ – user991 May 28 '13 at 2:52
  • $\begingroup$ @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.) $\endgroup$ – D.W. May 28 '13 at 3:05
  • $\begingroup$ @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. $\endgroup$ – 0xFE May 28 '13 at 4:03
  • $\begingroup$ @0xFE, yes, that's correct. $\endgroup$ – D.W. May 28 '13 at 4:07

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.