Admissible tracks in Shamir's scheme (Q609362): Difference between revisions

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''.