You are looking at a specific version 20010422:191900 of this paper. See the latest version.

Paper 2001/030

On the Power of Nonlinear Secret-Sharing

Amos Beimel and 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.

Metadata
Available format(s)
PDF PS
Publication info
Published elsewhere. This paper was accepted for publication in the proceedings of the 16th Annu. IEEE Conf. on Computational Complexity, 2001
Keywords
secret-sharingnonlinear secret-sharingmonotone span programsquadratic residuosity
Contact author(s)
beimel @ cs bgu ac il
History
2001-04-22: received
Short URL
https://ia.cr/2001/030
License
Creative Commons Attribution
CC BY
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.