Paper 2023/129 Original: eprint.iacr.org/2023/129 ↗

A Lower Bound on the Share Size in Evolving Secret Sharing

Abstract

Secret sharing schemes allow sharing a secret between a set of parties in a way that ensures that only authorized subsets of the parties learn the secret. Evolving secret sharing schemes (Komargodski, Naor, and Yogev [TCC ’16]) allow achieving this end in a scenario where the parties arrive in an online fashion, and there is no a-priory bound on the number of parties. An important complexity measure of a secret sharing scheme is the share size, which is the maximum number of bits that a party may receive as a share. While there has been a significant progress in recent years, the best constructions for both secret sharing and evolving secret sharing schemes have a share size that is exponential in the number of parties. On the other hand, the best lower bound, by Csirmaz [Eurocrypt ’95], is sub-linear. In this work, we give a tight lower bound on the share size of evolving secret sharing schemes. Specifically, we show that the sub-linear lower bound of Csirmaz implies an exponential lower bound on evolving secret sharing.