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 $({\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).
Metadata
- Available format(s)
-
PDF
PS
- Publication info
- Published elsewhere. Unknown where it was published
- Keywords
- secret sharingcheatererror decodablePSMT
- 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},
note = {\url{https://eprint.iacr.org/2009/263}},
url = {https://eprint.iacr.org/2009/263}
}
