Cryptology ePrint Archive: Report 2020/1616
Algebraic Geometric Secret Sharing Schemes over Large Fields Are Asymptotically Threshold
Fan Peng and Hao Chen and Chang-An Zhao
Abstract: In Chen-Cramer Crypto 2006 paper \cite{cc} algebraic geometric secret sharing schemes were proposed such that the ``Fundamental Theorem in Information-Theoretically Secure Multiparty Computation" by Ben-Or, Goldwasser and Wigderson \cite{BGW88} and Chaum, Crépeau and Damgård \cite{CCD88} can be established over constant-size base
finite fields. These algebraic geometric secret sharing schemes defined by a curve of genus $g$ over a constant size finite field ${\bf F}_q$ is quasi-threshold in the following sense, any subset of $u \leq T-1$ players (non qualified) has no information of the secret and any subset of $u \geq T+2g$ players (qualified) can reconstruct the secret. It is natural to ask that how far
from the threshold these quasi-threshold secret sharing schemes are? How many subsets of $u \in [T, T+2g-1]$ players can recover the secret or have no information of the secret?
In this paper it is proved that almost all subsets of $u \in [T,T+g-1]$ players have no information of the secret and almost all
subsets of $u \in [T+g,T+2g-1]$ players can reconstruct the secret when the size $q$ goes to the infinity and the genus satisfies $\lim \frac{g}{\sqrt{q}}=0$. Then algebraic geometric secretsharing schemes over large finite fields are asymptotically
threshold in this case. We also analyze the case when the size $q$ of the base field is fixed and the genus goes to the infinity.
Category / Keywords: public-key cryptography / Algebraic geometric secret sharing, Quasi-threshold, Threshold, Algebraic-Geometry codes.
Date: received 29 Dec 2020
Contact author: zhaochan3 at mail sysu edu cn
Available format(s): PDF | BibTeX Citation
Version: 20201230:215038 (All versions of this report)
Short URL: ia.cr/2020/1616
[ Cryptology ePrint archive ]