Cryptology ePrint Archive: Report 2019/1429

Secret Sharing Schemes : A Fine Grained Analysis

Shion Samadder Chaudhury and 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.

Category / Keywords: foundations / Secret Sharing, Circuit Complexity, Randomized Decision Tree , Share Redistribution, Boolean Functions

Date: received 8 Dec 2019, last revised 8 Dec 2019, withdrawn 9 Feb 2020

Contact author: chaudhury shion at gmail com,saby math@gmail com,sakurai@inf kyushu-u ac jp

Available format(s): (-- withdrawn --)

Version: 20200210:045421 (All versions of this report)

Short URL:

[ Cryptology ePrint archive ]