**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 $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.

**Category / Keywords: **cryptographic protocols / information theoretically secure secret sharing,

**Date: **received 21 Mar 2002, last revised 21 Mar 2002

**Contact author: **cramer at daimi aau dk

**Available format(s): **Postscript (PS) | Compressed Postscript (PS.GZ) | BibTeX Citation

**Version: **20020322:022646 (All versions of this report)

**Short URL: **ia.cr/2002/036

[ Cryptology ePrint archive ]