Paper 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.
Metadata
- Available format(s)
-
PDF
- Category
- Foundations
- Publication info
- Preprint.
- Keywords
- Secret sharingEvolving secret sharing
- Contact author(s)
- noammaz @ gmail com
- History
- 2023-02-28: revised
- 2023-02-03: received
- See all versions
- Short URL
- https://ia.cr/2023/129
- License
-
CC BY
BibTeX
@misc{cryptoeprint:2023/129,
author = {Noam Mazor},
title = {A Lower Bound on the Share Size in Evolving Secret Sharing},
howpublished = {Cryptology ePrint Archive, Paper 2023/129},
year = {2023},
note = {\url{https://eprint.iacr.org/2023/129}},
url = {https://eprint.iacr.org/2023/129}
}
