Application of Recursive Algorithm on Shamir's Scheme Reconstruction for Cheating Detection and Identification

Rafika Husnia Munfa'ati; Sugi Guritman; Bib Paruhum Silalahi

doi:10.34312/jjom.v4i1.12001

Application of Recursive Algorithm on Shamir's Scheme Reconstruction for Cheating Detection and Identification

Rafika Husnia Munfa'ati, Sugi Guritman, Bib Paruhum Silalahi

Abstract

Information data protection is necessary to ward off and overcome various fraud attacks that may be encountered. A secret sharing scheme that implements cryptographic methods intends to maintain the security of confidential data by a group of trusted parties is the answer. In this paper, we choose the application of recursive algorithm on Shamir-based linear scheme as the primary method. In the secret reconstruction stage and since the beginning of the share distribution stage, these algorithms have been integrated by relying on a detection parameter to ensure that the secret value sought is valid. Although the obtained scheme will be much simpler because it utilizes the Vandermonde matrix structure, the security aspect of this scheme is not reduced. Indeed, it is supported by two detection parameters formulated from a recursive algorithm to detect cheating and identify the cheater(s). Therefore, this scheme is guaranteed to be unconditionally secure and has a high time efficiency (polynomial running time).

Keywords

Cryptography; Recursive Algorithm; Shamir’s Linear Scheme

Full Text:

PDF

References

Z. N. Ahzan, S. Guritman, and B. P. Silalahi, “Deteksi dan Identifikasi Pelaku Kecurangan Skema Pembagian Rahasia Linear Berbasis Skema Shamir,” Jurnal Karya Pendidikan Matematika, vol. 7, no. 1, pp. 27–41, 2020.

A. Shamir, “How to share a secret,” Communications of the ACM, vol. 22, no. 11, pp. 612–613, nov 1979, doi: http://dx.doi.org/10.1145/359168.359176.

G. R. Blakley, “Safeguarding cryptographic keys,” in 1979 International Workshop on Managing Requirements Knowledge (MARK). IEEE, jun 1979, pp. 313–318, doi: http://dx.doi.org/10.1109/MARK.1979.8817296.

M. Tompa and H. Woll, “How to share a secret with cheaters,” Journal of Cryptology, vol. 1, no. 3, pp. 133–138, oct 1989, doi: http://dx.doi.org/10.1007/BF02252871.

T. Rabin and M. Ben-Or, “Verifiable secret sharing and multiparty protocols with honest majority,” in Proceedings of the twenty-first annual ACM symposium on Theory of computing - STOC ’89. New York, New York, USA: ACM Press, 1989, pp. 73–85, doi: http://dx.doi.org/10.1145/73007.73014.

A. Slinko, “Ways to merge two secret sharing schemes,” IET Information Security, vol. 14, no. 1, pp. 146–150, jan 2020, doi: http://dx.doi.org/10.1049/iet-ifs.2019.0210.

D. Becerra and G. Vega, “Secret Sharing Scheme with Efficient Cheating Detection,” in Proceedings of the 2nd International Conference on Networking, Information Systems and Security - NISS19. New York,: ACM Press, 2019, pp. 1–7, doi: http://dx.doi.org/10.1145/3320326. 3320331.

Y. Liu, “Linear ( k , n ) secret sharing scheme with cheating detection,” Security and Communication Networks, vol. 9, no. 13, pp. 2115–2121, sep 2016, doi: http://dx.doi.org/10.1002/sec.1467.

Y. Liu, C. Yang, Y. Wang, L. Zhu, and W. Ji, “Cheating identifiable secret sharing scheme using symmetric bivariate polynomial,” Information Sciences, vol. 453, pp. 21–29, jul 2018, doi: http://dx.doi.org/10.1016/j.ins.2018.04.043.

K. H. Rosen, Discrete Mathematics and Its Application, 8th ed. New York: McGraw-Hill Education, 2019.

L. Harn, C.-F. Hsu, Z. Xia, and J. Zhou, “How to Share Secret Efficiently over Networks,” Security and Communication Networks, vol. 2017, pp. 1–6, 2017, doi: http://dx.doi.org/10.1155/2017/5437403.

A. Patra and D. Ravi, “Beyond Honest Majority: The Round Complexity of Fair and Robust Multi-party Computation,” in Advances in Cryptology – ASIACRYPT, 2019, pp. 456–487, doi: http://dx.doi.org/10.1007/978-3-030-34578-5 17.

L. Harn, Z. Xia, C. Hsu, and Y. Liu, “Secret sharing with secure secret reconstruction,” Information Sciences, vol. 519, pp. 1–8, may 2020, doi: http://dx.doi.org/10.1016/j.ins.2020. 01.038.

M. Xiao and Z. Xia, “Security Analysis of a Multi-secret Sharing Scheme with Unconditional Security,” in SpaCCS 2020, LNCS, 2021, ch. 12383, pp. 533–544, doi: http://dx.doi.org/10.1007/978-3-030-68884-4 44.

S. Cabello, C. Padro´ , and G. Sa´ez, “Secret sharing schemes with detection of cheaters for general access structure,” Des. Codes Cryptogr., vol. 25, no. 2, pp. 175–188, 2002.

S. Mashhadi, “Secure publicly verifiable and proactive secret sharing schemes with general access structure,” Information Sciences, vol. 378, pp. 99–108, feb 2017, doi: http://dx.doi.org/10.1016/j.ins.2016.10.040.

S. Banerjee, D. S. Gupta, and G. P. Biswas, “Hierarchy-based cheating detection and cheater identification in secret sharing schemes,” in 2018 4th International Conference on Recent Advances in Information Technology (RAIT). IEEE, mar 2018, pp. 1–6, doi: http://dx.doi.org/10.1109/RAIT.2018.8389094.

DOI: https://doi.org/10.34312/jjom.v4i1.12001