Paper 2019/1429

Secret Sharing Schemes : A Fine Grained Analysis

Shion Samadder Chaudhury, Sabyasachi Dutta, and Kouichi Sakurai

Abstract

In this paper we prove that embedding parity bits and other function outputs in share string enables us to construct a secret sharing scheme (over binary alphabet) robust against a resource bounded adversary. Constructing schemes robust against adversaries in higher complexity classes requires an increase in the share size and increased storage. By connecting secret sharing with the randomized decision tree of a Boolean function we construct a scheme which is robust against an infinitely powerful adversary while keeping the constructions in a very low complexity class, viz. $AC^0$. As an application, we construct a robust secret sharing scheme in $AC^0$ that can accommodate new participants (dynamically) over time. Our construction requires a new redistribution of secret shares and can accommodate a bounded number of new participants.

Metadata
Available format(s)
-- withdrawn --
Category
Foundations
Publication info
Preprint.
Keywords
Secret SharingCircuit ComplexityRandomized Decision TreeShare RedistributionBoolean Functions
Contact author(s)
chaudhury shion @ gmail com
saby math @ gmail com
sakurai @ inf kyushu-u ac jp
History
2020-02-10: withdrawn
2019-12-10: received
See all versions
Short URL
https://ia.cr/2019/1429
License
Creative Commons Attribution
CC BY
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.