blog untuk menyelami dalamnya dunia


  1. Graph isomorphism
  1. 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.
  1. 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 :
    1. membuktikan H dan G1 adalah isomorfis, atau
    2. membuktikan bahwa H dan G2 adalah isomorfis.
    3. Peggy mengikutii, dia kemudian:
    4. membuktikan bahwa H dan G1 adalah isomorfis, tanpa membuktikan bahwa H dan G2 adalah isomorfis, atau
    5. membuktikan bahwa H dan G2 adalah isomorfis, tanpa membuktikan bahwa H dan G1 adalah isomorfis.
  4. 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.

  1. Zero-Knowledge Proof of a Discrete Logarithm

Zero-Knowledge Proof merupakan suatu metode yang digunakan untuk membuktikan kepada pihak lain (verifier) bahwa statement yang dia miliki adalah benar, tanpa menyatakan ke pihak yang lain tersebut mengenai kejujuran dari statement tersebut.

Terdapat beberapa properties dari Zero-Knowledge Proof diantaranya yaitu:

  1. Completeness

Prover yang jujur dapat meyakinkan kepada verifier dengan probabilitas yang sangat besar.

  1. Soundness

Tidak ada seorangpun yang tidak menetahui tentang rahasia tersebut dapat meyakinkan verifier dengan probabilitas dapat diabaikan

  1. Zero-knowledge

Pembuktian tidak akan bocor dengan informasi tambahan

Zero-Knowledge Proof of a Discrete Logarithm merupakan salah satu Zero-Knowledge Proof pada logaritma diskrit. Misalkan Peggy ingin membuktikan kepada victor bahwa dia mengetahui suatu nilai x yang memenuhi persamaan Ax ≡B (mod p). Dimana p = prima, x = bilangan acak yang relatif prima terhadap p. A, B dan p adalah publik, x adalah privat.

Protokol :

  1. Peggy membangkitkan nilai acak r sebanyak t, dimana ri < p-1.
  2. Peggy menghitung hi = Ari mod p, untuk semua nilai i, dan mengirimnya kepada Victor.
  3. Peggy dan Victor membangkitkan t bit: b1,b2,b3,…,bt.
  1. Untuk semua bit t, Peggy melakukan :
    • Jika bi = 0, dia mengirim ri kepada Victor
    • Jika bi = 1, dia mengirimkan si = (ri-rj) mod (p-1), dimana j nilai terkecil untuk bj=1.
  2. Untuk semua bit t, Victor mengkonfirmasi :
    • jika bi = 0, bahwa Ari ≡ hi (mod p)
    • jika bi = 1, bahwa Asi ≡ hihj-1 (mod p)
  3. Peggy mengirim victor Z, dimana Z = (x – rj) mod (p – 1)
  4. Victor konfirmasi bahwa AZ ≡ Bhj-1 (mod p)

Probabilitas kemungkinan Peggy melakukan penipuan yaitu sebesar 2-t.

Contoh Soal:

Misalkan P=7, x=5, A=2, B=4  memenuhi persamaan Ax ≡ B (mod p).

Protokol :

  1. Peggy membangkitkan nilai acak r sebanyak t, dimana ri < p-1.

r1 = 2, r2 = 3,dan r3 = 4

  1. Peggy menghitung hi = Ari mod p, untuk semua nilai i, dan mengirimnya kepada Victor.

h1 = 22 mod 7 = 4

h2 = 23 mod 7 = 1

h3 = 24 mod 7 = 2

  1. Peggy dan Victor membangkitkan t bit: b1,b2,b3,…,bt.

Missal :

b1 = 0, b2 = 1, dan b3 = 1

  1. Untuk semua bit t, Peggy melakukan :
    • b1 = 0, dia mengirim r1 = 2 kepada Victor
    • b2 = 1, dia mengirimkan si = (ri-rj) mod (p-1), dimana j nilai terkecil untuk bj=1.

S2 = (r2-r2) mod p = 3-3 mod 6 = 0

    • b3 = 1, dia mengirimkan

S3 = (r3-r2) mod p = 4-3 mod 6 = 1

  1. Untuk semua bit t, Victor mengkonfirmasi :
    1. b1 = 0, bahwa Ar1 ≡ h1 (mod p)  22 4 mod 7
    2. b2 = 1, bahwa As2 ≡ h2h2-1 (mod p)  20 1.1-1 mod 7 1 mod 7
    3. b3 = 1, bahwa As3 ≡ h3h2-1 (mod p)  21 2.1-1 mod 7 2.1 mod 7
  2. Peggy mengirim victor Z, dimana Z = (x – rj) mod (p – 1)

Z = (5-3) mod 6 = 2

  1. Victor konfirmasi bahwa AZ ≡ Bhj-1 (mod p)

22 4.1-1 mod 7

≡ 4.1 mod 7

≡ 4 mod 7

≡ 4

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: