2006 | OriginalPaper | Buchkapitel
Algebraic Geometric Secret Sharing Schemes and Secure Multi-Party Computations over Small Fields
verfasst von : Hao Chen, Ronald Cramer
Erschienen in: Advances in Cryptology - CRYPTO 2006
Verlag: Springer Berlin Heidelberg
Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. powered by
We introduce algebraic geometric techniques in secret sharing and in secure multi-party computation (MPC) in particular. The main result is a linear secret sharing scheme (LSSS) defined over a finite field
${\mathbb F}_q$
, with the following properties.
1. It is
ideal
. The number of players
n
can be
as large as
$\#C({\mathbb F}_q)$
, where
C
is an algebraic curve
C
of genus
g
defined over
${\mathbb F}_q$
.
2. It is
quasi-threshold
: it is
t
-rejecting and
t
+1+2
g
-accepting, but not necessarily
t
+1-accepting. It is thus in particular a ramp scheme. High information rate can be achieved.
3. It has
strong multiplication
with respect to the
t
-threshold adversary structure, if
$t<\frac{1}{3}n-\frac{4}{3}g$
. This is a multi-linear algebraic property on an LSSS facilitating zero-error multi-party multiplication, unconditionally secure against corruption by an active
t
-adversary.
4. The finite field
${\mathbb F}_q$
can be
dramatically smaller than n
. This is by using algebraic curves with many
${\mathbb F}_q$
-rational points. For example, for each small enough
ε
, there is a finite field
${\mathbb F}_q$
such that for infinitely many
n
there is an LSSS over
${\mathbb F}_q$
with strong multiplication satisfying
$(\frac{1}{3}- \epsilon) n\leq t < \frac{1}{3}n$
.
5. Shamir’s scheme, which requires
n
>
q
and which has strong multiplication for
$t<\frac{1}{3}n$
, is a special case by taking
g
=0.
Now consider the classical (“BGW”) scenario of MPC unconditionally secure (with zero error probability) against an active
t
-adversary with
$t<\frac{1}{3}n$
, in a synchronous
n
-player network with secure channels. By known results it now follows that there exist MPC protocols in this scenario, achieving the same communication complexities in terms of the number of field elements exchanged in the network compared with known Shamir-based solutions. However, in return for decreasing corruption tolerance by a small
ε
-fraction,
q
may be dramatically smaller than
n
. This tolerance decrease is unavoidable due to properties of MDS codes. The techniques extend to other models of MPC. Results on less specialized LSSS can be obtained from more general coding theory arguments.