Evolving secret sharing revisited: computational security and succinctness

Abstract Evolving secret sharing (Komargodski, Naor, and Yogev, TCC’16) generalizes the notion of secret sharing to the setting of evolving access structures , in which the share holders are added to the system in an online manner, and where the dealer does not know neither the access structure nor the maximum psnber of parties in advance. Here, the main difficulty is to distribute shares to the new players without updating the shares of old players; moreover, one would like to minimize the share size as a function of the psnber of players. In this paper, we initiate a systematic study of evolving secret sharing in the computational setting , where the maximum psnber of parties is polynomial in the security parameter, but the dealer still does not know this value, neither it knows the access structure in advance. Moreover, the privacy guarantee only holds against computationally bounded adversaries corrupting an unauthorized subset of the players. Our main result is that for many interesting, and practically relevant, evolving access structures, under standard hardness assumptions, there exist efficient secret sharing schemes with computational privacy and in which the shares are succinct (i.e., much smaller compared to the size of a natural computational representation of the evolving access structure). These access structures include evolving graphs access structures, threshold access structures, and monotone circuits/DNF/CNF access structures meeting an additional rigidity property that we show to be necessary if one wants to avoid updating the shares of old parties.