Constructions and lower bounds for evolving 2-threshold secret sharing schemes

In this paper we consider evolving 2-threshold secret sharing schemes. In such schemes, the number of participants grows over time and is potentially unbounded, any two participants reconstruct the secret, and no single participant can figure out any partial information about it. They are referred to as (2,∞)-threshold secret sharing schemes. The cost of a (2,∞)-threshold secret sharing scheme can be measured as the maximum, over all possible n ≥ 2, of the ratio between the sum of the lengths of the shares for the first n participants and the sum of the lengths of the shares for a (standard) optimal (2, n)-threshold secret sharing scheme. It is known that such a cost measure is lower bounded by 3/2. Moreover, currently, the best known (2,∞)-threshold secret sharing scheme has cost 1.59375. Our contribution improves the state-of-the-art in several ways: • We describe a new (2,∞)-threshold secret sharing scheme whose cost is 1.5859375, improving on the previous best known scheme. • Motivated by the fact that in some applications one knows a lower bound on the number of participants, we generalize the cost measure, by considering the maximum over all possible n ≥ z0, where z0 is any integer greater than or equal to 2. • We provide constructions of optimal schemes for the generalized cost measure and through a theoretical analysis we prove some interesting properties for the lower bound of the cost. • By using algorithmic techniques, for reasonably small cases, we exhaustively study the problem of finding tight lower bounds. In particular, we obtain a lower bound of 1.534375, improving the lower bound of 3/2. We close the paper summarizing our findings and discussing some open issues.