Paper 2019/361

On polynomial secret sharing schemes

Anat Paskin-Chernivasky and Artiom Radune

Abstract

Nearly all secret sharing schemes studied so far are linear or multi-linear schemes. Although these schemes allow to implement any monotone access structure, the share complexity may be suboptimal -- the gap between the best known lower bounds and best known upper bounds is exponential for some access structures. There is growing evidence in the literature, that non-linear 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, where shares are (multi-variate polynomials) of secret and randomness vectors over some finite field. Our main hope is that the nice algebraic structure of polynomials would help obtain better lower bounds than those known for the general setting, extending over the class of multi-linear schemes. Some of the concrete new results we prove in this work are as follows.\\ \textbf{On share complexity of polynomial schemes.}\\ First we studied degree 1 in randomness (where the degree of secret is unlimited). We have shown that a large subclass of these schemes are equivalent to multi-linear schemes, in the sense that for any such scheme, there exists an equivalent multi-linear scheme with very similar share complexity. Also, we have shown that the class of schemes of polynomials of degree exactly 2 in r, without degree 1 in r monomials, is very weak, and can implement only trivial access structures where the minterms consist of single parties.\\ Another observation 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 multi-linear scheme with similar share complexity per bit, for sufficiently long secrets. It is interesting to check, whether similar ideas could be applied to the recent improvement of Beimel et al. with share complexity $O(2^{0.862n})$ for general schemes, transforming it into a . \textbf{On the randomness complexity of polynomial schemes.}\\ We prove that for every degree 2 polynomial secret sharing scheme, there exists an equivalent degree-2 scheme with identical share complexity with randomness complexity bounded by $O(2^{2^n})$. For general polynomial secret sharing schemes, randomness complexity can be bounded by $SC^{O(SC)^2}$, where $SC$ is the share complexity of the original scheme. 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, and may be viewed as a proof of concept. One nice application of low (say polynomial) randomness complexity is transforming polynomial schemes with polynomial (in $n$) algebraic formulas $C(s,r)$, into a degree-3 scheme with only polynomial blowup in share complexity (using standard randomizing polynomials constructions).