# How share size is reduced in robust secret sharing?

THIS IS ROBUST SECRET SHARING SCHEME

The dealer $\mathcal{D}$ wants to share a secret among the participants $\{P_1, P_2, \ldots, P_n\}$, where at most $t$ participants are malicious and $t<n/2$. For $i = 1, \ldots, n$, let the distinct elements $\alpha_{i}\in\mathbb{F}_{2^q} \setminus \{0\}$ be fixed and public, where $q$ is positive integer such that the cardinality of the field $\mathbb{F}_{2^q}$ is larger than $n$. The dealer $\mathcal{D}$ chooses randomly a polynomial $f(x)\in\mathbb{F}_{2^q}[X]$ of degree at most $t$, where $f(0) = s$ is the secret to be shared, and computes $f (\alpha_{i}) = s_i$ in $\mathbb{F}_{2^q}$, where $i = 1, \ldots, n$. $\mathcal{D}$ chooses randomly $k_{i, j} = (\alpha_{i,j}, \beta_{i,j})$ from $\mathbb{F}_{2^q} \times \mathbb{F}_{2^q}$, and computes $y_{i, j} = \alpha_{j,i} s_i + \beta_{j, i}$, where $j = 1, 2, \ldots, n$ and $i = 1, \ldots, n$. $\mathcal{D}$ privately sends to each $P_i$ the share $$S_i = (s_i, y_{i,1}, \ldots, y_{i, n}, k_{1, i}, \ldots, \ldots, k_{n, i}).$$ Reconstruction Phase: Round 1: Each $P_i$ sends $(s'_i, y'_{i,1}, \ldots, y'_{i, n})$ to the reconstructor $\mathcal{R}$. Round 2: Each $P_i$ sends $(k'_{i, 1}, \ldots, k'_{i, n})$ to the reconstructor $\mathcal{R}$. Computation by $\mathcal{R}$: $\mathcal{R}$ sets $v_{ij}$, $i, j \in \{1,2, \ldots, n\}$, to be $1$ if $P_i$'s authentication tag is accepted by $P_j$, i.e., if $y'_{i, j} = \alpha'_{j,i} s'_i + \beta'_{j, i}$; otherwise she sets $v_{ij}$ to $0$.

\item $\mathcal{R}$ computes the set $\mathcal{I} \subseteq \{1,2, \ldots, n\}$ with the property that $$\forall i \in \mathcal{I}: |\{j \in \{1,2, \ldots, n\} | v_{ij} = 1\}| = \Sigma_{j \in \{1,2, \ldots, n\}} v_{ij} \geq t+1.$$

Clearly, $\mathcal{I}$ contains all honest participants.

Using Lagrange's interpolation method, $\mathcal{R}$ computes a polynomial $f(x) \in \mathbb{F}_{2^q}[X]$ of degree at most $t$ such that $f(\alpha_i) = s'_i$ for at least $(t + 1)$ participants $i$ in $\mathcal{I}$. If no such polynomial exists then output $\perp$, otherwise, output $s = f(0)$.

NOW IN ROBUST SECRET SHARING SCHEME WITH REDUCED SHARE SIZE WHAT WE CHANGE IS THE FIELD OF KEY SPACE

$\mathcal{D}$ chooses randomly $k_{i, j} = (\alpha_{i,j}, \beta_{i,j})$ from $\mathbb{F}_{2^m} \times \mathbb{F}_{2^m}$, and computes $y_{i, j} = \alpha_{j,i} s_i + \beta_{j, i}$, where $j = 1, 2, \ldots, n$ and $i = 1, \ldots, n$. Where $\mathbb{F}_{2^m}$ is larger than $n$. And $q$and $m$ are different.

Now i dont understand how share is reduced?

• Is it possible for you to share the paper where you got this scheme from? – Louis Jun 14 '16 at 2:56
• Sorry. I can't. – Sayantan Koley Jun 14 '16 at 19:35