# Solving Shamir secret sharing schemes

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!

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.

• Thanks Mark you've made that much clearer to me now. I appreciate it! Feb 8, 2023 at 4:34
• @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. May 14 at 12:46