Nearly Optimal Robust Secret Sharing against Rushing Adversaries

Robust secret sharing is a strengthening of secret sharing which allows the 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. It is known that in this setting, to recover a secret of length m bits with error less than 2^-lambda, shares of size at least m + lambda bits are needed. Recently, Bishop, Pastro, Rajaraman, and Wichs (EUROCRYPT 2016) gave a construction with shares of size m + O(lambda * polylog(n, m, lambda)) bits that is secure against non-rushing adversaries. Later, Fehr and Yuan (EUROCRYPT 2019) constructed a scheme that is secure against rushing adversaries, and has shares of size m + O(lambda * n^epsilon * polylog(n, m, lambda)) bits for an arbitrary constant epsilon > 0. They also showed a variant of their construction with share size m + O(lambda * polylog(n, m, lambda)) 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(lambda * log n * (log n + log m)) bits, and polynomial-time sharing and reconstruction. Central to our construction is an 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.

• Algorithms and Theory

• Security, Privacy and Abuse Prevention