Communication Efficient Secret Sharing in the Presence of Malicious Adversary
Preprint
Abstract
Consider the communication efficient secret sharing problem. A dealer wants to share a secret with $n$ parties such that any $k\leq n$ parties can reconstruct the secret and any $z<k$ parties eavesdropping on their shares obtain no information about the secret. In addition, a legitimate user contacting any $d$, $k\leq d \leq n$, parties to decode the secret can do so by reading and downloading the minimum amount of information needed. We are interested in communication efficient secret sharing schemes that tolerate the presence of malicious parties actively corrupting their shares and the data delivered to the users. The knowledge of the malicious parties about the secret is restricted to the shares they obtain. We characterize the capacity, i.e. maximum size of the secret that can be shared. We derive the minimum amount of information needed to to be read and communicated to a legitimate user to decode the secret from $d$ parties, $k\leq d \leq n$. Error-correcting codes do not achieve capacity in this setting. We construct codes that achieve capacity and achieve minimum read and communication costs for all possible values of $d$. Our codes are based on Staircase codes, previously introduced for communication efficient secret sharing, and on the use of a pairwise hashing scheme used in distributed data storage and network coding settings to detect errors inserted by a limited knowledge adversary.
Keywords
All Related Versions
This publication has 9 references indexed in Scilit:
- Staircase Codes for Secret Sharing With Optimal Communication and Read OverheadsIEEE Transactions on Information Theory, 2017
- Communication Efficient Secret SharingIEEE Transactions on Information Theory, 2016
- Network Codes Resilient to Jamming and EavesdroppingIEEE/ACM Transactions on Networking, 2014
- The tail at scaleCommunications of the ACM, 2013
- Threshold changeable secret sharing schemes revisitedTheoretical Computer Science, 2012
- Securing Dynamic Distributed Storage Systems Against Eavesdropping and Adversarial AttacksIEEE Transactions on Information Theory, 2011
- Network Coding for Distributed Storage SystemsIEEE Transactions on Information Theory, 2010
- On Secret Reconstruction in Secret Sharing SchemesIEEE Transactions on Information Theory, 2008
- On sharing secrets and Reed-Solomon codesCommunications of the ACM, 1981