General Error Decodable Secret Sharing Scheme and Its Application

Kaoru Kurosawa

Paper 2009/263

General Error Decodable Secret Sharing Scheme and Its Application

Kaoru Kurosawa

Abstract

Consider a model of secret sharing schemes with cheaters. We say that a secret sharing scheme is error decodable if we can still recover the secret $s$ correctly from a noisy share vector $({s h a r e}_{1}^{'}, \dots, {s h a r e}_{n}^{'})$ . In this paper, we first prove that there exists an error decodable secret sharing scheme if and only if the adversary structure $Γ$ satisfies a certain condition called $Q^{3}$ . Next for any $Γ$ which satisfies $Q^{3}$ , we show an error decodable secret sharing scheme such that the decoding algorithm runs in polynomial-time in $| S |$ and the size of a linear secret sharing scheme (monotone span program) which realzes $Γ$ . We finally show an applicaiton to $1$ -round Perfectly Secure Message Transmission schemes (PSMT).

Metadata

Available format(s): PDF PS
Publication info: Published elsewhere. Unknown where it was published
Keywords: secret sharing cheater error decodable PSMT
Contact author(s): kurosawa @ mx ibaraki ac jp
History: 2009-06-03: received
Short URL: https://ia.cr/2009/263
License: CC BY

BibTeX

@misc{cryptoeprint:2009/263,
      author = {Kaoru Kurosawa},
      title = {General Error Decodable Secret Sharing Scheme and Its Application},
      howpublished = {Cryptology {ePrint} Archive, Paper 2009/263},
      year = {2009},
      url = {https://eprint.iacr.org/2009/263}
}