Threshold Changeable Ramp Secret Sharing

Threshold changeable secret sharing studies the problem of changing the thresholds of a secret sharing scheme after the shares of the initial scheme have been distributed to players. We focus on the most studied scenario of dealer-free threshold increase in the absence of secure channels with an outsider adversary. Previous theoretical works in this scenario only consider an unchanged privacy threshold and define optimal threshold changeable secret sharing schemes as ones meeting the bounds in this case. We highlight increasing the privacy threshold as an independent design goal on top of increasing the reconstruction threshold. We prove new bounds for the above threshold increase scenario with respect to a new privacy threshold that is possibly bigger than the initial privacy threshold. We similarly define an optimal threshold changeable secret sharing scheme as one that achieves equality in all these bounds. A trade-off between the new privacy threshold and the required combiner communication complexity is discovered and new optimal schemes for the case when privacy threshold also increases are identified. These theoretical results put our new construction of threshold changeable secret sharing on a firm ground. Our threshold changeable ramp scheme does not need a priori knowledge of the targeted thresholds to design the protocol and allow the conversion into a ramp scheme with arbitrary new reconstruction thresholds while the privacy threshold grows proportionally as the reconstruction threshold grows. Previous such schemes were only known from lattice-based constructions that use a non-standard privacy definition. Our new schemes are statistical secret sharing schemes that guarantee indistinguishability of shares up to the new privacy threshold.