Non-admissible tracks in Shamirʼs scheme

We consider Shamirʼs secret sharing schemes, with the secret placed as ai in the scheme polynomial f(x)=a0+⋯+ak−1xk−1, determined by sequences , called tracks, of pairwise different public identities assigned to shareholders. The shares are given by yj=f(tj), 1⩽j⩽n.If a track t defines Shamirʼs scheme with threshold k then t is called (k,i)-admissible (cf. Schinzel et al., 2010 [11], and Spież et al., 2010 [14], ). If t is not (k,i)-admissible, then there is a coalition, called (k,i)-privileged, consisting of less than k shareholders, who can reconstruct the secret ai by themselves. In Schinzel et al. (2010) [11], given i≠0,k−1, it was proved that the number of privileged coalitions of maximal length is qk−2+O(qk−3), where the constant in the O-symbol depends on k and i.In this paper we characterize (k,i)-privileged coalitions of length r as common zeros of k−r elementary symmetric polynomials τj(s)=0, r−i⩽j⩽k−1−i. We prove that special coalitions being (k,i)-privileged for every i≠0,k−1 exist if and only if . Their number is and they are permutations of the tracks (a,aζ,…,aζk−2) with and ζ∈Fq a primitive r-th root of unity.