Paper 2019/1134
Blackbox Secret Sharing Revisited: A CodingTheoretic Approach with Application to Expansionless NearThreshold Schemes
Ronald Cramer and Chaoping Xing
Abstract
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} blackbox 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. Sharecomputation and secretreconstruction 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 n1$), $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 Vandermondedeterminant 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 twofold. (1) We introduce a novel, nontrivial, effective construction of BBSS based on {\em coding theory} instead of number theory. For thresholdBBSS we also achieve minimal expansion factor $O(\log n)$. (2) Our method is more versatile. Namely, we show, for the first time, BBSS that is {\em nearthreshold}, i.e., $rt$ is an arbitrarily small constant fraction of $n$, {\em and} that has expansion factor~$O(1)$, i.e., individual sharevectors of {\em constant} length (``asymptotically expansionless''). Threshold can be concentrated essentially freely across full range. We also show expansion is minimal for nearthreshold and that such BBSS cannot be attained by previous methods. Our general construction is based on a wellknown mathematical principle, the localglobal principle. More precisely, we first construct BBSS over local rings through either ReedSolomon or algebraic geometry codes. We then ``glue'' these schemes together in a dedicated manner to obtain a global secret sharing scheme, i.e., defined over the integers, which, as we finally prove using novel insights, has the desired BBSS properties. Though our main purpose here is advancing BBSS for its own sake, we also briefly address possible protocol applications.
Metadata
 Available format(s)
 Category
 Foundations
 Publication info
 Preprint. MINOR revision.
 Keywords
 FoundationSecret SharingCodes
 Contact author(s)

cramer @ cwi nl
xingcp @ ntu edu sg  History
 20191002: revised
 20191002: received
 See all versions
 Short URL
 https://ia.cr/2019/1134
 License

CC BY
BibTeX
@misc{cryptoeprint:2019/1134, author = {Ronald Cramer and Chaoping Xing}, title = {Blackbox Secret Sharing Revisited: A CodingTheoretic Approach with Application to Expansionless NearThreshold Schemes}, howpublished = {Cryptology ePrint Archive, Paper 2019/1134}, year = {2019}, note = {\url{https://eprint.iacr.org/2019/1134}}, url = {https://eprint.iacr.org/2019/1134} }