Constructions and Lower Bounds for Evolving Two-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 <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"> <tex-math notation="LaTeX">$(2,\infty)$ </tex-math></inline-formula>-threshold secret sharing schemes. The cost of a <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"> <tex-math notation="LaTeX">$(2,\infty)$ </tex-math></inline-formula>-threshold secret sharing scheme can be measured as the maximum, over all possible <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"> <tex-math notation="LaTeX">$n\ge 2$ </tex-math></inline-formula>, 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 <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"> <tex-math notation="LaTeX">$(2,n)$ </tex-math></inline-formula>-threshold secret sharing scheme. It is known that such a cost measure is lower bounded by <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"> <tex-math notation="LaTeX">$3/2$ </tex-math></inline-formula>. Moreover, currently, the best known <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"> <tex-math notation="LaTeX">$(2,\infty)$ </tex-math></inline-formula>-threshold secret sharing scheme has cost 1.59375. Our contribution improves the state-of-the-art in several ways:•We describe a new <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"> <tex-math notation="LaTeX">$(2,\infty)$ </tex-math></inline-formula>-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 <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"> <tex-math notation="LaTeX">$n\ge z_{0}$ </tex-math></inline-formula>, where <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"> <tex-math notation="LaTeX">$z_{0}$ </tex-math></inline-formula> 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 <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"> <tex-math notation="LaTeX">$3/2$ </tex-math></inline-formula>. We close the paper summarizing our findings and discussing some open issues.