A {\em blackbox} secret sharing (BBSS) scheme works
in exactly the same way for all finite Abelian groups $G$; it can be instantiated for
any such group $G$ and {\em only} black-box access to its group operations and to random
group elements is required. A secret is a single group element and each of the $n$ players' shares is a vector of such elements. Share-computation and secret-reconstruction is by integer linear combinations. These do not depend on $G$, and neither do the privacy and reconstruction parameters $t,r$. This classical, fundamental primitive was introduced by Desmedt and Frankel (CRYPTO 1989) in their context of “threshold cryptography.''
The expansion factor is the total number of group elements in a full sharing divided by $n$. For threshold BBSS with $t$-privacy ($1\leq t \leq n-1$), $t+1$-reconstruction and arbitrary $n$, constructions with minimal expansion $O(\log n)$ exist
(CRYPTO 2002, 2005). These results are firmly rooted in number theory; each makes
(different) judicious choices of orders in number fields admitting
a vector of elements of very large length (in the number field degree) whose corresponding Vandermonde-determinant
is sufficiently controlled
so as to enable BBSS by a suitable adaptation of Shamir's scheme.
Alternative approaches generally lead to very large expansion.
The state of the art of BBSS has not changed for the last 15 years. Our contributions are two-fold.
(1) We introduce a novel, nontrivial, effective construction of BBSS based on {\em coding theory}
For threshold-BBSS we also achieve minimal expansion factor $O(\log n)$.
$r-t$ is an arbitrarily small
constant fraction of $n$, {\em and} that has expansion factor~$O(1)$, i.e.,