Paper 2019/522
SecretSharing from Robust Conditional Disclosure of Secrets
Amos Beimel and Naty Peter
Abstract
A secretsharing 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. Secretsharing schemes are an important tool in cryptography and they are used as a building box in many secure protocols. In the original constructions of secretsharing 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 secretsharing 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 secretsharing 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 secretsharing 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 secretsharing scheme had shares of size $\tilde{O}(2^{0.942n})$. Most applications of secretsharing require linearity. Our scheme is conceptually simpler than previous schemes, using a new reduction to twoparty CDS protocols (previous schemes used a reduction to multiparty 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 secretsharing 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 zeroinputs of $f$. We show that if a function $f$ has a twoparty CDS protocol with message size $c_f$, then it has a twoparty $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 multilinear $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 secretsharing schemes. Finally, we construct robust $k$party CDS protocols for $k>2$.
Metadata
 Available format(s)
 Category
 Cryptographic protocols
 Publication info
 Preprint. MINOR revision.
 Keywords
 secret sharing
 Contact author(s)
 naty @ post bgu ac il
 History
 20190520: received
 Short URL
 https://ia.cr/2019/522
 License

CC BY
BibTeX
@misc{cryptoeprint:2019/522, author = {Amos Beimel and Naty Peter}, title = {SecretSharing from Robust Conditional Disclosure of Secrets}, howpublished = {Cryptology ePrint Archive, Paper 2019/522}, year = {2019}, note = {\url{https://eprint.iacr.org/2019/522}}, url = {https://eprint.iacr.org/2019/522} }