Cheating Detection and Identification in Shamir Secret Sharing Scheme using Parity-Based Verification - Mirza Farhan Azhari; Sugi Guritman; Jaharuddin Jaharuddin; Teduh Wulandari Mas'oed (ZERO: Jurnal Sains, Matematika dan Terapan, 2026)
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.