Paper 2019/246

Towards optimal robust secret sharing with security against a rushing adversary

Serge Fehr and 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.