A
black-box secret sharing scheme for the threshold
access structure
![$T_{t,n}$](Abs/img1.gif)
is one which works over any finite Abelian group
![$G$](Abs/img2.gif)
. 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
![$Z\!\!\!Z$](Abs/img3.gif)
and are designed
independently of the group
![$G$](Abs/img2.gif)
from which the secret and the shares are
sampled. This means that perfect completeness and perfect privacy are
guaranteed
regardless of which group
![$G$](Abs/img2.gif)
is chosen. We define the
black-box secret sharing problem as the problem of devising, for an arbitrary
given
![$T_{t,n}$](Abs/img1.gif)
, a scheme with minimal expansion factor, i.e., where the
length of the full vector of shares divided by the number of players
![$n$](Abs/img4.gif)
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
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