Penerapan Algoritme Rekursif pada Rekonstruksi Skema Shamir untuk Deteksi dan Identifikasi Kecurangan

Abstract

Perlindungan data informasi mutlak dibutuhkan untuk menangkal dan mengatasi beragam serangan yang mungkin dihadapi. Skema pembagian rahasia (SPR) yang menerapkan metode kriptografi di dalamnya dengan tujuan mempertahankan keamanan data rahasia oleh sekelompok pihak terpercaya adalah jawabannya. Konsep ini mulanya digagas secara individual oleh Shamir (1979) dan Blakley (1979) yang lebih familiar disebut sebagai SPR ambang batas-(t,n). Prinsipnya, pesan terenkripsi (secret) s didistribusikan oleh pihak terpercaya (dealer) kepada n partisipan pemegang kunci privat (shareholder) dan hanya jika terdapat sebarang subset t atau lebih partisipan saja maka pesan tersebut baru dapat dibaca. Share dalam konteks ini berupa kepingan-kepingan secret yang harus disatukan terlebih dahulu oleh dealer agar pesan dapat didekripsi. SPR menjadi solusi atas beragam risiko serangan yang mungkin terjadi, di mana share yang terlalu sedikit akan rentan hilang dan sebaliknya jika digandakan terlalu banyak dapat meningkatkan potensi kecurangan. Penelitian ini difokuskan pada empat tujuan utama, yaitu: (1) Memodifikasi skema Shamir pada fase pembagian share dan rekonstruksi secret dengan penerapan algoritme rekursif; (2) Mengonstruksi skema linear Shamir yang telah dimodifikasi untuk mendeteksi kecurangan dan mengidentifikasi pelakunya; (3) Membuktikan bahwa skema linear Shamir yang telah dimodifikasi memiliki efisiensi waktu yang tinggi; (4) Menganalisis tingkat keamanan deteksi dan identifikasi kecurangan dari skema yang diajukan. Penerapan algoritme rekursif pada skema linear berbasis Shamir dipilih sebagai metode utamanya. Bukan hanya pada fase rekonstruksi secret, namun sejak awal pada fase pembagian share, algoritme ini telah diintegrasikan satu sama lain dengan memanfaatkan suatu parameter detektor untuk menjamin nilai secret yang dicari adalah valid. Meski skema yang diperoleh akan jauh lebih sederhana karena memanfaatkan struktur matriks Vandermonde, namun aspek keamanan pada skema ini tidak berkurang sebab didukung oleh parameter detektor khusus yang dirumuskan dari algoritme rekursif untuk mendeteksi kecurangan dan mengidentifikasi pelakunya. Karenanya skema ini dijamin aman tanpa syarat (unconditionally secure). Selain adanya parameter detektor akan menjamin bahwa hanya partisipan yang jujur sajalah yang dapat merekonstruksi secret, skema ini juga memiliki efisiensi waktu yang tinggi (polynomial running time). Hal itu dikarenakan teknik rekursif dapat meningkatkan laju komputasi yang dibutuhkan dengan menghitung ukuran masukan n pada masing-masing algoritmenya. Dengan kata lain algoritme ini mampu mengatasi kekurangan pada penelitian-penelitian SPR linear Shamir sebelumnya. Karena semakin kompleks/rumit suatu algoritme yang dijalankan maka tentu akan semakin banyak waktu yang dihabiskan untuk menyelesaikannya.

Information data protection is absolutely necessary to ward off and overcome various attacks that may be encountered. A secret sharing scheme (SSS) that implements cryptographic methods with the aim of maintaining the security of confidential data by a group of trusted parties is the answer. This concept first was conceived individually by Shamir (1979) and Blakley (1979) which is more familiar referred to as SSS threshold-(t,n). In principle, encrypted messages (secret) s are distributed by a trusted party (dealer) to n participants holding private keys (shareholders), and when there are any subset t or more participants then the message can only be read. Here, shares are secret pieces that the dealer must put together first so that the message can be decrypted. SSS is a solution to various possible attack risks, where too few shares will be vulnerable to lose and otherwise if too many are duplicated it can increase the potential for cheating. This research is mainly on four objectives, namely: (1) Modifying the Shamir scheme in the share distribution and secret reconstruction phases by applying a recursive algorithm; (2) Constructing a modified Shamir linear scheme to detect cheating and identify the cheater(s); (3) Proving that the modified Shamir linear scheme has high time efficiency; (4) Analyzing the security level of cheating detection and identification of the proposed scheme. The application of the recursive algorithm on the Shamir-based linear scheme was chosen as the main method. Not only in the secret reconstruction phase but since the beginning of the share distribution phase, these algorithms have been integrated with each other by relying on a detector 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 because it is supported by special detector parameters formulated from a recursive algorithm to detect cheating and identify the cheater(s). Therefore, this scheme is guaranteed to be unconditionally secure. In addition to the existence of a detector parameter that will ensure only honest participants can reconstruct the secret, this scheme also has a high time efficiency (polynomial running time). This is because the recursive technique can increase the computational speed required by calculating the input size n in each algorithm. In other words, this algorithm is able to overcome the shortcomings of previous Shamir linear SSS studies. Because the more complicated an algorithm is, the more time it will take to complete it.