Paper 2019/1428

$AC^0$ Constructions for Evolving Secret Sharing Schemes and Redistribution of Secret Shares

Shion Samadder Chaudhury, Sabyasachi Dutta, and Kouichi Sakurai

Abstract

Classical secret sharing schemes are built on the assumptions that the number of participants and the access structure remain fixed over time. Evolving secret sharing addresses the question of accommodating new participants with changeable access structures. One goal of this article is to initiate the study of evolving secret sharing sharing such that both share generation and reconstruction algorithms can be implemented by $AC^0$ circuits. We give a concrete construction with some minor storage assumption. Furthermore, allowing certain trade-offs we consider the novel problem of robust redistribution of secret shares (in $AC^0$) in the spirit of dynamic access structure by suitably modifying a construction of Cheng-Ishai-Li (TCC $2017$). A naive solution to the problem is to increase the alphabet size. We avoid this by modifying shares of some of the old participants. This modification is also necessary to make newly added participant(s) non-redundant to the secret sharing scheme.