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 .