You are looking at a specific version 20200623:030731 of this paper. See the latest version.

Paper 2019/1131

Nearly Optimal Robust Secret Sharing against Rushing Adversaries

Pasin Manurangsi and Akshayaram Srinivasan and Prashant Nalini Vasudevan

Abstract

Robust secret sharing is a strengthening of standard secret sharing that allows the shared secret to be recovered even if some of the shares being used in the reconstruction have been adversarially modified. In this work, we study the setting where out of all the $n$ shares, the adversary is allowed to adaptively corrupt and modify $t$ shares, where $n = 2t+1$. Further, we deal with \textit{rushing} adversaries, meaning that the adversary is allowed to see the honest parties' shares before modifying its own shares. It is known that when $n = 2t+1$, to share a secret of length $m$ bits and recover it with error less than $2^{-\sec}$, shares of size at least $m+\sec$ bits are needed. Recently, Bishop, Pastro, Rajaraman, and Wichs (EUROCRYPT 2016) constructed a robust secret sharing scheme with shares of size $m + O(\sec\cdot\textrm{polylog}(n,m,\sec))$ bits that is secure in this setting against non-rushing adversaries. Later, Fehr and Yuan (EUROCRYPT 2019) constructed a scheme that is secure against rushing adversaries, but has shares of size $m + O(\sec\cdot n^{\epsilon}\cdot \textrm{polylog}(n,m,\sec))$ bits for an arbitrary constant $\epsilon > 0$. They also showed a variant of their construction with share size $m + O(\sec\cdot\textrm{polylog}(n,m,\sec))$ bits, but with super-polynomial reconstruction time. We present a robust secret sharing scheme that is secure against rushing adversaries, has shares of size $m+O(\sec \log{n} (\log{n}+\log{m}))$ bits, and has polynomial-time sharing and reconstruction. Central to our construction is a polynomial-time algorithm for a problem on semi-random graphs that arises naturally in the paradigm of local authentication of shares used by us and in the aforementioned work.

Metadata
Available format(s)
PDF
Category
Foundations
Publication info
A minor revision of an IACR publication in CRYPTO 2020
Contact author(s)
akshayaram @ berkeley edu
History
2020-06-23: last of 2 revisions
2019-10-02: received
See all versions
Short URL
https://ia.cr/2019/1131
License
Creative Commons Attribution
CC BY
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.