Welcome to the resource topic for 2019/246
Title:
Towards optimal robust secret sharing with security against a rushing adversary
Authors: Serge Fehr, Chen Yuan
Abstract:Robust secret sharing enables the reconstruction of a secret-shared message in the presence of up to t (out of n) {\em incorrect} shares. The most challenging case is when n = 2t+1, which is the largest t for which the task is still possible, but only up to a small error probability 2^{- \kappa} and with some overhead in the share size. Recently, Bishop, Pastro, Rajaraman and Wichs proposed a scheme with an (almost) optimal overhead of \widetilde{O}(\kappa). This seems to answer the open question posed by Cevallos et al. 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 {\em non-rushing} adversary, and thus it satisfies a {\em weaker} notion of security compared to the scheme by Cevallos et al. or to the classical scheme by Rabin and BenOr. 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., but it greatly improves on the linear dependency on n of the best known scheme that features security against a rushing adversary. A small variation of our scheme has the same \widetilde{O}(\kappa) overhead as the scheme of Bishop et al.\ {\em and} achieves security against a rushing adversary, but suffers from a (slightly) superpolynomial reconstruction complexity.
ePrint: https://eprint.iacr.org/2019/246
Talk: https://www.youtube.com/watch?v=g47XAFEd5M8
See all topics related to this paper.
Feel free to post resources that are related to this paper below.
Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.
For more information, see the rules for Resource Topics .