Paper 2020/1616

Algebraic Geometric Secret Sharing Schemes over Large Fields Are Asymptotically Threshold

Fan Peng, 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 ${\mathbf{F}}_q$ is quasi-threshold in the following sense, any subset of $u\le T-1$ players (non qualified) has no information of the secret and any subset of $u\ge 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 $$ players can recover the secret or have no information of the secret? In this paper it is proved that almost all subsets of $$ players have no information of the secret and almost all subsets of $$ players can reconstruct the secret when the size $$ goes to the infinity and the genus satisfies $$. Then algebraic geometric secretsharing schemes over large finite fields are asymptotically threshold in this case. We also analyze the case when the size $$ of the base field is fixed and the genus goes to the infinity.