Admissible tracks in Shamir's scheme
type: Item
instance of: scholarly article
title: Admissible tracks in Shamir's scheme
zbMATH Open document ID: 1209.94054
author: Stanisław Spież
author: Jerzy Urbanowicz
author: Andrzej Schinzel
published in: Finite Fields and their Applications
publication date: 2010-11-30T00:00:00Z
review text: In Shamir's classic secret sharing schemes, a secret is coded as the independent coefficient \(a_0\) of a polynomial \(P(X) = \sum_{j=0}^{k-1} a_jX^j\) over a finite field. Provided a set, or \textit{track}, of pairwise different points \(\left(x_{\nu}\right)_{\nu=0}^{n-1}\), the \(\nu\)-th share \((x_{\nu},y_{\nu}) =(x_{\nu},P(x_{\nu}))\) is given to the \(\nu\)-th participant. Clearly, when \(k\) shares are put together, direct interpolation allows the recovering of the polynomial \(P(X)\) and consequently of the secret \(a_0\). This determines a \textit{\(k\)-out-of-\(n\)} secret sharing scheme (SSS). The authors call a subset of a track a \textit{privileged coalition} if it has fewer than \(k\) elements but its shares allow to recover a secret. A track is \textit{\((k,i)\)-admissible} if no privileged coalition exists when the secret is coded as the coefficient \(a_i\) in a Shamir's like SSS, and it is \textit{\(k\)-admissible} if it is \((k,i)\)-admissible for each \(i\). The coalitions are characterized in the paper as roots of some homogeneous symmetric polynomials. Some interesting counting results are given, e.g. the number of \((k,i)\)-admissible tracks over \(\mathbb{F}_q\), namely \(q^n-\left[{n\choose 2}+{n\choose k-1}\right]q^{n-1} + O(q^{n-2})\), the number of \(k\)-admissible tracks and the number of privileged coalitions with exactly \(k-1\) participants. The characterization of coalitions and the estimated bounds allow the authors to state at the end of the paper effective algorithms to build admissible tracks and to extend them while preserving ``admissibility''.
Mathematics Subject Classification ID: 94A62
Mathematics Subject Classification ID: 11T71
zbMATH DE Number: 5821497
zbMATH Keywords: secret sharing
zbMATH Keywords: elementary symmetric polynomials
zbMATH Keywords: equations in many variables over finite fileds
zbMATH Keywords: threshold access structure
reviewed by: Guillermo Morales Luna
MaRDI profile type: Publication
full work available at URL: j.ffa.2010.09.003
OpenAlex ID: W1991374353
cites work: Q4204100
cites work: Several Generalizations of Shamir's Secret Sharing Scheme
cites work: Q5690468
cites work: Q4674810
cites work: How to share a secret
cites work: Elementary symmetric polynomials in Shamir's scheme
cites work: Q4839149
DOI: 10.1016/J.FFA.2010.09.003
description: scientific article; zbMATH DE number 5821497