Paper 2015/951

Nearly Optimal Robust Secret Sharing

Mahdi Cheraghchi

Abstract

We prove that a known approach to improve Shamir's celebrated secret sharing scheme; i.e., adding an information-theoretic authentication tag to the secret, can make it robust for $n$ parties against any collusion of size $\delta n$, for any constant $\delta \in (0, 1/2)$. This result holds in the so-called "non-rushing" model in which the $n$ shares are submitted simultaneously for reconstruction. We thus obtain an efficient and robust secret sharing scheme in this model that is essentially optimal in all parameters including the share size which is $k(1+o(1)) + O(\kappa)$, where $k$ is the secret length and $\kappa$ is the security parameter. Like Shamir's scheme, in this modified scheme any set of more than $\delta n$ honest parties can efficiently recover the secret. Using algebraic geometry codes instead of Reed-Solomon codes, we decrease the share length to a constant (only depending on $\delta$) while the number of shares $n$ can grow independently. In this case, when $n$ is large enough, the scheme satisfies the "threshold" requirement in an approximate sense; i.e., any set of $\delta n(1+\rho)$ honest parties, for arbitrarily small $\rho > 0$, can efficiently reconstruct the secret.

Metadata
Available format(s)
PDF
Category
Foundations
Publication info
Preprint. MINOR revision.
Keywords
secret sharinginformation theoretic privacy
Contact author(s)
cheraghchi @ gmail com
History
2015-10-05: revised
2015-09-30: received
See all versions
Short URL
https://ia.cr/2015/951
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2015/951,
      author = {Mahdi Cheraghchi},
      title = {Nearly Optimal Robust Secret Sharing},
      howpublished = {Cryptology ePrint Archive, Paper 2015/951},
      year = {2015},
      note = {\url{https://eprint.iacr.org/2015/951}},
      url = {https://eprint.iacr.org/2015/951}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.