0
$\begingroup$

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?

Improve this question
$\endgroup$
4
  • 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, 2013 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, 2013 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, 2013 at 1:30
  • 1
    $\begingroup$ Yes, because that allows one to select an element uniformly. $\:$ $\endgroup$
    – user991
    May 28, 2013 at 2:54

1 Answer 1

Reset to default
2
$\begingroup$

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.)

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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