**Secret-Sharing from Robust Conditional Disclosure of Secrets**

*Amos Beimel and Naty Peter*

**Abstract: **A secret-sharing scheme is a method by which a dealer, holding a secret string, distributes shares to parties such that only authorized subsets of parties can reconstruct the secret.
The collection of authorized subsets is called an access structure.
Secret-sharing schemes are an important tool in cryptography and they are used as a building box in many secure
protocols.
In the original constructions of secret-sharing schemes by Ito et al. [Globecom 1987], the share size of each party is $\tilde{O}(2^{n})$ (where $n$ is the number of parties in the access structure).
New constructions of secret-sharing schemes followed; however, the share size in these schemes remains basically the same.
Although much efforts have been devoted to this problem, no progress was made for more than 30 years.
Recently, in a breakthrough paper, Liu and Vaikuntanathan [STOC 2018] constructed a secret-sharing scheme for a general access structure with share size $\tilde{O}(2^{0.994n})$.
The construction is based on new protocols for conditional disclosure of secrets (CDS).
This was improved by Applebaum et al. [EUROCRYPT 2019] to $\tilde{O}(2^{0.892n})$.

In this work, we construct improved secret-sharing schemes for a general access structure with share size $\tilde{O}(2^{0.762n})$. Our schemes are linear, that is, the shares are a linear function of the secret and some random elements from a finite field. Previously, the best linear secret-sharing scheme had shares of size $\tilde{O}(2^{0.942n})$. Most applications of secret-sharing require linearity. Our scheme is conceptually simpler than previous schemes, using a new reduction to two-party CDS protocols (previous schemes used a reduction to multi-party CDS protocols).

In a CDS protocol for a function $f$, there are $k$ parties and a referee; each party holds a private input and a common secret, and sends one message to the referee (without seeing the other messages). On one hand, if the function $f$ applied to the inputs returns $1$, then it is required that the referee, which knows the inputs, can reconstruct the secret from the messages. On the other hand, if the function $f$ applied to the inputs returns $0$, then the referee should get no information on the secret from the messages. However, if the referee gets two messages from a party, corresponding to two different inputs (as happens in our reduction from secret-sharing to CDS), then the referee might be able to reconstruct the secret although it should not.

To overcome this problem, we define and construct $t$-robust CDS protocols, where the referee cannot get any information on the secret when it gets $t$ messages for a set of zero-inputs of $f$. We show that if a function $f$ has a two-party CDS protocol with message size $c_f$, then it has a two-party $t$-robust CDS protocol with normalized message size $\tilde{O}(t c_f)$. Furthermore, we show that every function $f:[N] \times [N]\rightarrow \{0,1\}$ has a multi-linear $t$-robust CDS protocol with normalized message size $\tilde{O}(t+\sqrt{N})$. We use a variant of this protocol (with $t$ slightly larger than $\sqrt{N}$) to construct our improved linear secret-sharing schemes. Finally, we construct robust $k$-party CDS protocols for $k>2$.

**Category / Keywords: **cryptographic protocols / secret sharing

**Date: **received 18 May 2019

**Contact author: **naty at post bgu ac il

**Available format(s): **PDF | BibTeX Citation

**Version: **20190520:203115 (All versions of this report)

**Short URL: **ia.cr/2019/522

[ Cryptology ePrint archive ]