Graph isomorphism and Zero Knowledge of a Discrete Logarithm (Part2)

Langsung aja buat temen2 semua,,ini lanjutan tugas kemarin,,hufft,,hhe
maaf cuma sedikit, lagi males buat posting,,T__T

PENGERTIAN

Definisi. Graf sederhana G1 = (V1, E1) dan G2 = (V2, E2) disebut isomorfis jika ada sebuah fungsi bijektif (satu-ke-satu dan onto) dari V1 ke V2 dengan sifat bahwa a bertetangga dengan b pada G1 jika dan hanya jika f(a) bertetangga dengan f(b) pada G2, untuk seluruh a dan b pada V1.

Fungsi f seperti itu disebut isomorfisme. Dengan kata lain, G1 dan G2 adalah isomorfis jika simpul-simpulnya dapat diurutkan dengan suatu cara sedemikian rupa sehingga matriks kedekatan dan dan adalah identik. Secara visual, dua buah graf, G1dan G2, isomorfis jika graf-graf tersebut dapat disusun dengan suatu cara sedemikian rupa sehingga tampilannya identik (tentu tanpa merubah ketetanggaan).

Menentukan dua buah graf tidak isomorfis lebih mudah dibandingkan dengan menentukan apakah dua buah graf isomorfis. Untuk dua buah graf sederhana dengan masing-masing simpulnya berjumlah n buah, maka akan ada n! kemungkinan isomorfisme yang harus diperiksa. Untuk itu kita dapat memeriksa invarian, yaitu, sifat yang harus dimiliki oleh dua buah graf sederhana yang isomorfis. Keduanya haruslah :

* memiliki jumlah simpul yang sama, dan

* jumlah garis hubung yang sama , dan

* derajat dari simpul-simpulnya sama.

Perhatikan bahwa dua graf yang salah satu dari invarian di atas berbeda pasti menyebabkan kedua graf tersebut tidak isomorfis, tetapi jika seluruhnya sesuai, belum tentu graf tersebut isomorfis.

Jadi dapat dikatakan bahwa :

* Graf adalah sebuah jaringan garis yang menghubungkan titik-titik yang berbeda.

* Isomorfis bila identik kecuali untuk nama dari titik-titiknya

* Untuk graf yang besar, menemukan keisomorfisan membutuhkan perhitungan berabad-abad. Keisomorfisan merupakan salah satu NP-complete problem.

2. PEMANFAATAN

Diasumsikan bahwa mengetahui keisomorfisan diantara dua graf, G1 dan G2. protokol akan meyakinkan Victor bahwa Peggy mengetahui keisomorfisan tersebut:

1. Peggy secara acak mempermutasi G1 untuk menghasilkan graf lain, H, yang isomorfis dengan G1. Karena Peggy mengetahui keisomorfisan antara H dan G1, maka Peggy juga mengetahui keisomorfisan antara H dan G2. Untuk orang lain, menemukan keisomorfisan antara G1 dan H atau antara G2 dan H sama susahnya dengan menemukan keisomorfisan antara G1 dan G2.
2. Peggy mengirmkan H ke Victor.
3. Victor menanyakan kpd Peggy untuk :membuktikan H dan G1 adalah isomorfis, atau membuktikan bahwa H dan G2 adalah isomorfis.Peggy mengikutii, dia kemudian:membuktikan bahwa H dan G1 adalah isomorfis, tanpa membuktikan bahwa H dan G2 adalah isomorfis, atau
4.  membuktikan bahwa H dan G2 adalah isomorfis, tanpa membuktikan bahwa H dan G1 adalah isomorfis.
5. Peggy dan Victor mengulang langkah (1) sampai (4) sebanyak n kali.

         Jika Peggy tidak mengetahui keisomorfisan antara G1 dan G2, Peggy tidak dapat menghasilkan graf H yang isomorfis untuk keduanya. Peggy dapat menghasilkan sebuah graf yang isomorfis untuk G1 atau yang isomorfis to G2. seperti contoh sebelumnya, Peggy hanya punya 50 persen kesempatan untuk menebak langkah mana yang akan diambil Victor untuk ditanyakan pada Peggy pada langkah ke3.

          Protokol ini tidak memberikan Victor banyak informasi yang berguna untuk menuntun dia untuk menebak keisomofisan antara G1 dan G2. Karena Peggy menghasilkan sebuah graf baru H untuk setiap round pada protokol. Victor bisa saja tidak mendapatkan informasi apapun tidak peduli berapa banyaknya round yang mereka lakukan dalam protokol. Victor tidak akan mampu menebak keisomorfisan antara G1 dan G2 dari jawaban Peggy. Dalam setiap round, Victor menerima sebuah permutation acak yang baru pada H, bersamaan dgn keisomorfisan antara H dan G1 atau G2.

sumber