Paper 2019/1137
On the Complexity of Arithmetic Secret Sharing
Ronald Cramer, Chaoping Xing, and Chen Yuan
Abstract
Since the mid 2000s, asymptotically-good strongly-multiplicative linear (ramp) secret
sharing schemes over a fixed finite field have turned out as a
central theoretical primitive in numerous
constant-communication-rate results in multi-party cryptographic scenarios,
and, surprisingly, in two-party cryptography as well.
Known constructions of this most powerful class of arithmetic secret sharing schemes all rely heavily on algebraic geometry (AG), i.e., on dedicated AG codes based on asymptotically good towers of algebraic function fields defined over finite fields. It is a well-known open question since the first (explicit) constructions of such schemes
appeared in CRYPTO 2006 whether the use of ``heavy machinery'' can be avoided here. i.e.,
the question is whether the mere existence of such schemes can also be proved by ``elementary''
techniques only (say, from classical algebraic coding theory), even disregarding effective construction. So far, there is no progress.
In this paper we show the theoretical result
that, (1) {\em no matter whether this open question has an affirmative answer or not},
these schemes {\em can} be constructed explicitly by {\em elementary algorithms} defined
in terms of basic algebraic coding theory.
This pertains to all relevant operations
associated to such schemes, including, notably,
the generation of an instance for a given number of players
Metadata
- Available format(s)
-
PDF
- Category
- Foundations
- Publication info
- Published by the IACR in TCC 2020
- Keywords
- Arithmetic Secret Sharing Scheme
- Contact author(s)
- chenyuan @ cwi nl
- History
- 2020-09-23: last of 2 revisions
- 2019-10-03: received
- See all versions
- Short URL
- https://ia.cr/2019/1137
- License
-
CC BY
BibTeX
@misc{cryptoeprint:2019/1137, author = {Ronald Cramer and Chaoping Xing and Chen Yuan}, title = {On the Complexity of Arithmetic Secret Sharing}, howpublished = {Cryptology {ePrint} Archive, Paper 2019/1137}, year = {2019}, url = {https://eprint.iacr.org/2019/1137} }