Paper 2014/909

Robust Secret Sharing Schemes Against Local Adversaries

Allison Bishop Lewko and Valerio Pastro

Abstract

We study robust secret sharing schemes in which between one third and one half of the players are corrupted. In this scenario, robust secret sharing is possible only with a share size larger than the secrets, and allowing a positive probability of reconstructing the wrong secret. In the standard model, it is known that at least $m+k$ bits per share are needed to robustly share a secret of bit-length $m$ with an error probability of $2^{-k}$; however, to the best of our knowledge, the efficient scheme that gets closest to this lower bound has share size $m+\widetilde O (n+k)$, where $n$ is the number of players in the scheme. We show that it is possible to obtain schemes with close to minimal share size in a model of local adversaries, i.e. in which corrupt players cannot communicate between receiving their respective honest shares and submitting corrupted shares to the reconstruction procedure, but may coordinate before the execution of the protocol and can also gather information afterwards. In this limited adversarial model, we prove a lower bound of roughly $m+k$ bits on the minimal share size, which is (somewhat surprisingly) similar to the lower bound in the standard model, where much stronger adversaries are allowed. We then present an efficient secret sharing scheme that essentially meets our lower bound, therefore improving upon the best known constructions in the standard model by removing a linear dependence on the number of players. For our construction, we introduce a novel procedure that compiles an error correcting code into a new randomized one, with the following two properties: a single local portion of a codeword leaks no information on the encoded message itself, and any set of portions of a codeword reconstructs the message with error probability exponentially low in the set size.

Metadata
Available format(s)
PDF
Category
Foundations
Publication info
Preprint. MINOR revision.
Keywords
secret sharingmacserror-correcting codeslocal adversaries
Contact author(s)
valerio @ cs columbia edu
History
2015-02-11: revised
2014-11-05: received
See all versions
Short URL
https://ia.cr/2014/909
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2014/909,
      author = {Allison Bishop Lewko and Valerio Pastro},
      title = {Robust Secret Sharing Schemes Against Local Adversaries},
      howpublished = {Cryptology ePrint Archive, Paper 2014/909},
      year = {2014},
      note = {\url{https://eprint.iacr.org/2014/909}},
      url = {https://eprint.iacr.org/2014/909}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.