Paper 2016/1088

How to infinitely share a secret more efficiently

Anat Paskin-Cherniavsky

Abstract

We device a general secret sharing scheme for evolving access structures (following [KNY16]). Our scheme has (sub)exponentially smaller share complexity (share of $i$'th party) for certain access structures compared to the general scheme in ~\cite{KNY16}. We stress that unlike ~\cite{KNY16}'s scheme, our scheme requires that the entire evolving access structure is known in advance. Revising, ~\cite{KNY16}'s scheme (in its most optimized form) is based on a representation of the access structure by an ordered (possibly infinite) oblivious, read once decision tree. Each node is associated with an output of the function (0 or 1). The tree is augmented to cut paths that reach a node where $f$ evaluates to 1 at that node (works for evolving access structures, in which the descendants of all 1-nodes must be 1). Each party $P_i$ receives a (single-bit) share for each edge exiting a node labeled by $x_i$. Generally, the scheme of ~\cite{KNY16} has share complexity $O(w_T(i))$, where $w_T(i)$ is the width of layer $i$ relevant decision tree. In general, this width can reach $\Omega(2^i)$. To get non trivial share complexity, $e^{n^{o(1)}}$, a \emph{tree} of width $e^{n^{o(1)}}$ is required. Our scheme is based on a generalized (infinite) tree representation of the access structure. The main difference is that vertices are labeled with sequences of variables, rather than a single variable. As a result, we often get smaller trees, and the edges $e$ are labeled by more complex (non-evloving) monotone functions $g_e$ of the variables in the sequence. The share associated with the edge is shared (among the parties in the relevant sequence). As a result, the tree is smaller, while the shares received for every edge in it are bigger. Still, the tradeoff is often on our side. Namely, for access structures with ordered read-once \emph{branching programs} with relatively small width, $e^{O(i^c)}$ for $c<0.25$, share complexity of $e^{n^{o(1)}}$ is achieved. More specifically, the resulting share complexity is $(iw_{BP}(i^2))^{O(\log{i} + \log{w_{BP}(i^2)})}$. In particular, for $w=\Omega(i)$, we get share complexity of $w_{BP}(i^2)^{O(\log{w_{BP}(i^2)})}$. Finally, a further improved variant of our scheme for a special class of ``counting'' access structures yields polynomial share complexity. In particular, we obtain an evolving secret sharing scheme for \emph{evolving majority} with share complexity $\tilde{O}(n^6)$, answering an open question of~\cite{KNY16}.

Note: Revised the "Future work" section. Also, somewhat cleaned up the notation.