Paper 2015/1115

Efficient Threshold Secret Sharing Schemes Secure against Rushing Cheaters

Avishek Adhikari, Kirill Morozov, Satoshi Obana, Partha Sarathi Roy, Kouichi Sakurai, and Rui Xu

Abstract

In this paper, we consider three very important issues namely detection, identification and robustness of $k$-out-of-$n$ secret sharing schemes against rushing cheaters who are allowed to submit (possibly forged) shares {\em after} observing shares of the honest users in the reconstruction phase. Towards this we present five different schemes. Among these, first we present two $k$-out-of-$n$ secret sharing schemes, the first one being capable of detecting $(k-1)/3$ cheaters such that $|V_i|=|S|/\epsilon^3$ and the second one being capable of detecting $n-1$ cheaters such that $|V_i|=|S|/\epsilon^{k+1}$, where $S$ denotes the set of all possible secrets, $\epsilon$ denotes the successful cheating probability of cheaters and $V_i$ denotes set all possible shares. Next we present two $k$-out-of-$n$ secret sharing schemes, the first one being capable of identifying $(k-1)/3$ rushing cheaters with share size $|V_i|$ that satisfies $|V_i|=|S|/\epsilon^k$. This is the first scheme whose size of shares does not grow linearly with $n$ but only with $k$, where $n$ is the number of participants. For the second one, in the setting of public cheater identification, we present an efficient optimal cheater resilient $k$-out-of-$n$ secret sharing scheme against rushing cheaters having the share size $|V_i|= (n-t)^{n+2t}|S|/\epsilon^{n+2t}$. The proposed scheme achieves {\em flexibility} in the sense that the security level (i.e. the cheater(s) success probability) is independent of the secret size. Finally, we design an efficient $(k, \delta)$ robust secret sharing secure against rushing adversary with optimal cheater resiliency. Each of the five proposed schemes has the smallest share size having the mentioned properties among the existing schemes in the respective fields.

Metadata
Available format(s)
PDF
Category
Cryptographic protocols
Publication info
Preprint. MINOR revision.
Keywords
Secret SharingCheating DetectionCheater IdentificationRobustnessRushing CheatersUniversal HashReed-Solomon Code
Contact author(s)
morozov @ imi kyushu-u ac jp
History
2015-11-18: received
Short URL
https://ia.cr/2015/1115
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2015/1115,
      author = {Avishek Adhikari and Kirill Morozov and Satoshi Obana and Partha Sarathi Roy and Kouichi Sakurai and Rui Xu},
      title = {Efficient Threshold Secret Sharing Schemes Secure against Rushing Cheaters},
      howpublished = {Cryptology ePrint Archive, Paper 2015/1115},
      year = {2015},
      note = {\url{https://eprint.iacr.org/2015/1115}},
      url = {https://eprint.iacr.org/2015/1115}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.