3
$\begingroup$

I have been working through the introduction to cryptography with coding theory book and have just come across Shamir secret sharing questions. However I just don't quite think I'm understanding it correctly. The question states:

In a (2,19) Shamir threshold scheme working in modulo 41, there are two shares (2,14) and (4,25). Another share is (3,x) where x is unreadable. Find x, the polynomial and the message.

I understand that I must solve for a line that interpolates (2,14) and (4,25) but haven't made it much further and have struggled to find questions in a similar structure. Any help would be greatly appreciated!

$\endgroup$

1 Answer 1

4
$\begingroup$

To solve for the line you want, you really do the "basic" thing you might expect. The formula for a line is $f(x) = ax + b$. We know that $f(2) = 2a + b = 14$, and $f(4) = 4a + b = 25$. It follows that $f(4) - f(2) = 2a = 11$, so $a = 11\times 2^{-1}\bmod 41$. We have that $21\times 2\equiv 1\bmod 41$, so $ a = 11\times 21\bmod 41 = 26$. You can then solve that $f(2) = 2\times 26 + b = 14\implies b \equiv 38$. So $f(x) = 26x + 38$.

This argument works, but doesn't scale to higher-degree polynomials well. To do this, it helps to know some linear algebra. Specifically, the space of all polynomials of a given degree over a field $k$ $\mathcal{P}_n(k) = \{\sum_{i = 0}^n a_ix^i\mid a_i\in k\}$ forms a vector space over $k$. This vector space is of dimension $n+1$. One obvious basis for it is the monomial basis $\{1,x,\dots,x^{n+1}\}$.

For any set of $n+1$ points $x_1,\dots,x_{n+1}\in k$, there is a special matrix called the Vandermonde matrix. It maps polynomials (written in the monomial basis) to the "evaluation basis", i.e. sends a polynomial $p(x) = \sum_{i=0}^n a_ix^i = (a_0,\dots,a_n)$ (in the monomial basis) to an "evaluation representation" $(p(x_0),\dots,p(x_{n+1}))$. Anyway, the general way to reconstruct Shamir's secret sharing is

  1. collect enough evaluation points $(p(x_0),\dots,p(x_{n+1}))$
  2. use the (inverse) vandermonde matrix to change basis to the monomial basis $p(x) = \sum_{i=0}^n a_ix^i$
  3. evaluate $p(0)$.

There are optimizations you can do to this (you don't need to compute a full matrix-vector product, as you only need a single entry $p(0) = a_0$ from the result, so it suffices to compute an inner product), but the above is what I find most conceptually clear.

$\endgroup$
2
  • 1
    $\begingroup$ Thanks Mark you've made that much clearer to me now. I appreciate it! $\endgroup$
    – Des_lat
    Feb 8, 2023 at 4:34
  • $\begingroup$ @Mark Schultz-Wu Could you please provide some references for the general way to reconstruct Shamir's secret-sharing scheme? Wikipedia has an example, but not for modulo a prime. $\endgroup$ May 14 at 12:46

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.