Paper 2015/1032

Essentially Optimal Robust Secret Sharing with Maximal Corruptions

Allison Bishop, Valerio Pastro, Rajmohan Rajaraman, and Daniel Wichs

Abstract

In a $t$-out-of-$n$ robust secret sharing scheme, a secret message is shared among $n$ parties who can reconstruct the message by combining their shares. An adversary can adaptively corrupt up to $t$ of the parties, get their shares, and modify them arbitrarily. The scheme should satisfy privacy, meaning that the adversary cannot learn anything about the shared message, and robustness, meaning that the adversary cannot cause the reconstruction procedure to output an incorrect message. Such schemes are only possible in the case of an honest majority, and here we focus on unconditional security in the maximal corruption setting where $n = 2t+1$. In this scenario, to share an $m$-bit message with a reconstruction failure probability of at most $2^{-k}$, a known lower-bound shows that the share size must be at least $m + k$ bits. On the other hand, all prior constructions have share size that scales linearly with the number of parties $n$, and the prior state-of-the-art scheme due to Cevallos et al. (EUROCRYPT '12) achieves $m + \widetilde{O}(k + n)$. In this work, we construct the first robust secret sharing scheme in the maximal corruption setting with $n=2t+1$, that avoids the linear dependence between share size and the number of parties $n$. In particular, we get a share size of only $m + \widetilde{O}(k)$ bits. Our scheme is computationally efficient and relies on approximation algorithms for the minimum graph bisection problem.

Metadata
Available format(s)
PDF
Category
Foundations
Publication info
Preprint. MINOR revision.
Keywords
Secret SharingInformation Theoretic Security
Contact author(s)
wichs @ cs neu edu
History
2015-11-05: revised
2015-10-26: received
See all versions
Short URL
https://ia.cr/2015/1032
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2015/1032,
      author = {Allison Bishop and Valerio Pastro and Rajmohan Rajaraman and Daniel Wichs},
      title = {Essentially Optimal Robust Secret Sharing with Maximal Corruptions},
      howpublished = {Cryptology ePrint Archive, Paper 2015/1032},
      year = {2015},
      note = {\url{https://eprint.iacr.org/2015/1032}},
      url = {https://eprint.iacr.org/2015/1032}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.