We examine the fake share scenario posed by Tompa and Woll and propose scheme to counteract the problem of cheating. Tompa and Woll suggested that in Shamir’s secret reconstruction algorithm, a dishonest user (cheater) could decide to pool a fake share in order to get the real secret; thus, the other honest users receive an incorrect share. Shamir’s scheme does not prevent any malicious behaviour of dishonest users during secret reconstruction. Cheater detection and identification are very important for fair secret reconstruction. Our proposed scheme is not only to detect and identify a cheater, but to prevent him from recovering the secret exclusively when the honest users cannot. Otherwise, our scheme will show us in secret reconstruction algorithm that how to recover the secret by honest users even if a cheater pools a fake share.

secret sharing, verifiable secret sharing, honest users, dishonest users.

Received: February 2, 2023;  Accepted: March 6, 2023; Published: April 11, 2023

How to cite this article: Qassim Al Mahmoud, Khaldoun Besoul and Ayman Alhalaybeh, Unconditionally secure fair (t, n)-secret sharing scheme, Advances and Applications in Discrete Mathematics 38(1) (2023), 127-143. http://dx.doi.org/10.17654/0974165823024

This Open Access Article is Licensed under Creative Commons Attribution 4.0 International License

References:

[1] A. Shamir, How to share a secret, Comm. ACM 22(11) (1979), 612-613.
[2] T. Araki, Efficient threshold secret sharing schemes secure against cheating from cheaters, Proceedings of ACISP’07, LNCS, Springer-Verlag, Vol. 4586, 2007, pp. 13-142.
[3] M. Carpentieri, A. De Santis and U. Vaccaro, Size of shares and probability of cheating in threshold schemes, Proceedings of Eurocrypt’93, LNCS, Springer-Verlag, Vol. 765, 1994, 118-125.
[4] K. Kurosawa, S. Obana and W. Ogata, t-cheater identifiable secret sharing schemes, Proceedings of Crypto’95, LNCS, Springer-Verlag, Vol. 963, 1995, pp. 410-423.
[5] T. Rabin and M. Ben-Or, Verifiable secret sharing and multiparty protocols with honest majority, Proceedings of the 21st Annual ACM Symposium on the Theory of Computing, 1989, pp. 73-85.
[6] C. Bhndo, A. De Santis, L. Gargano and U. Vaccaro, Secret sharing schemes with veto capabilities, Proceedings of the First French-Israeli Workshop on Algebraic Coding, LNCS, Springer-Verlag, Vol. 781 1993, pp. 82-89.
[7] R. J. McEliece and D. V. Sarwate, On sharing secrets and Reed-Solomon codes, Comm. ACM 24 (1981), 583-584.
[8] C. Charnes, J. Pieprzyk and R. Safavi-Naini, Conditionally secure secret sharing scheme with disenrollment capability, Proceedings of CCS’94, ACM, 1994, pp. 89-95.
[9] Y. Tian, J. Ma, C. Peng and Q. Jiang, Fair threshold secret sharing scheme, IET Information Security 7(2) (2013), 106-112.
[10] L. Harn and C. Lin, Detection and identification of cheaters in secret sharing scheme, Des. Codes Cryptogr. 52(1) (2009), 15-24.
[11] M. Tompa and H. Woll, How to share a secret with cheaters, J. Cryptol. 1(3) (1989), 133-138.
[12] T. P. Pedersen, Non-interactive and information-theoretic secure verifiable secret sharing, Advances in Cryptology-CRYPTO’91, LNCS, Springer-Verlag, Berlin, Vol. 576, 1992, pp. 129-140.
[13] Hung-Yu Lin and Lein Harn, Fair reconstruction of a secret, Inform. Process. Lett. 55(1) (1995), 45-47.
[14] B. Chor, S. Goldwasser, S. Micali and B. Awerbuch, Verifiable secret sharing and achieving simultaneity in the presence of faults, Proceedings of the 26th IEEE Symposium on Foundations of Computer Science, IEEE Computer Society, Oregon, Portland, 1985, pp. 383-395.
[15] P. Feldman, A practical scheme for non-interactive verifiable secret sharing, Proceedings of the 28th IEEE Symposium on Foundations of Computer Science, IEEE Computer Society, Los Angeles, California, 1987, pp. 427-437.