Cryptology ePrint Archive: Report 2014/628

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

Discussion forum: Show discussion | Start new discussion