Faulty share detection in Shamir’s secret sharing

A. Yu. Uteshev ; A. V. Marov

Vestnik Sankt-Peterburgskogo universiteta. Prikladnaâ matematika, informatika, processy upravleniâ, Tome 15 (2019) no. 2, pp. 274-282

Résumé

For Shamir's secret key sharing algorithm, we develop the procedure for detection of faulty shares. This procedure consists of the error locator polynomial construction for the data set $ \{ (x_j,y_j)\}_{j=1}^N $ with $ y $ values generated from $ x $ ones by a polynomial interpolant of a degree $ n N-1 $ with possible occurrence of some errors. The error locator polynomial is sought out in the form of an appropriate Hankel polynomial $$ \mathcal H_{L}(x;\{ \tau \}) := \left| \begin{array}{lllll} \tau_0 \tau_1 \tau_2 \ldots \tau_{L} \\ \tau_1 \tau_2 \tau_3 \ldots \tau_{L+1} \\ \vdots \vdots \vdots \vdots \\ \tau_{L-1} \tau_{L} \tau_{L+1} \ldots \tau_{2L-1} \\ 1 x x^2 \ldots x^{L} \end{array} \right| \, , $$ where $ \tau_{\ell} := \displaystyle \sum_{j=1}^{N} y_j \frac{x_j^{\ell}}{W^{\prime}(x_j)} $; $ \displaystyle W(x):=\prod_{j=1}^N (x- x_j) $.

Détail

Keywords: Shamir’s secret sharing, Hankel polynomials
Mots-clés : polynomial interpolation, error correction.