Graph isomorphism and Zero-Knowledge Proof of a Discrete Logarithm

1. Graph isomorphism

1. PENGERTIAN

Definisi. Graf sederhana G₁ = (V₁, E₁) dan G₂ = (V₂, E₂) disebut isomorfis jika ada sebuah fungsi bijektif (satu-ke-satu dan onto) dari V₁ ke V₂ dengan sifat bahwa a bertetangga dengan b pada G₁ jika dan hanya jika f(a) bertetangga dengan f(b) pada G₂, untuk seluruh a dan b pada V₁.

Fungsi f seperti itu disebut isomorfisme. Dengan kata lain, G₁ dan G₂ adalah isomorfis jika simpul-simpulnya dapat diurutkan dengan suatu cara sedemikian rupa sehingga matriks kedekatan dan dan adalah identik. Secara visual, dua buah graf, G₁dan G₂, 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, G₁ dan G₂. protokol akan meyakinkan Victor bahwa Peggy mengetahui keisomorfisan tersebut:

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

Jika Peggy tidak mengetahui keisomorfisan antara G₁ dan G₂, Peggy tidak dapat menghasilkan graf H yang isomorfis untuk keduanya. Peggy dapat menghasilkan sebuah graf yang isomorfis untuk G₁ atau yang isomorfis to G₂. 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 G₁ dan G₂. 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 G₁ dan G₂ dari jawaban Peggy. Dalam setiap round, Victor menerima sebuah permutation acak yang baru pada H, bersamaan dgn keisomorfisan antara H dan G₁ atau G_2.

2. 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.

2. Soundness

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

3. 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 r_i < p-1.
2. Peggy menghitung h_i = A^ri mod p, untuk semua nilai i, dan mengirimnya kepada Victor.
3. Peggy dan Victor membangkitkan t bit: b₁,b₂,b₃,…,b_t.

4. Untuk semua bit t, Peggy melakukan :
   • Jika b_i = 0, dia mengirim r_i kepada Victor
   • Jika b_i = 1, dia mengirimkan s_i = (r_i-r_j) mod (p-1), dimana j nilai terkecil untuk b_j=1.
5. Untuk semua bit t, Victor mengkonfirmasi :
   • jika b_i = 0, bahwa A^ri ≡ h_i (mod p)
   • jika bi = 1, bahwa A^si ≡ hihj^-1 (mod p)
6. Peggy mengirim victor Z, dimana Z = (x - r_j) mod (p - 1)
   
7. 
   
   
   Victor konfirmasi bahwa A^Z ≡ Bh_j^-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 A^x ≡ B (mod p).

Protokol :

1. Peggy membangkitkan nilai acak r sebanyak t, dimana r_i < p-1.
   r₁ = 2, r₂ = 3,dan r₃ = 4

2. Peggy menghitung h_i = A^ri mod p, untuk semua nilai i, dan mengirimnya kepada Victor.

h₁ = 2² mod 7 = 4

h₂ = 2³ mod 7 = 1

h₃ = 2⁴ mod 7 = 2

3. Peggy dan Victor membangkitkan t bit: b₁,b₂,b₃,…,b_t.

Missal :

b₁ = 0, b₂ = 1, dan b₃ = 1

4. Untuk semua bit t, Peggy melakukan :

• b₁ = 0, dia mengirim r₁ = 2 kepada Victor
• b₂ = 1, dia mengirimkan s_i = (r_i-r_j) mod (p-1), dimana j nilai terkecil untuk b_j=1.

S₂ = (r₂-r₂) mod p = 3-3 mod 6 = 0

• b₃ = 1, dia mengirimkan

S₃ = (r₃-r₂) mod p = 4-3 mod 6 = 1

5. Untuk semua bit t, Victor mengkonfirmasi :
   1. b₁ = 0, bahwa A^r1 ≡ h₁ (mod p) = 2² ≡ 4 mod 7
   2. b₂ = 1, bahwa A^s2 ≡ h₂h₂^-1 (mod p) = 2⁰ ≡ 1.1^-1 mod 7 ≡ 1 mod 7
   3. b₃ = 1, bahwa A^s3 ≡ h₃h₂^-1 (mod p) = 2¹ ≡ 2.1^-1 mod 7 ≡ 2.1 mod 7
6. Peggy mengirim victor Z, dimana Z = (x - r_j) mod (p - 1)
   

Z = (5-3) mod 6 = 2

5. Victor konfirmasi bahwa A^Z ≡ Bh_j^-1 (mod p)

            2² ≡ 4.1^-1 mod 7

             ≡ 4.1 mod 7

             ≡ 4 mod 7

             ≡ 4