Kamis, 01 Juli 2010

SECURE MULTIPARTY COMPUTATION

Latar Belakang
Setiap orang memiliki data rahasia masing masing dan mereka mengharapkan orang lain yang tidak berkepentingan tidak mengetahuinya. Suatu saat terdapat suatu kondisi dimana setiap orang yang berada dalam satu grup misalnya, dituntut secara bersama-sama untuk melakukan perhitungan terhadap inputan rahasia dari masing-masing pihak. Akan tetapi tidak ada seorang pun yang dapat dipercaya untuk mengetahui seluruh inputan yang diberikan setiap anggota dalam suatu grup tersebut.
Untuk mengatasi masalah tersebut, biasa kita dapat menggunakan orang yang dipercaya yang bukan dalam grup tersebut untuk melakukan perhitungan, atau kita dapat juga menggunakan protokol secure multiparty computation.

Secure Multiparty Computation
Secure multiparty computation ialah protokol, dimana sejumlaah orang dalam satu grup dapat memperoleh dan menghiting secara bersama sama beberapa fungsi dari banyak variable dengan suatu cara yang special. Hasil dari fungsi tersebut pada akhirnya akan diketahui oleh seluruh anggota grup, tetapi tidak satupun dari mereka yang mengetahui input yang dimasukkan oleh anggota yang lain dalam fungsi tersebut.
Protokol – 1
Bagaimana sejumlah orang dalam suatu grup dapat menghitung rata-rata dari gaji mereka jika setiap anggota dalam grup tersebut tidak mengetahui gaji anggota yang lain. Dibawah ini merupakan protokol untuk menjawab pertanyaan diatas, yaitu :
a. Alice menambahkan suatu angka random rahasia ke gajinya, mengenkrip hasilnya tersebut dengan public key Bob dan mengirimkannya ke Bob.
b. Bob mendekrip hasil dari Alice dengan private key-nya. Dia menambahkan gajinya ke nilai yang didapat dari Alice, mengenkrip hasilnya dengan public key Carol dan mengirimkannya ke Carol.
c. Carol mendekrip hasil dari Bob dengan private key-nya. Dia menambahkan gajinya ke nilai yang didapat dari Bob, mengenkrip hasilnya dengan public key Dave dan mengirimkannya ke Dave.
d. Dave mendekrip hasil dari Carol dengan private key-nya. Dia menambahkan gajinya ke nilai yang didapat dari Carol, mengenkrip hasilnya dengan public key Alice dan mengirimkannya ke Alice.
e. Alice mendekrip hasil dari Dave dengan private key-nya. Mengurangi angka random dari step (a) untuk mendapatkan jumlah gaji seluruhnya.
f. Alice membagi hasilnya tersebut dengan jumlah anggota dan mengumumkan hasilnya.
Protokol ini mengasumsikan bahwa setiap orang dapat dipercaya kejujurannya, mereka mungkin merasa aneh, tetapi tetap mengikuti protocol tersebut. Jika beberapa partisipan berbohong tentang gajinya, maka rata-rata yang didapat akan salah. Masalah yang lebih serius adalah Alice dapat salah merepresentasikan hasilnya ke setiap orang. Dia dapat mengurangi beberapa angka yang dia suka pada step (e). Alice dapat dicegah dari tindakan demikian dengan memaksanya komitmen terhadap angka randomnya menggunakan skema bit-commitment, tetapi ketika dia membuka angka randomnya pada akhir protocol, Bob dapat mengetahui gaji Alice.
Protocol – 2
Alice dan Bob sedang berada di restoran. Mereka mempunyai anggapan siapakah di antara mereka yang usianya lebih tua. Akan tetapi, keduanya tidak saling memberitahu usia masing-masing. Mereka membisikkan berapa usia mereka kepada pihak yang terpercaya dan netral, misal pramusaji, yang bertindak sebagai seseorang yang membandingkan nilai dari usia Alice dan Bob lalu memberitahukan hasilnya kepada keduanya.
Protokol tersebut mempunyai dua permasalahan. Pertama, pramusaji tidak memiliki kemampuan berhitung dengan baik apabila jumlah partisipan lebih dari dua orang bahkan banyak. Kedua, apabila Alice dan Bob sangat menjaga kerahasiaan informasi, maka mereka akan memaksa pramusaji untuk memasukkan kepalanya dalam wadah berisi air, khawatir jika mereka memberitahukan kepada pramusaji yang mungkin terkontaminasi minuman keras.
Kriptografi kunci publik memberikan solusi yang lebih baik (jauh dari violent solution). Terdapat protokol sebagai berikut :
a. Alice mengetahui sebuah nilai a
b. Bob mengetahui sebuah nilai b
c. Alice dan Bob menentukan a < b, dalam hal ini Alice tidak mendapatkan tambahan informasi nilai b, dan Bob juga tidak mendapatkan tambahan informasi nilai a
d. Alice dan Bob diyakinkan terhadap suatu validitas (kebenaran) komputasi.
Protokol ini tidak terlindungi dari serangan active cheaters. Tidak ada yang dapat menghentikan salah satu pihak melakukan kecurangan yaitu memberikan informasi (usia) yang palsu. Apabila Bob adalah computer program yang mengeksekusi protokol secara blindly, maka Alice dapat memperkirakan usia Bob dengan executing protokol berulang kali. Misal, Alice memberikan nilai usianya sebesar 60, setelah menganalisis bahwa dia lebih tua dari Bob, maka Alice execute kembali dengan nilai 30 dan ternyata analisis menunjukkan bahwa Bob lebih tua. Alice execute kembali dengan nilai 45. Hal ini dilakukan terus-menerus hingga mendapatkan pendekatan nilai dari usia Bob.
Dengan asumsi jika partisipan tidak melakukan actively cheat, maka protokol ini dapat dilakukan dengan multiple participants.
Protocol – 3
Pada protokol ini, akan dianalogikan sebagai Secure Multiparty Dating Service. Apabila Alice dan Bob telah share fetish yang sama, maka mereka akan menemukan kebahagiaan (berjodoh). Akan tetapi jika mereka tidak melakukan share fetish yang sama, maka mereka dapat meminta perusahaan tersebut untuk merahasiakan informasi dari fetish tersebut.
Bagaimana protokol ini bekerja ?
a. Alice melakukan hash fetish ke dalam tujuh digit string menggunakan one-way-function.
b. Alice menjadikan tujuh digit string sebagai nomor teleponnya, lalu melakukan panggilan di nomor telepon tersebut dan meninggalkan pesan kepada Bob. Jika tidak ada jawaban, maka Alice melakukan one-way function secara terus-menerus hingga ada orang lain yang memberi jawaban.
c. Alice memberitahu Bob frekuensi dia melakukan one-way function terhadap fetish miliknya.
d. Bob melakukan hash fetish miliknya sebanyak frekuensi yang dilakukan oleh Alice dan melakukan hal yang sama dilakukan oleh Alice.
sumber

Tidak ada komentar:

Posting Komentar

terima kasi yah
madridista89

Daftar Blog Saya

Entri Populer