International Association for Cryptologic Research

International Association
for Cryptologic Research

CryptoDB

Paper: Towards Optimal Robust Secret Sharing with Security Against a Rushing Adversary

Authors:
Serge Fehr
Chen Yuan
Download:
DOI: 10.1007/978-3-030-17659-4_16
Search ePrint
Search Google
Abstract: Robust secret sharing enables the reconstruction of a secret-shared message in the presence of up to t (out of n) incorrect shares. The most challenging case is when $$n = 2t+1$$, which is the largest t for which the task is still possible, up to a small error probability $$2^{-\kappa }$$ and with some overhead in the share size.Recently, Bishop, Pastro, Rajaraman and Wichs [3] proposed a scheme with an (almost) optimal overhead of $$\widetilde{O}(\kappa )$$. This seems to answer the open question posed by Cevallos et al. [6] who proposed a scheme with overhead of $$\widetilde{O}(n+\kappa )$$ and asked whether the linear dependency on n was necessary or not. However, a subtle issue with Bishop et al.’s solution is that it (implicitly) assumes a non-rushing adversary, and thus it satisfies a weaker notion of security compared to the scheme by Cevallos et al. [6], or to the classical scheme by Rabin and BenOr [13].In this work, we almost close this gap. We propose a new robust secret sharing scheme that offers full security against a rushing adversary, and that has an overhead of $$O(\kappa n^\varepsilon )$$, where $$\varepsilon > 0$$ is arbitrary but fixed. This $$n^\varepsilon $$-factor is obviously worse than the $$\mathrm {polylog}(n)$$-factor hidden in the $$\widetilde{O}$$ notation of the scheme of Bishop et al. [3], but it greatly improves on the linear dependency on n of the best known scheme that features security against a rushing adversary (when $$\kappa $$ is substantially smaller than n).A small variation of our scheme has the same $$\widetilde{O}(\kappa )$$ overhead as the scheme of Bishop et al. and achieves security against a rushing adversary, but suffers from a (slightly) superpolynomial reconstruction complexity.
Video from EUROCRYPT 2019
Video provided under Creative Commons / CC BY 3.0
BibTeX
@article{eurocrypt-2019-29394,
  title={Towards Optimal Robust Secret Sharing with Security Against a Rushing Adversary},
  booktitle={Advances in Cryptology – EUROCRYPT 2019},
  series={Advances in Cryptology – EUROCRYPT 2019},
  publisher={Springer},
  volume={11478},
  pages={472-499},
  doi={10.1007/978-3-030-17659-4_16},
  author={Serge Fehr and Chen Yuan},
  year=2019
}