Welcome to the resource topic for 2001/030
Title:
On the Power of Nonlinear Secret-Sharing
Authors: Amos Beimel, Yuval Ishai
Abstract:A secret-sharing scheme enables a dealer to distribute a secret
among n parties such that only some predefined authorized sets of
parties will be able to reconstruct the secret from their shares.
The (monotone) collection of authorized sets is called an access
structure, and is freely identified with its characteristic monotone
function f:{0,1}^n → {0,1}. A family of secret-sharing schemes is
called efficient if the total length of the n shares is polynomial
in n. Most previously known secret-sharing schemes belonged to a
class of linear schemes, whose complexity coincides with the
monotone span program size of their access structure. Prior to this
work there was no evidence that nonlinear schemes can be
significantly more efficient than linear schemes, and in particular
there were no candidates for schemes efficiently realizing access
structures which do not lie in NC.
The main contribution of this work is the construction of two
efficient nonlinear schemes:
(1) A scheme with perfect privacy whose access structure is
conjectured not to lie in NC;
(2) A scheme with statistical privacy whose access structure is
conjectured not to lie in P/poly.
Another contribution is the study of a class of nonlinear schemes,
termed quasi-linear schemes, obtained by composing linear schemes
over different fields. We show that while these schemes are possibly
(super-polynomially) more powerful than linear schemes, they cannot
efficiently realize access structures outside NC.
ePrint: https://eprint.iacr.org/2001/030
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 .