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.
Category / Keywords: cryptographic protocols / Verifiable Secret Sharing Schemes, Error-Correcting Codes Publication Info: full version of the paper presented in WCC 2005 Date: received 1 Oct 2003, last revised 20 Jun 2005 Contact author: svetla nikova at esat kuleuven ac be Available format(s): Postscript (PS) | Compressed Postscript (PS.GZ) | PDF | BibTeX Citation Version: 20050620:161424 (All versions of this report) Short URL: ia.cr/2003/210 Discussion forum: Show discussion | Start new discussion