Towards optimal robust secret sharing with security against a rushing adversary

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 -κ and with some overhead in the share size. Recently, Bishop, Pastro, Rajaraman and Wichs [3] proposed a scheme with an (almost) optimal overhead of Õ(k). This seems to answer the open question posed by Cevallos et al. [6] who proposed a scheme with overhead of Õ(n+κ) 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(κn ε ), where ε>0 is arbitrary but fixed. This n ε -factor is obviously worse than the polylog (n) -factor hidden in the Õ 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 κ is substantially smaller than n). A small variation of our scheme has the same Õ(κ) overhead as the scheme of Bishop et al. and achieves security against a rushing adversary, but suffers from a (slightly) superpolynomial reconstruction complexity.

• View at Publisher
• View at Scopus

Free Full Text ( Final Version , 455kb )