Konstruksi dekomposisi graf untuk menentukan laju informasi suatu skema secret sharing

Abstract

Dalam suatu sistem komunikasi data, penyampaian pesan dilakukan melalui media perantara yang disebut channel. Channel dapat berupa saluran telepon, frekuensi radio, dan jaringan komputer. Agar pihak-pihak yang tidak diinginkan tidak dapat membaca pesan yang dikirimkan, maka pesan tersebut harus dikodekan (encode) ke dalam bentuk yang tidak mudah untuk dibaca, antara lain bentuk binary code (kode biner). Pada Skema Secret Sharing, pesan yang telah dikodekan tersebut dibagi menjadi beberapa bagian dan masing-masing bagian disebut dengan shadow. Kemudian sebuah shadow didistribusikan masing-masing kepada seorang penerima atau peserta. Masing-masing peserta tidak dapat memperoleh informasi mengenai isi pesan dari shadownya. Jika beberapa orang peserta menggabungkan shadow mereka, maka pesan dapat diperoleh. Pada tulisan ini dipelajari Skema Secret Sharing untuk struktur akses berlandaskan graf. Jika diberikan sebuah graf, maka dari graf tersebut dapat dilihat bahwa sepasang peserta yang pada graf direpresentasikan sebagai simpul, dapat merekonstruksi pesan jika sepasang peserta (dua simpul) dihubungkan oleh sebuah sisi. Sebaliknya, jika tidak dihubungkan oleh sebuah sisi, maka pesan tidak dapat direkonstruksi. Kemudian dipelajari laju informasi optimal dari suatu Skema Secret Sharing, yaitu dengan memberikan batas atas dan batas bawah laju informasi. Batas atas dapat diperoleh dengan menggunakan teorema dari Cappocelli et al (1993). Batas bawah diperoleh dari konstruksi yang berlandaskan pada dekomposisi graf, dan diselesaikan dengan pemrograman linear. Efisiensi suatu skema dapat ditentukan dari laju informasi optimal. Jika laju informasi lebih besar dari batas atas, maka pesan tidak dapat direkonstruksi. Sedangkan jika laju informasi lebih kecil dari batas bawah, maka skema tersebut tidak efisien.