Jumat, 11 Juni 2010

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^^

Tidak ada komentar:

Poskan Komentar

terima kasi yah
madridista89

Daftar Blog Saya

Entri Populer