Paper 2003/210
On a Relation Between Verifiable Secret Sharing Schemes and a Class of Error-Correcting Codes
Ventzislav Nikov and 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
Metadata
- Available format(s)
-
PDF PS
- Category
- Cryptographic protocols
- Publication info
- Published elsewhere. full version of the paper presented in WCC 2005
- Keywords
- Verifiable Secret Sharing SchemesError-Correcting Codes
- Contact author(s)
- svetla nikova @ esat kuleuven ac be
- History
- 2005-06-20: last of 4 revisions
- 2003-10-02: received
- See all versions
- Short URL
- https://ia.cr/2003/210
- License
-
CC BY
BibTeX
@misc{cryptoeprint:2003/210, author = {Ventzislav Nikov and Svetla Nikova}, title = {On a Relation Between Verifiable Secret Sharing Schemes and a Class of Error-Correcting Codes}, howpublished = {Cryptology {ePrint} Archive, Paper 2003/210}, year = {2003}, url = {https://eprint.iacr.org/2003/210} }