Paper 2019/361
On polynomial secret sharing schemes
Anat PaskinChernivasky and Artiom Radune
Abstract
Nearly all secret sharing schemes studied so far are linear or multilinear schemes. Although these schemes allow to implement any monotone access structure, the share complexity, $SC$, may be suboptimal  there are access structures for which the gap between the best known lower bounds and best known multilinear schemes is exponential. There is growing evidence in the literature, that nonlinear schemes can improve share complexity for some access structures, with the work of Beimel and Ishai (CCC '01) being among the first to demonstrate it. This motivates further study of non linear schemes. We initiate a systematic study of polynomial secret sharing schemes (PSSS), where shares are (multivariate) polynomials of secret and randomness vectors $\vec{s},\vec{r}$ respectively over some finite field $\F_q$. Our main hope is that the algebraic structure of polynomials would help obtain better lower bounds than those known for the general secret sharing. Some of the initial results we prove in this work are as follows. \textbf{On share complexity of polynomial schemes.}\\ First we study degree (at most) 1 in randomness variables $\vec{r}$ (where the degree of secret variables is unlimited). We have shown that for a large subclass of these schemes, there exist equivalent multilinear schemes with $O(n)$ share complexity overhead. Namely, PSSS where every polynomial misses monomials of exact degree $c\geq 2$ in $\vec{s}$ and 0 in $\vec{r}$, and PSSS where all polynomials miss monomials of exact degree $\geq 1$ in $\vec{s}$ and 1 in $\vec{r}$. This translates the known lower bound of $\Omega(n^{\log(n)})$ for multi linear schemes onto a class of schemes strictly larger than multi linear schemes, to contrast with the best $\Omega(n^2/\log(n))$ bound known for general schemes, with no progress since 94'. An observation in the positive direction we make refers to the share complexity (per bit) of multi linear schemes (polynomial schemes of total degree 1). We observe that the scheme by Liu et. al obtaining share complexity $O(2^{0.994n})$ can be transformed into a multilinear scheme with similar share complexity per bit, for sufficiently long secrets. % For the next natural degree to consider, 2 in $\vec{r}$, we have shown that PSSS where all share polynomials are of exact degree 2 in $\vec{r}$ (without exact degree 1 in $\vec{r}$ monomials) where $\F_q$ has odd characteristic, can implement only trivial access structures where the minterms consist of single parties. Obtaining improved lower bounds for degree2 in $\vec{r}$ PSSS, and even arbitrary degree1 in $\vec{r}$ PSSS is left as an interesting open question. \textbf{On the randomness complexity of polynomial schemes.}\\ We prove that for every degree2 polynomial secret sharing scheme, there exists an equivalent degree2 scheme with identical share complexity with randomness complexity, $RC$, bounded by $2^{poly(SC)}$. For general PSSS, we obtain a similar bound on $RC$ (preserving $SC$ and $\F_q$ but not degree). So far, bounds on randomness complexity were known only for multi linear schemes, demonstrating that $RC \leq SC$ is always achievable. Our bounds are not nearly as practical as those for multilinear schemes, and should be viewed as a proof of concept. If a much better bound for some degree bound $d=O(1)$ is obtained, it would lead directly to superpolynomial countingbased lower bounds for degree$d$ PSSS over constantsized fields. Another application of low (say, polynomial) randomness complexity is transforming polynomial schemes with polynomialsized (in $n$) algebraic formulas $C(\vec{s},\vec{r})$ for each share , into a degree3 scheme with only polynomial blowup in share complexity, using standard randomizing polynomials constructions.
Note: We revised and added details in many of the proofs. Note that the account of previous work is not up to date, and stops around early 2019.
Metadata
 Available format(s)
 Category
 Foundations
 Publication info
 Published elsewhere. Minor revision. ITC 2020
 Keywords
 secret sharing schemespolynomialsshare complexityrandomness complexity
 Contact author(s)

anps83 @ gmail com
tom radune @ gmail com  History
 20200616: last of 2 revisions
 20190410: received
 See all versions
 Short URL
 https://ia.cr/2019/361
 License

CC BY
BibTeX
@misc{cryptoeprint:2019/361, author = {Anat PaskinChernivasky and Artiom Radune}, title = {On polynomial secret sharing schemes}, howpublished = {Cryptology ePrint Archive, Paper 2019/361}, year = {2019}, note = {\url{https://eprint.iacr.org/2019/361}}, url = {https://eprint.iacr.org/2019/361} }