Optimal Black-Box Secret Sharing over Arbitrary Abelian Groups
Ronald Cramer and Serge Fehr
Abstract
A {\em black-box} secret sharing scheme for the threshold
access structure is one which works over any finite Abelian group .
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 from which the secret and the shares
are sampled. This means that perfect completeness and perfect
privacy are guaranteed {\em regardless} of which group is chosen. We define
the black-box secret sharing problem as the problem of devising, for
an arbitrary given , a scheme with minimal expansion factor,
i.e., where the length of the full vector of shares divided by the
number of players 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 with
, the expansion factor of their scheme is . 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 with
, a black-box secret sharing scheme with expansion factor
, which we show is minimal.