Welcome to the resource topic for 2002/036
Title:
Optimal Black-Box Secret Sharing over Arbitrary Abelian Groups
Authors: Ronald Cramer, Serge Fehr
Abstract:A {\em black-box} secret sharing scheme for the threshold
access structure T_{t,n} is one which works over any finite Abelian group G.
Briefly, such a scheme differs from an ordinary linear secret sharing
scheme (over, say, a given finite field) in that distribution matrix
and reconstruction vectors are defined over the integers and are designed {\em
independently} of the group G from which the secret and the shares
are sampled. This means that perfect completeness and perfect
privacy are guaranteed {\em regardless} of which group G is chosen. We define
the black-box secret sharing problem as the problem of devising, for
an arbitrary given T_{t,n}, a scheme with minimal expansion factor,
i.e., where the length of the full vector of shares divided by the
number of players n is minimal.
Such schemes are relevant for instance in the context of distributed
cryptosystems based on groups with secret or hard to compute group
order. A recent example is secure general multi-party computation over
black-box rings.
In 1994 Desmedt and Frankel have proposed an
elegant approach to the black-box secret sharing problem
based in part on polynomial interpolation over
cyclotomic number fields. For arbitrary given T_{t,n} with
0<t<n-1, the expansion factor of their scheme is O(n). This is
the best previous general approach to the problem.
Using low degree integral extensions of the integers over which there exists a
pair of sufficiently large Vandermonde matrices with co-prime
determinants, we construct, for arbitrary given T_{t,n} with
0<t<n-1 , a black-box secret sharing scheme with expansion factor
O(\log n), which we show is minimal.
ePrint: https://eprint.iacr.org/2002/036
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 .