Welcome to the resource topic for 2019/522
Title:
Secret-Sharing from Robust Conditional Disclosure of Secrets
Authors: Amos Beimel, 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.
ePrint: https://eprint.iacr.org/2019/522
See all topics related to this paper.
Feel free to post resources that are related to this paper below.
Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.
For more information, see the rules for Resource Topics .