Deteksi dan Identifikasi Kecurangan pada Skema Pembagian Rahasia Shamir Menggunakan Verifikasi Berbasis Paritas

Abstract

Pengelolaan kunci kriptografi merupakan aspek penting dalam sistem keamanan modern karena berkaitan dengan kerahasiaan, integritas, dan ketersediaan informasi. Skema pembagian rahasia Shamir memungkinkan suatu rahasia dibagi menjadi beberapa keping dan hanya dapat dipulihkan apabila sejumlah minimum keping digabungkan. Namun, skema Shamir standar mengasumsikan bahwa setiap partisipan menyerahkan keping yang valid, sehingga keping yang dimodifikasi akibat kesalahan atau kecurangan dapat menghasilkan rahasia yang salah tidak dapat terdeteksi. Penelitian ini bertujuan menguraikan peran parameter verifikasi berbasis paritas dalam skema ambang batas Shamir termodifikasi, termasuk proses pembangkitan dan pengikatannya terhadap setiap keping rahasia pada tahap distribusi. Penelitian ini juga menganalisis mekanisme verifikasi paritas di bawah authenticated parity model dalam mendeteksi dan mengidentifikasi keping rahasia yang rusak selama rekonstruksi, serta menentukan kondisi yang diperlukan untuk koreksi dan pemulihan rahasia asli. Selain itu, penelitian ini mengevaluasi beban komputasi tambahan dari rekonstruksi rekursif yang diusulkan dibandingkan metode yang telah ada, serta trade-off antara efisiensi penyimpanan keping rahasia dan kinerja rekonstruksi berdasarkan batas bawah OKS. Penelitian dilakukan melalui pendekatan konstruktif-teoretis yang disertai simulasi numerik, diawali dengan kajian literatur mengenai skema pembagian rahasia Shamir dan mekanisme deteksi kecurangan di bawah kerangka Ogata–Kurosawa–Stinson (OKS). Skema bekerja pada lapangan hingga dengan bilangan prima sebagai modulus; dealer membangkitkan polinomial rahasia berderajat k-1, dan setiap partisipan memperoleh keping rahasia beserta parameter cek paritas, sehingga setiap keping direpresentasikan sebagai tripel identitas partisipan, nilai keping, dan parameter paritas yang diasumsikan tersimpan secara autentik (authenticated parity model). Pada tahap rekonstruksi, combiner memverifikasi setiap keping melalui relasi paritas, mengidentifikasi dan mengoreksi keping yang tidak sesuai, sebelum rahasia dipulihkan melalui formulasi rekursif berbasis struktur matriks Vandermonde tanpa menghitung invers matriks secara penuh. Hasil penelitian menunjukkan bahwa mekanisme paritas mampu mendeteksi, mengidentifikasi, dan mengoreksi keping tidak valid tanpa memerlukan pemeriksaan kombinatorik terhadap seluruh sub himpunan partisipan, serta tetap mempertahankan sifat kerahasiaan sempurna dari skema Shamir. Penambahan mekanisme verifikasi tidak menyebabkan peningkatan orde komputasi yang besar, meskipun laju informasi efektif menurun akibat tambahan parameter paritas pada setiap keping. Simulasi empiris menunjukkan bahwa waktu eksekusi tetap berada pada skala milidetik dan skema tetap fleksibel terhadap perubahan urutan penggabungan keping serta penambahan peserta baru. Penelitian ini menyimpulkan bahwa skema Shamir termodifikasi dengan parameter verifikasi berbasis paritas, yang direpresentasikan sebagai tripel identitas partisipan, nilai keping, dan parameter paritas, mampu mendeteksi, mengidentifikasi, dan mengoreksi keping rahasia yang dimodifikasi pada tahap rekonstruksi di bawah authenticated parity model, sekaligus tetap mempertahankan sifat kerahasiaan sempurna dari skema Shamir. Penambahan parameter paritas menurunkan laju informasi efektif menjadi ? = 1/2, namun rekonstruksi rekursif berbasis metode selisih terbagi Newton tetap efisien tanpa menghitung invers matriks Vandermonde secara penuh, sehingga penambahan mekanisme verifikasi tidak menyebabkan lonjakan kompleksitas komputasi. Simulasi empiris menunjukkan bahwa waktu eksekusi tetap berada pada skala praktis, sehingga skema yang diusulkan dapat dipandang sebagai perluasan skema Shamir yang menyediakan kemampuan verifikasi dan koreksi dengan overhead terkendali sekaligus menjadi dasar matematis bagi pengembangan skema pembagian rahasia yang lebih adaptif terhadap manipulasi keping.