ZERO KNOWLEDGE PROOF OF A DISCRETE LOGARITHM (part1)

Jika kemarin yang dibahas adalah zero knowledge proof saja,,nah sekarang pembahasan lebih mendalam tentang zero knowledge of a Discrete Logarithm, yah secara postingan ini adalah tugas yang dikasi pak didik minggu lalu,,
sekelompok sama aji setiyo sukarno, awang darmawan, dan deny binsar,,kami mengerjakan tugas ini bersama(^_^),,hhe.
langsung aja buat penjelasan tentang ZKP of a Discrete Logarithm,..

maaf,,fotonya ga nyambung^^

Zero-Knowledge Proof diperkenalkan oleh Uriel Feige, Amos Fiat, dan Adi Shamir. Zero-Knowledge Proof merupakan suatu metode interactive dari suatu pihak untuk membuktikan pihak lain bahwa (biasanya matematika) statement dia adalah benar, tanpa menyatakan ke yang lain kejujuran dari statement tersebut.

Zero-Knowledge Proof harus memenuhi tiga sifat yaitu:

1. Completeness
2. Soundness
3. Zero-knowledge

Zero-Knowledge Proof of a Discrete Logarithm merupakan salah satu Zero-Knowledge Proof pada logaritma diskrit. Misal Peggy ingin membuktikan kepada Victor bahwa ia mengetahui sebuah nilai x yang memenuhi Ax ≡ B (mod p). Dimana p = prima, x = bil random yang relatif prima terhadap p. A, B dan p adalah publik, x adalah privat. 

Alur 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. 
4. 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. 
5. Untuk semua bit t, Victor mengkonfirmasi : – jika bi = 0, bahwa Ari ≡ hi (mod p) – jika bi = 1, bahwa Asi ≡ hihj-1 (mod p) 
6. Peggy mengirim victor Z, dimana Z = (x - rj) mod (p - 1) 
7. Victor konfirmasi bahwa AZ ≡ Bhj-1 (mod p) Probabilitas kemungkinan Peggy melakukan penipuan yaitu sebesar 2-t. 

Contoh Soal: Misalkan P=13, x=5, A=2, B=6  memenuhi persamaan Ax ≡ B (mod p). 

Alur Protokol : 

1. Peggy membangkitkan nilai acak r sebanyak t, dimana ri < p-1. r1 = 2 dan r2 = 3 
2. Peggy menghitung hi = Ari mod p, untuk semua nilai i, dan mengirimnya kepada Victor. H1 = 22 mod 13 = 4 H2 = 23 mod 13 = 8 
3. Peggy dan Victor membangkitkan t bit: b1,b2,b3,…,bt. Missal : b1 = 0 dan b2 = 1
4. Untuk semua bit t, Peggy melakukan : – Jika b1 = 0, dia mengirim r1 = 2 kepada Victor – Jika 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 13 = 0 5. Untuk semua bit t, Victor mengkonfirmasi : a. jika bi = 0, bahwa Ari ≡ hi (mod p)  22 ≡ 4 mod 13 b. jika bi = 1, bahwa Asi ≡ hihj-1 (mod p)  20 ≡ 8.8-1 mod 13 ≡ 1 mod 13 
5. Peggy mengirim victor Z, dimana Z = (x - rj) mod (p - 1)  Z = (5-3) mod 12 = 2 
6. Victor konfirmasi bahwa AZ ≡ Bhj-1 (mod p)  22 ≡ 6.8-1 mod 13 ≡ 6.5 mod 13 ≡ 30 mod 13 ≡ 4 mod 13 

yang jelas rumit banget, discrete logarithm aja rada2,,apalagi yang ini,,

hhe,,.semoga bisa bermanfaat^^