Cheating Detection and Identification in Shamir Secret Sharing Scheme using Parity-Based Verification
Abstract
Shamir's (k, n)-threshold secret sharing scheme provides information-theoretic secrecy against unauthorized subsets. However, it does not verify whether submitted shares are genuine during reconstruction. This study proposes a parity-based modification of Shamir's scheme. In the proposed construction, each share is extended into a triplet over Zp (the integers modulo p). The additional component ci serves as an authenticated verification parameter bound to the participant identity and share value. Under the authenticated parity model, the proposed scheme detects and identifies forged shares before reconstruction. Once a forged share is identified, its original value can be restored locally from the authenticated parity value. The cheating success probability is bounded by 1/p. The construction also attains the Ogata-Kurosawa-Stinson lower bound on share size and preserves the threshold reconstruction property. The secret is embedded as the leading coefficient ak-1 and recovered using a recursive divided-difference formulation, requiring O(k2) field operations and O(k) memory after verification. Runtime evaluation over a 256-bit prime field shows that reconstruction remains practical for large reconstruction sets. The additional parity component yields information rate rho = 1/2. It also requires only one extra field element per participant. A blockchain wallet key-distribution case study is included to illustrate how authenticated parity values can support share verification and correction in institutional key recovery. Compared with prior cheating-detection schemes, the proposed construction achieves an OKS-bound cheating probability within a Shamir-based framework. It also supports recursive coefficient recovery and post-identification share correction.
Keywords
Full Text:
PDFReferences
A. Shamir, “How to share a secret,” Commun. ACM, vol. 22, no. 11, pp. 612–613, Nov. 1979, doi: 10.1145/359168.359176.
G. R. Blakley, “Safeguarding cryptographic keys,” in 1979 International Workshop on Managing Requirements Knowledge (MARK), New York, NY, USA: IEEE, Jun. 1979, pp. 313–318. doi: 10.1109/MARK.1979.8817296.
D. R. Stinson, Cryptography: theory and practice, 3. ed. in Discrete mathematics and its applications. Boca Raton, Fla.: Chapman & Hall/CRC, 2006.
M. Tompa and H. Woll, “How to share a secret with cheaters,” J. Cryptology, vol. 1, no. 3, pp. 133–138, Oct. 1989, doi: 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, Seattle, Washington, United States: ACM Press, 1989, pp. 73–85. doi: 10.1145/73007.73014.
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), Dhanbad: IEEE, Mar. 2018, pp. 1–6. doi: 10.1109/RAIT.2018.8389094.
B. Chor, S. Goldwasser, S. Micali, and B. Awerbuch, “Verifiable secret sharing and achieving simultaneity in the presence of faults,” in 26th Annual Symposium on Foundations of Computer Science (sfcs 1985), Portland, OR, USA: IEEE, 1985, pp. 383–395. doi: 10.1109/SFCS.1985.64.
R. J. McEliece and D. V. Sarwate, “On sharing secrets and Reed-Solomon codes,” Commun. ACM, vol. 24, no. 9, pp. 583–584, Sep. 1981, doi: 10.1145/358746.358762.
A. Martín Del Rey, J. P. Mateus, and G. R. Sánchez, “A secret sharing scheme based on cellular automata,” Applied Mathematics and Computation, vol. 170, no. 2, pp. 1356–1364, Nov. 2005, doi: 10.1016/j.amc.2005.01.026.
E. F. Brickell, “Some Ideal Secret Sharing Schemes,” in Advances in Cryptology — EUROCRYPT ’89, vol. 434, J.-J. Quisquater and J. Vandewalle, Eds., in Lecture Notes in Computer Science, vol. 434. , Berlin, Heidelberg: Springer Berlin Heidelberg, 1990, pp. 468–475. doi: 10.1007/3-540-46885-4_45.
S. Cabello, C. Padró, and G. Sáez, “Secret Sharing Schemes with Detection of Cheaters for a General Access Structure,” Designs, Codes and Cryptography, vol. 25, no. 2, pp. 175–188, Feb. 2002, doi: 10.1023/A:1013856431727.
M. Carpentieri, A. De Santis, and U. Vaccaro, “Size of Shares and Probability of Cheating in Threshold Schemes,” in Advances in Cryptology — EUROCRYPT ’93, vol. 765, T. Helleseth, Ed., in Lecture Notes in Computer Science, vol. 765. , Berlin, Heidelberg: Springer Berlin Heidelberg, 1994, pp. 118–125. doi: 10.1007/3-540-48285-7_10.
Y. Tian, J. Ma, C. Peng, and Q. Jiang, “Fair ( t , n ) threshold secret sharing scheme,” IET Information Security, vol. 7, no. 2, pp. 106–112, Jun. 2013, doi: 10.1049/iet-ifs.2012.0064.
L. Harn and C. Lin, “Detection and identification of cheaters in (t, n) secret sharing scheme,” Des. Codes Cryptogr., vol. 52, no. 1, pp. 15–24, Jul. 2009, doi: 10.1007/s10623-008-9265-8.
C.-S. Laih and Y.-C. Lee, “V-fairness (t, n) secret sharing scheme,” IEE Proc., Comput. Digit. Tech., vol. 144, no. 4, p. 245, 1997, doi: 10.1049/ip-cdt:19971223.
Y. Liu, “Linear ( k , n ) secret sharing scheme with cheating detection,” Security Comm Networks, vol. 9, no. 13, pp. 2115–2121, Sep. 2016, doi: 10.1002/sec.1467.
D. Becerra and G. Vega, “Secret Sharing Scheme with Efficient Cheating Detection,” in Proceedings of the 2nd International Conference on Networking, Information Systems & Security, Rabat Morocco: ACM, Mar. 2019, pp. 1–7. doi: 10.1145/3320326.3320331.
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: 10.1016/j.ins.2018.04.043.
R. H. Munfa’ati, S. Guritman, and B. P. Silalahi, “Application of Recursive Algorithm on Shamir’s Scheme Reconstruction for Cheating Detection and Identification,” Jambura J. Math, vol. 4, no. 1, Jan. 2022, doi: 10.34312/jjom.v4i1.12001.
Z. Nur 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, p. 27, Apr. 2020, doi: 10.26714/jkpm.7.1.2020.27-41.
A. K. Chattopadhyay, S. Saha, A. Nag, and S. Nandi, “Secret sharing: A comprehensive survey, taxonomy and applications,” Computer Science Review, vol. 51, p. 100608, Feb. 2024, doi: 10.1016/j.cosrev.2023.100608.
P. Sarosh, S. A. Parah, G. M. Bhat, A. A. Heidari, and K. Muhammad, “Secret Sharing-based Personal Health Records Management for the Internet of Health Things,” Sustainable Cities and Society, vol. 74, p. 103129, Nov. 2021, doi: 10.1016/j.scs.2021.103129.
V. Attasena, J. Darmont, and N. Harbi, “Secret sharing for cloud data security: a survey,” The VLDB Journal, vol. 26, no. 5, pp. 657–681, Oct. 2017, doi: 10.1007/s00778-017-0470-9.
R. Gennaro, S. Goldfeder, and A. Narayanan, “Threshold-Optimal DSA/ECDSA Signatures and an Application to Bitcoin Wallet Security,” in Applied Cryptography and Network Security, vol. 9696, M. Manulis, A.-R. Sadeghi, and S. Schneider, Eds., in Lecture Notes in Computer Science, vol. 9696. , Cham: Springer International Publishing, 2016, pp. 156–174. doi: 10.1007/978-3-319-39555-5_9.
A. A. A. M. Kamal and M. Fujisawa, “Efficient and secure secret sharing-based data outsourcing suitable for Internet of Things environments,” Internet of Things, vol. 32, p. 101645, Jul. 2025, doi: 10.1016/j.iot.2025.101645.
M. Tejedor-Romero, D. Orden, I. Marsa-Maestre, J. Junquera-Sanchez, and J. M. Gimenez-Guzman, “Distributed Remote E-Voting System Based on Shamir’s Secret Sharing Scheme,” Electronics, vol. 10, no. 24, p. 3075, Dec. 2021, doi: 10.3390/electronics10243075.
D. Liu, G. Yu, Z. Zhong, and Y. Song, “Secure multi-party computation with secret sharing for real-time data aggregation in IIoT,” Computer Communications, vol. 224, pp. 159–168, Aug. 2024, doi: 10.1016/j.comcom.2024.06.002.
S. Saha, A. K. Chattopadhyay, A. K. Barman, A. Nag, and S. Nandi, “Secret Image Sharing Schemes: A Comprehensive Survey,” IEEE Access, vol. 11, pp. 98333–98361, 2023, doi: 10.1109/ACCESS.2023.3304055.
J. Pieprzyk and X.-M. Zhang, “Cheating Prevention in Linear Secret Sharing,” in Information Security and Privacy, vol. 2384, L. Batten and J. Seberry, Eds., in Lecture Notes in Computer Science, vol. 2384. , Berlin, Heidelberg: Springer Berlin Heidelberg, 2002, pp. 121–135. doi: 10.1007/3-540-45450-0_9.
E. F. Brickell and D. M. Davenport, “On the classification of ideal secret sharing schemes,” J. Cryptology, vol. 4, no. 2, pp. 123–134, Jan. 1991, doi: 10.1007/BF00196772.
Y. Kim, J. Kwon, and H.-S. Lee, “On Ideal Secret-Sharing Schemes for $k$-homogeneous access structures,” 2023, arXiv. doi: 10.48550/ARXIV.2309.07479.
DOI: http://dx.doi.org/10.30829/zero.v10i2.28985
Refbacks
- There are currently no refbacks.
This work is licensed under a Creative Commons Attribution-ShareAlike 4.0 International License.