Nearly optimal robust secret sharing

Nearly optimal robust secret sharing. Cheraghchi, M. Designs, Codes and Cryptography, 87(8):1777–1796, 2019. Preliminary version in Proceedings of ISIT 2016.

Link

Paper doi abstract bibtex

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 $δ n$, for any constant $δ ∈ (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 a fully explicit 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(κ)$, where $k$ is the secret length and $κ$ is the security parameter. Like Shamir's scheme, in this modified scheme any set of more than $δ n$ honest parties can efficiently recover the secret. Using algebraic geometry codes instead of Reed-Solomon codes, the share length can be decreased to a constant (only depending on $δ$) 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 $δ n(1+ρ)$ honest parties, for arbitrarily small $ρ > 0$, can efficiently reconstruct the secret.

@ARTICLE{ref:Che19:SS,
  author =	 {Mahdi Cheraghchi},
  title =	 {Nearly optimal robust secret sharing},
  journal =	 {Designs, Codes and Cryptography},
  volume =	 87,
  number =	 8,
  pages =	 {1777--1796},
  year =	 2019,
  doi =		 {10.1007/s10623-018-0578-y},
  url_Link =
                  {https://link.springer.com/article/10.1007/s10623-018-0578-y},
  keywords =	 {Coding and information theory, Cryptography,
                  Algebraic coding theory},
  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 a fully explicit 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, the share length can be
                  decreased 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.},
  note =	 {Preliminary version in Proceedings of {ISIT 2016.}},
  url_Paper =	 {https://eprint.iacr.org/2015/951}
}

Downloads: 0