Paper 2020/080

Better Secret-Sharing via Robust Conditional Disclosure of Secrets

Benny Applebaum, Tel Aviv University
Amos Beimel, Ben Gurion University
Oded Nir, Tel Aviv University
Naty Peter

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 $2^{n-o(n)}$ and until recently no better scheme was known. In a recent breakthrough, Liu and Vaikuntanathan (STOC 2018) have reduced the share size to $2^{0.994n+o(n)}$, which was later improved to $2^{0.892n+o(n)}$ by Applebaum et al. (EUROCRYPT 2019). In this paper we improve the exponent of general secret-sharing schemes down to $0.637$. For the special case of linear secret-sharing schemes, we get an exponent of $0.762$ (compared to $0.942$ 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.

Available format(s)
Cryptographic protocols
Publication info
Published elsewhere. Minor revision. STOC 2020
secret-sharing schemesconditional disclosure of secrets protocols
Contact author(s)
benny applebaum @ gmail com
amos beimel @ gmail com
odednir123 @ gmail com
naty @ post bgu ac il
2023-09-05: last of 2 revisions
2020-01-28: received
See all versions
Short URL
Creative Commons Attribution


      author = {Benny Applebaum and Amos Beimel and Oded Nir and Naty Peter},
      title = {Better Secret-Sharing via Robust Conditional Disclosure of Secrets},
      howpublished = {Cryptology ePrint Archive, Paper 2020/080},
      year = {2020},
      doi = {10.1145/3357713.3384293},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.