Paper 2019/522
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 (where 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 .
The construction is based on new protocols for conditional disclosure of secrets (CDS).
This was improved by Applebaum et al. [EUROCRYPT 2019] to .
In this work, we construct improved secret-sharing schemes for a general access structure with share size .
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 .
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 , there are 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 applied to the inputs returns , 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 applied to the inputs returns , 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 -robust CDS protocols, where the referee cannot get any information on the secret when it gets messages for a set of zero-inputs of .
We show that if a function has a two-party CDS protocol with message size , then it has a two-party -robust CDS protocol with normalized message size .
Furthermore, we show that every function has a multi-linear -robust CDS protocol with normalized message size .
We use a variant of this protocol (with slightly larger than ) to construct our improved linear secret-sharing schemes.
Finally, we construct robust -party CDS protocols for .