RUS  ENG
Full version
JOURNALS // Vestnik Sankt-Peterburgskogo Universiteta. Seriya 10. Prikladnaya Matematika. Informatika. Protsessy Upravleniya // Archive

Vestnik S.-Petersburg Univ. Ser. 10. Prikl. Mat. Inform. Prots. Upr., 2019 Volume 15, Issue 2, Pages 274–282 (Mi vspui407)

This article is cited in 1 paper

Computer science

Faulty share detection in Shamir’s secret sharing

A. Yu. Utesheva, A. V. Marovb

a St. Petersburg State University, 7–9, Universitetskaya nab., St. Petersburg, 199034, Russian Federation
b RAIDIX, 33 (A), nab. reki Smolenki, St. Petersburg, 199178, Russian Federation

Abstract: 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) $.

Keywords: Shamir’s secret sharing, polynomial interpolation, Hankel polynomials, error correction.

UDC: 621.394.147

MSC: 94A62

Received: January 30, 2019
Accepted: March 15, 2019

Language: English

DOI: 10.21638/11701/spbu10.2019.210



Bibliographic databases:


© Steklov Math. Inst. of RAS, 2024