1
$\begingroup$

I always thought that part of the idea behind SSS was that there is only a single $t-1$ degree polynomial through $t$ unique points; that this holds when the polynomial coefficients are over the reals and also in particular for SSS when the elements are chosen from a finite field. However I'm running into (what I think is) a counterexample -- so I must be doing something wrong :)

Consider SSS with modulus is $4$, so we are working in $\text{GF}(4)$. Assume the secret to be shared is $S = 3$, and the polynomial chosen ends up being $f(x) = x^2 + 2x + 3 \mod 4$. We pick three points $(0,3), (1,2), (3,2)$ on $f(x)$ as the shares (I'm aware the y-intercept should not be chosen as a share in this type of SSS scheme, but it's not super relevant to the question at hand). When I attempt to reconstruct the secret by solving the system of equations for the polynomial coefficients defined by the shares, I get two possible polynomials for $f(x) = a_2 x^2 + a_1 x + S \mod 4$.

$S = 3 \mod 4$

$a_2 + a_1 + S = 2 \mod 4$

$9a_2 + 3a_1 + S = 2 \mod 4$

Solving this system for the coefficients yields $a_1 = 0, a_2 = 3$ and $a_1 = 2, a_2 = 1$ as solutions, implying that two degree $2$ polynomials go through the $3$ points $(0,3), (1,2), (3,2)$. Namely $g(x) = 3x^2 + 3 \mod 4$ and $h(x) = x^2 + 2x + 3 \mod 4$. I thought there should only be one degree $2$ polynomial through $3$ distinct points?

I think my understanding is wrong somewhere, and would appreciate anyone pointing it out!

Improve this question
$\endgroup$
2
  • $\begingroup$ Rereading this closely, maybe the mistake is that the integers $\mod 4$ are not a field, since $2$ doesn't have an inverse $\mod 4$.. so the integers $\mod 4$ are not isomorphic to $\text{GF}(4)$. Then, the error in my thinking is that the integers $\mod p^k$ for prime $p$ and $k \geq 1$ are isomomorphic to $\text{GF}(p^k)$. In this case, can someone clarify when the integers modulo $p^k$ are isomorphic to $\text{GF}(p^k)$? $\endgroup$
    – Gordon
    Commented Mar 24 at 16:20
  • $\begingroup$ For $k>1$, the integers modulo $p^k$ are not isomorphic to GF$(p^k)$; for $k=1$, they are. That's all there is to it. $\endgroup$
    – Dilip Sarwate
    Commented Mar 25 at 16:25

1 Answer 1

Reset to default
3
$\begingroup$

You are operating in integers modulo $4$ which is not a field, it is $\mathbb{Z}_4.$ This means that there are zero divisors (for example $2\times2=0 \pmod 4$) and thus polynomial representation of functions is not unique.

Improve this answer
$\endgroup$

Your Answer

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

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