13
$\begingroup$

I read ampersand's question "Necessity for finite field arithmetic and the prime number p in Shamir's Secret Sharing Scheme", where he asked why Shamir's Secret Sharing Scheme uses arithmetic in a finite field of prime order.

The answers to that question explain that a prime field is not necessary for Shamir's scheme, but, rather, that any finite field can be used. However, they don't really address the other part of the question, namely why do we need a finite field at all? Couldn't we just use, say, ordinary integer arithmetic instead?

Can someone please explain (in the simplest possible manner) the reason that Shamir's Secret Sharing Scheme uses finite field arithmetic?

$\endgroup$
7
  • 2
    $\begingroup$ Shamir's Secret Sharing Scheme uses finite field arithmetic because one can easily $\hspace{1.3 in}$ sample elements almost-uniformly from a finite field. $\:$ $\endgroup$
    – user991
    Jul 18, 2013 at 8:58
  • $\begingroup$ Thats the only reason? It has nothing to do with security? $\endgroup$
    – Herc11
    Jul 18, 2013 at 9:01
  • 2
    $\begingroup$ Almost-uniform sampling is needed for security. $\:$ $\endgroup$
    – user991
    Jul 18, 2013 at 9:02
  • 3
    $\begingroup$ From at practical point of view, computers couldn't perform real field arithmetic anyway, since it can only represent real values approximately. By using a finite field, you are able to ensure the algorithm will output exact values. $\endgroup$ Jul 18, 2013 at 9:14
  • $\begingroup$ For calculating the interpolation polynomial one needs its coefficients to be elements of a field. Sampling random values uniformly from an infinite field is not possible, so you have to take a finite field. $\endgroup$
    – j.p.
    Jul 18, 2013 at 9:29

2 Answers 2

6
$\begingroup$

The reason that a field must be used in Shamir's reconstruction scheme is that the calculations used in the reconstruction need to divide one "number" by another, and division is not defined in $\mathbb Z$, the set of integers: $\frac{m}{n}$ is not necessarily a member of $\mathbb Z$. So, why not use $\mathbb R$, or $\mathbb Q$ which can be "implemented" in terms of pairs of integers? The answer again is that computers use floating-point arithmetic which is not the same as real arithmetic, or integer arithmetic which is, if we ignore overflow and underflow, effectively modular arithmetic in $\mathbb Z_{2^m}$ which is not a field but a ring. A more subtle issue is that the Shamir's scheme implicitly assumes that a polynomial of degree $n$ with coefficients in a field does not have more than $n$ roots in the field, which property is not true in rings. For example, the polynomial $x^2 - 1$ has four roots $\pm 1, \pm 4$ in the ring $\mathbb Z_{15}$ instead of the two $\pm 1$ that it has in a field such as $\mathbb Z_{17} = \mathbb F_{17}$.

As a concrete example of what might happen with integer arithmetic as implemented on a general-purpose computer, consider this formula for secret reconstruction $$s_0 = (-1)^k (x_1x_2x_3\cdots x_k) \sum_{i=1}^k \frac{y_i}{x_i\cdot c_i}$$ taken from another answer of mine. Here, $s_0$ is the secret that is reconstructed from shares $(x_i,y_i)$ (that is, $y_i = s(x_i)$) and $$c_i = (x_i-x_1)(x_i-x_2)\cdots(x_i-x_{i-1})(x_i-x_{i+1})\cdots(x_i-x_k).$$ Now consider the case where the $k$ shareholders who have gathered to reconstruct the secret all happen to have $x_i$ an odd integer. Then, $c_i$ is an even integer -- in fact, a multiple of $2^{k-1}$ -- and so $\frac{y_i}{x_i\cdot c_i}$ is not necessarily an integer. However, the sum $s_0$ will work out to be an integer. With ordinary integer arithmetic on a computer, the fractional parts of $\frac{y_i}{x_i\cdot c_i}$, if any, will be lost when the integer division indicated is computed, and thus $s_0$ will not be computed correctly. This is not to say that one could not manage this issue with careful programming that works around the problem, but we also have to deal with the possibility that the computations might cause overflow or underflow which also needs to be worked around. In any case, there can be problems that arise because the polynomials re-constructed via Lagrange interpolation are not necessarily the same as the ones used to construct the secret originally. Foe example, both $x^2-1$ and $(x-1)(x-4) = x^2-5x+4$ have roots $1$ and $4$ in $Z_{15}$. Since we don't know ahead of time which shares will be available for reconstruction, we cannot be sure whether we will reconstruct the correct polynomial in the Lagrange interpolation process. Thus, whether the secret recovery process will work as claimed in a ring is an open question. That the process will work in a field is guaranteed.

$\endgroup$
17
  • $\begingroup$ Thanks Dilip for your answer. Have you got any advice for this problem? crypto.stackexchange.com/questions/9294/… $\endgroup$
    – Herc11
    Jul 19, 2013 at 21:46
  • $\begingroup$ Your answer about the roots of $$x^2-1$$ puzzled me. If I ave a set of equations let's say with 3 equations and 3 unknowns, where the knowns and unknown variables are GF elements I cannot be sure that I ll find the right answer?It depends on the irreducible polynomial? I am referring to GF generated by ir. polynomials $\endgroup$
    – Herc11
    Jul 19, 2013 at 22:18
  • $\begingroup$ If the three equations have a unique solution in a field whether it is a prime field (integers modulo a prime $p$) or an extension field (what you seem to be referring to as "GF generated by ir. polynomials), then standard calculations will give the right answer. The choice of irreducible polynomial merely changes the names we give to elements of the extension field and so the answer might "look" different but it is still the same answer: all that has happened is that we are using a different basis to represent the answer. $\endgroup$ Jul 20, 2013 at 2:31
  • $\begingroup$ So, It can be solved?i.e If I know that the set is defined in such a way that there is a solution, this solution can be computed? the set had 4 equations does this change anything?If it is a bigger set e.g. 6 eq?Its the same? $\endgroup$
    – Herc11
    Jul 20, 2013 at 2:33
  • 1
    $\begingroup$ $$\begin{align}x+y+z&=1\\2x+2y+2z&=2\\3x+3y+3z&=3\end{align}$$ has multiple solutions but not a unique solution in any field; $$\begin{align}x+y+z&=0\\2x+2y+2z&=1\\3x+3y+3z&=1\end{align}$$ has no solutions in any field because the equations are inconsistent. $\endgroup$ Jul 20, 2013 at 2:48
4
$\begingroup$

The simplest answer is probably to give an example of information leaked when using Shamir's secret sharing over the integers. Assume that we construct a low degree example, defining $q$ to be a linear polynomial with $q(0)=D$ and $q(1)=a_1$. By interpolation you find that: $$q(x)=(a_1-D)x+D.$$

Assume that you are given the share corresponding to evaluation at $2$, i.e. $q(2)$. You can see that $q(2)=2a_1-D$. Since $a_1$ and $D$ are integers, given this single share, you learn the parity of $D$.

$\endgroup$
6
  • $\begingroup$ Therefore, the selection of the shares uniformly is not the only security reason. However I didnt understand why you learn something about D's parity. A more helpful example woule be if: $$f(x)=a_1x+D$$ and at 2 users the $$f(1)$$ and $$f(-1)$$ is assigned. Then the two users could easily recover D by adding their shares. $\endgroup$
    – Herc11
    Jul 18, 2013 at 14:21
  • 1
    $\begingroup$ @Herc11: Yes, but two users putting their shares together to recover the secret is part of the specifications (when using a linear polynomial). $\endgroup$
    – minar
    Jul 18, 2013 at 14:28
  • $\begingroup$ Yes, you re right. About the parity of D? $\endgroup$
    – Herc11
    Jul 18, 2013 at 14:30
  • 2
    $\begingroup$ Well, if $a_1$ is an integer, then $2a_1$ is even. So $2a_1-D$ is odd if and only if $D$ is odd. So the share $f(2)$ directly leaks the parity of $D$. $\endgroup$
    – minar
    Jul 18, 2013 at 14:32
  • 2
    $\begingroup$ No. $\:$ (In fact, that's a result of the integers not being a field, rather than a result $\hspace{1.56 in}$ of there being infinitely many integers.) $\;\;\;$ $\endgroup$
    – user991
    Jul 19, 2013 at 9:34

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.