Abstract
We introduce two publicly cheater identifiable secret sharing (CISS) schemes with efficient reconstruction, tolerating t < k/2 cheaters. Our constructions are based on (k,n) threshold Shamir scheme, and they feature a novel application of multi-receiver authentication codes to ensure integrity of shares.
The first scheme, which tolerates rushing cheaters, has the share size |S|(n − t)n + t + 2/ε n + t + 2 in the general case, that can be ultimately reduced to |S|(k − t)k + t + 2/ε k + t + 2 assuming that all the t cheaters are among the k reconstructing players. The second scheme, which tolerates non-rushing cheaters, has the share size |S|(n − t)2t + 2/ε 2t + 2. These two constructions have the smallest share size among the existing CISS schemes of the same category, when the secret is a single field element.
In addition, we point out that an improvement in the share size to \(|S|/\epsilon^{n-\lfloor (k-1)/3\rfloor +1}\) can be achieved for a CISS tolerating t < k/3 rushing cheaters presented by Xu et al. at IWSEC 2013.
Access provided by Autonomous University of Puebla. Download to read the full chapter text
Chapter PDF
Similar content being viewed by others
Keywords
References
Blarkley, G.R.: Safeguarding cryptographic keys. In: Proceedings of AFIPS 1979 National Computer Conference, vol. 48, pp. 313–317 (1979)
Choudhury, A.: Brief announcement: optimal amortized secret sharing with cheater identification. In: Kowalski, D., Panconesi, A. (eds.) Proceedings of the 2012 ACM Symposium on Principles of Distributed Computing (PODC 2012), pp. 101–102. ACM, New York (2012)
Simmons, G.J.: A survey of information authentication. Proceedings of the IEEE 76(5), 603–620 (1988)
Desmedt, Y., Frankel, Y., Yung, M.: Multi-receiver/multi-sender network security: efficient authenticated multicast/feedback. In: Eleventh Annual Joint Conference of the IEEE Computer and Communications Societies, INFOCOM 1992, pp. 2045–2054. IEEE (1992)
Canetti, R.: Security and composition of multiparty cryptographic protocols. Journal of Cryptology 13(1), 143–202 (2000)
Kurosawa, K., Obana, S., Ogata, W.: t-cheater identifiable (k, n) threshold secret sharing schemes. In: Coppersmith, D. (ed.) CRYPTO 1995. LNCS, vol. 963, pp. 410–423. Springer, Heidelberg (1995)
Martin, K.M.: Challenging the adversary model in secret sharing schemes. In: Coding and Cryptography II. Proceedings of the Royal Flemish Academy of Belgium for Science and the Arts, pp. 45–63 (2008)
McEliece, R.J., Sarwate, D.V.: On sharing secrets and Reed-Solomon codes. Commun. ACM 24(9), 583–584 (1981)
Obana, S.: Almost optimum t-Cheater Identifiable secret sharing schemes. In: Paterson, K.G. (ed.) EUROCRYPT 2011. LNCS, vol. 6632, pp. 284–302. Springer, Heidelberg (2011)
Rabin, T., Ben-Or, M.: Verifiable secret sharing and multiparty protocols with honest majority. In: Johnson, D.S. (ed.) Proceedings of the Twenty-first Annual ACM Symposium on Theory of Computing (STOC 1989), pp. 73–85. ACM, New York (1989)
Reed, I.S., Solomon, G.: Polynomial codes over certain finite fields. J. Soc. Ind. Appl. Math. 8(2), 300–304 (1960)
Safavi-Naini, R., Wang, H.: New results on multi-receiver authentication codes. In: Nyberg, K. (ed.) EUROCRYPT 1998. LNCS, vol. 1403, pp. 527–541. Springer, Heidelberg (1998)
Shamir, A.: How to Share a Secret. Commun. ACM 22(11), 612–613 (1979)
Tompa, M., Woll, H.: How to share a secret with cheaters. In: Odlyzko, A.M. (ed.) CRYPTO 1986. LNCS, vol. 263, pp. 261–265. Springer, Heidelberg (1987), Journal version in: J. Cryptol. 1(2), 133–138 (1988)
Xu, R., Morozov, K., Takagi, T.: On cheater identifiable secret sharing schemes secure against rushing adversary. In: Sakiyama, K., Terada, M. (eds.) IWSEC 2013. LNCS, vol. 8231, pp. 258–271. Springer, Heidelberg (2013)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2014 Springer International Publishing Switzerland
About this paper
Cite this paper
Xu, R., Morozov, K., Takagi, T. (2014). Cheater Identifiable Secret Sharing Schemes via Multi-Receiver Authentication. In: Yoshida, M., Mouri, K. (eds) Advances in Information and Computer Security. IWSEC 2014. Lecture Notes in Computer Science, vol 8639. Springer, Cham. https://doi.org/10.1007/978-3-319-09843-2_6
Download citation
DOI: https://doi.org/10.1007/978-3-319-09843-2_6
Publisher Name: Springer, Cham
Print ISBN: 978-3-319-09842-5
Online ISBN: 978-3-319-09843-2
eBook Packages: Computer ScienceComputer Science (R0)