**An Efficient $t$-Cheater Identifiable Secret Sharing Scheme with Optimal Cheater Resiliency**

*Partha Sarathi Roy and Avishek Adhikari and Rui Xu and 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.

**Category / Keywords: **secret sharing

**Date: **received 15 Aug 2014

**Contact author: **royparthasarathi0 at gmail com, avishek adh@gmail com

**Available format(s): **PDF | BibTeX Citation

**Version: **20140820:184437 (All versions of this report)

**Short URL: **ia.cr/2014/628

[ Cryptology ePrint archive ]