Paper 2019/1428

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

Shion Samadder Chaudhury, Sabyasachi Dutta, and Kouichi Sakurai


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.

Available format(s)
-- withdrawn --
Publication info
Preprint. MINOR revision.
Robust Secret SharingCircuit ComplexityShare RedistributionEvolving Access Structure
Contact author(s)
chaudhury shion @ gmail com
saby math @ gmail com
sakurai @ inf kyushu-u ac jp
2020-02-12: withdrawn
2019-12-10: received
See all versions
Short URL
Creative Commons Attribution
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.