**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 $({\tt share}_1', \cdots, {\tt share}_n')$. In this paper, we first prove that there exists an error decodable secret sharing scheme if and only if the adversary structure $\Gamma$ satisfies a certain condition called $Q^3$. Next for any $\Gamma$ 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 $\Gamma$. We finally show an applicaiton to $1$-round Perfectly Secure Message Transmission schemes (PSMT).

**Category / Keywords: **secret sharing, cheater, error decodable, PSMT

**Date: **received 2 Jun 2009

**Contact author: **kurosawa at mx ibaraki ac jp

**Available format(s): **Postscript (PS) | Compressed Postscript (PS.GZ) | PDF | BibTeX Citation

**Version: **20090603:102423 (All versions of this report)

**Short URL: **ia.cr/2009/263

**Discussion forum: **Show discussion | Start new discussion

[ Cryptology ePrint archive ]