# An equivalent definition for shamir secret sharing?

Taking into account this paper I will write here a definition that the authors provide.

$$\textbf{Definition:}$$ (linear secret sharing scheme). A $$(t,n)$$ secret sharing scheme is a linear secret sharing scheme when the $$n$$ shares, $$v_1,v_2,...,v_n$$ can be presented as in Equation $$\ref{5}$$

$$(v_1,v_2,...,v_n)=(k_1,k_2,...,k_t)H,\label{5}\tag{5}$$

where $$H$$ is a public $$t × n$$ matrix whose any $$t × t$$ submatrix is not singular. The vector $$(k_1,k_2,...,k_n)$$ is randomly chosen by the dealer.

According to Definition, we can see that Shamir’s $$(t, n)$$ secret sharing scheme is a linear scheme. Let

$$f(x)=a_0+a_1x+\cdots+a_{t-1}x^{t-1}, \label{6}\tag{6}$$

The shares $$v_i = f(i)$$, $$i = 1, 2, ..., n$$ can be presented as in Equation $$\ref{7}$$

$$(v_1,v_2,...,v_n)=(a_0,a_1,...,a_{t-1})H,\label{7}\tag{7}$$

How is $$\ref{7}$$ equivalent to $$\ref{6}$$? in some definitions it quotes $$y_i= f(x_i)$$ or $$y_i= f(x_i)\bmod{p}$$ how do they differ with $$\ref{7}$$?

• the secret sharing scheme of Shamir is linear after all? why? Jan 17, 2022 at 9:51
• @kelalaka in $(5)$ you can replace index $n$ of $k_n$ with $t$...I don't want to interupt your edit...because you are always helpful Jan 17, 2022 at 11:28
• No probs, see my edits and learn :) Jan 17, 2022 at 11:43

Well, one can assign shares as $$v_i=f(x_i)$$ or $$v_i=f(i)$$ as long as the $$x_i$$ are distinct it will work. The authors chose to use $$v_i=f(i)$$.
The observation that Shamir secret sharing is linear follows directly by using the definition of matrix multiplication. There is a typo in the paper though, the matrix entry quoted should be $$h_{i,j}=j^{i-1}$$ and they missed a minus sign in the paper.
• well the weird is with all these definitions that in some case they write $f(x)=...mod{p}$ in other cases $f(x)=...$ without modulo and in some cases $y_i\equiv_p f(x_i)$...to be quite frank, i can not understand the difference...do you? Jan 17, 2022 at 13:35
• in other words the definition says give me the points $(s,a_1,a_2,...a_{t-1})$ recall that $a_0=s$ and i can find a mapping $H(s,a_1,a_2,...a_{t-1})=(v_1,v_2...,v_n)$ such that the pairs $(i,v_i)$ $\forall i \in n$ are points of the polynomial function $H=f(x)=s+\sum_{i=1}^{t-1}a_ix^i$? Jan 17, 2022 at 13:51
• @HungerLearn: The math in Shamir's secret sharing is done in a finite field. The integers modulo a prime $p$ form such a finite field, but there are also other types of finite fields. (In particular, any set with $p^n$ elements, where $p$ is a prime and $n$ is a positive integer, can be given multiplication and addition operators that make it a finite field.) The confusion of notation you mention probably reflects that: some authors are assuming a prime-order field and using notation from modular arithmetic, while others just assume a generic field. Feb 16, 2022 at 15:04