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)
PDF
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
Creative Commons Attribution
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},
      note = {\url{https://eprint.iacr.org/2014/628}},
      url = {https://eprint.iacr.org/2014/628}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.