Cryptology ePrint Archive: Report 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 $({\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