Anzeige
Erschienen in:
2019 | OriginalPaper | Buchkapitel
Towards Optimal Robust Secret Sharing with Security Against a Rushing Adversary
verfasst von : Serge Fehr, Chen Yuan
Erschienen in: Advances in Cryptology – EUROCRYPT 2019
Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. powered by
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.