Welcome to the resource topic for 2016/1088
Title:
How to infinitely share a secret more efficiently
Authors: 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}.
ePrint: https://eprint.iacr.org/2016/1088
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 .