Paper 2014/628
An Efficient $t$-Cheater Identifiable Secret Sharing Scheme with Optimal Cheater Resiliency
Partha Sarathi Roy, Avishek Adhikari, Rui Xu, Kirill Morozov, and Kouichi Sakurai
Abstract
In this paper, we present an efficient $k$-out-of-$n$ secret sharing scheme, which can identify up to $t$ rushing cheaters, with probability at least $1 - \epsilon$, where $0<\epsilon<1/2$, provided $t < k/2$. This is the optimal number of cheaters that can be tolerated in the setting of public cheater identification, on which we focus in this work. In our scheme, the set of all possible shares $V_i$ satisfies the condition that $|V_i|= \frac{(t+1)^{2n+k-3}|S|}{\epsilon^{2n+k-3}}$, where $S$ denotes the set of all possible secrets. In PODC-2012, Ashish Choudhury came up with an efficient $t$-cheater identifiable $k$-out-of-$n$ secret sharing scheme, which was a solution of an open problem proposed by Satoshi Obana in EUROCRYPT-2011. The share size, with respect to a secret consisting of one field element, of Choudhury's proposal in PODC-2012 is $|V_i|=\frac{(t+1)^{3n}|S|}{\epsilon^{3n}}$. Therefore, our scheme presents an improvement in share size over the above construction. Hence, to the best of our knowledge, our proposal currently has the minimal share size among existing efficient schemes with optimal cheater resilience, in the case of a single secret.
Metadata
- Available format(s)
- Publication info
- Preprint. MINOR revision.
- Keywords
- secret sharing
- Contact author(s)
-
royparthasarathi0 @ gmail com
avishek adh @ gmail com - History
- 2014-08-20: received
- Short URL
- https://ia.cr/2014/628
- License
-
CC BY
BibTeX
@misc{cryptoeprint:2014/628, author = {Partha Sarathi Roy and Avishek Adhikari and Rui Xu and Kirill Morozov and Kouichi Sakurai}, title = {An Efficient $t$-Cheater Identifiable Secret Sharing Scheme with Optimal Cheater Resiliency}, howpublished = {Cryptology {ePrint} Archive, Paper 2014/628}, year = {2014}, url = {https://eprint.iacr.org/2014/628} }