Welcome to the resource topic for 2003/210
Title:
On a Relation Between Verifiable Secret Sharing Schemes and a Class of Error-Correcting Codes
Authors: Ventzislav Nikov, Svetla Nikova
Abstract:In this paper we try to shed a new insight on Verifiable Secret
Sharing Schemes (VSS). We first define a new ``metric" (with slightly
different properties than the standard Hamming metric). Using
this metric we define a very particular class of codes that we call
{\it error-set correcting codes}, based on a set of forbidden distances which is a
monotone decreasing set. Next we redefine the packing problem for the new
settings and generalize the notion of error-correcting capability of the
error-set correcting codes accordingly (taking into account the new metric and the
new packing). Then we consider burst-error interleaving codes
proposing an efficient burst-error correcting technique, which is in fact the well
known VSS and Distributed Commitments (DC) pair-wise checking protocol and we prove
the error-correcting capability of the error-set correcting interleaving codes.
Using the known relationship, due to Van Dijk, between a Monotone
Span Program (MSP) and a generator matrix of the code generated by
the suitable set of vectors, we prove that the error-set
correcting codes in fact has the allowed (opposite to forbidden)
distances of the dual access structure of the access structure
that the MSP computes. We give an efficient construction for them
based on this relation and as a consequence we establish a link
between Secret Sharing Schemes (SSS) and the error-set correcting
codes.
Further we give a necessary and sufficient condition for the existence
of linear SSS (LSSS), to be secure against (\Delta,\Delta_A)-adversary
expressed in terms of an error-set correcting code. Finally, we present necessary
and sufficient conditions for the existence of a VSS scheme,
based on an error-set correcting code, secure against (\Delta,\Delta_A)-adversary.
Our approach is general and covers all known linear VSS/DC. It allows
us to establish the minimal conditions for security of VSSs. Our
main theorem states that the security of a scheme is equivalent to
a pure geometrical (coding) condition on the linear mappings describing
the scheme. Hence the security of all known schemes, e.g. all known bounds
for existence of unconditionally secure VSS/DC including the recent result of
Fehr and Maurer, can be expressed as certain (geometrical) coding conditions.
ePrint: https://eprint.iacr.org/2003/210
See all topics related to this paper.
Feel free to post resources that are related to this paper below.
Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.
For more information, see the rules for Resource Topics .