Paper 2002/036
Optimal BlackBox Secret Sharing over Arbitrary Abelian Groups
Ronald Cramer and Serge Fehr
Abstract
A {\em blackbox} 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 blackbox 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 multiparty computation over blackbox rings. In 1994 Desmedt and Frankel have proposed an elegant approach to the blackbox secret sharing problem based in part on polynomial interpolation over cyclotomic number fields. For arbitrary given $T_{t,n}$ with $0<t<n1$, 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 coprime determinants, we construct, for arbitrary given $T_{t,n}$ with $0<t<n1$ , a blackbox secret sharing scheme with expansion factor $O(\log n)$, which we show is minimal.
Metadata
 Available format(s)
 PS
 Category
 Cryptographic protocols
 Publication info
 Published elsewhere. Unknown where it was published
 Contact author(s)
 cramer @ daimi aau dk
 History
 20020322: received
 Short URL
 https://ia.cr/2002/036
 License

CC BY
BibTeX
@misc{cryptoeprint:2002/036, author = {Ronald Cramer and Serge Fehr}, title = {Optimal BlackBox Secret Sharing over Arbitrary Abelian Groups}, howpublished = {Cryptology ePrint Archive, Paper 2002/036}, year = {2002}, note = {\url{https://eprint.iacr.org/2002/036}}, url = {https://eprint.iacr.org/2002/036} }