Paper 2020/080

Better Secret-Sharing via Robust Conditional Disclosure of Secrets

Abstract

A secret-sharing scheme allows to distribute a secret $s$ among $n$ parties such that only some predefined ``authorized'' sets of parties can reconstruct the secret, and all other ``unauthorized'' sets learn nothing about $s$. For over 30 years, it was known that any (monotone) collection of authorized sets can be realized by a secret-sharing scheme whose shares are of size $$ and until recently no better scheme was known. In a recent breakthrough, Liu and Vaikuntanathan (STOC 2018) have reduced the share size to $$, which was later improved to $$ by Applebaum et al. (EUROCRYPT 2019). In this paper we improve the exponent of general secret-sharing schemes down to $$. For the special case of linear secret-sharing schemes, we get an exponent of $$ (compared to $$ of Applebaum et al.). As our main building block, we introduce a new \emph{robust} variant of conditional disclosure of secrets (robust CDS) that achieves unconditional security even under bounded form of re-usability. We show that the problem of general secret-sharing schemes reduces to robust CDS protocols with sub-exponential overhead and derive our main result by implementing robust CDS with a non-trivial exponent. The latter construction follows by presenting a general immunization procedure that turns standard CDS into a robust CDS.