Menjalankan algoritma pada data dari jarak jauh dan memastikan jawaban belum dirusak

8

Saya sudah memikirkan masalah komputasi / kripto / database khusus ini selama bertahun-tahun dan saya hanya ingin tahu apakah sudah ada solusi untuk itu. Sejujurnya saya bahkan tidak tahu bidang apa masalah ini sebenarnya milik.

Singkatnya: orang A memiliki daftar data, orang lain (B) memiliki algoritma yang memberikan setiap item pada daftar ini skor dan kemudian menjumlahkan semua skor ini untuk memberikan skor keseluruhan untuk seluruh daftar. Bagaimana kita dapat menjalankan algoritme pada daftar data sehingga data dijaga sangat aman (lebih disukai tidak pernah meninggalkan orang A) tetapi agar orang B dapat memastikan algoritme berjalan dengan benar dan tidak dirusak.

Berikut ini sebuah contoh: Anna dan Bob tinggal di sebuah desa besar. Anna memiliki daftar di komputernya tentang semua hal yang telah dia lakukan di desa, baik dan buruk. Bob telah membuat algoritma penilaian yang sangat sederhana untuk daftar tersebut, yang berjalan pada setiap item dalam daftar dan memberikan skor dan kemudian menambahkan semua angka-angka ini untuk memberi Anna skor akhir. Skor ini membuat Bob tahu betapa bermanfaatnya Anna bagi komunitas desa dan khusus untuk pendapat Bobs. (Ini lebih dari contoh karena ini sebenarnya sistem yang ingin saya buat)

Namun Anna tidak ingin memberi Bob daftar, karena kemudian ia memiliki akses ke info berpotensi memalukan di sana (semua orang memiliki kerangka di lemari mereka). Namun Bob tidak percaya Anna untuk menjalankan algoritmanya sendiri, karena ia mungkin hanya berbohong dan memberi tahu Bob bahwa nilainya sangat tinggi sehingga Bob lebih mungkin untuk membantunya.

Ada beberapa solusi yang sudah saya pikirkan, tetapi semua memiliki masalah:

A. Temukan orang acak untuk mengambil data dan menjalankan algoritme dan mengirim skor kembali, tetapi mungkin sulit untuk memastikan bahwa orang acak ini tidak mengenal Anna dan mencoba membantunya atau membuat salinan data dan kemudian mencoba untuk melacaknya kembali dan memeras Anna.

B. Biarkan Anna menjalankan algoritme tetapi entah bagaimana menyandikan kode cek ke dalam skor, misalnya, alih-alih menilai suatu peristiwa sebagai 1 nilai sebagai 1,0000000000797, sedemikian rupa sehingga Bob kemudian dapat menggunakan ini sebagai kode centang untuk melihat apakah yang diberikan skornya benar. Namun pemeriksaan ini juga dapat disalahgunakan oleh Bob untuk menunjukkan hal-hal spesifik apa yang telah dilakukan Anna. Saya juga dapat membayangkan sistem seperti itu akan sepele untuk merekayasa balik sehingga Anna dapat memberikan skor palsu dengan kode centang yang benar, mengingat Anna harus memiliki akses penuh ke algoritma Bob untuk menjalankannya.

C. Desa menciptakan server yang aman untuk mengambil data dan algoritma seperti itu dan menjalankannya bersama. Namun Anna dan Bob sama-sama tidak terlalu memercayai siapa pun untuk melakukan ini dan tidak membuat salinan data atau memodifikasi skor, kecuali ada arsitektur yang secara fundamental aman untuk melakukannya. Saya juga lebih suka ini menjadi sistem P2P.

cryptography security protocols encryption Robin A
sumber
Bagaimana jika algoritma penilaian Bob, misalnya, representasi biner dari apakah Anna telah melakukan atau belum melakukan masing-masing hal dalam daftar? (Jadi 1 * <apakah Anna melakukan hal 1> + 2 * <apakah Anna melakukan hal 2> + 4 * <apakah Anna melakukan hal 3> ...) Kemudian Bob akan memiliki akses ke data Anna hanya berdasarkan pada output dari algoritma penilaian.
TLW
1
Saya ingin tahu apakah enkripsi homomorfik memiliki permainan di sini? Ini memecahkan jenis masalah sebaliknya - memungkinkan beberapa sistem lain melakukan perhitungan data tanpa mempelajari nilai-nilai yang bekerja dengannya.
Alan Wolfe
@ TTW Saya tidak sepenuhnya yakin jika saya mengerti apa yang Anda katakan ... siapa yang menjalankan algoritma dalam situasi ini dan masih bagaimana kita bisa memastikan nilai akhir tidak dicegat dan dirusak?
Robin A

Jawaban:

9

Dalam komunitas crypto, tugas ini dikenal sebagai perhitungan yang didelegasikan , atau delegasi yang dapat diverifikasi. Anda ingin membiarkan server ("cloud") melakukan pekerjaan untuk Anda, tetapi Anda juga ingin cloud memberi Anda beberapa bukti bahwa itu benar-benar melakukan perhitungan (dan tidak hanya menampilkan output acak, dan melarikan diri) dengan uangmu).

Pointer, dari atas kepala saya, adalah "Delegasi perhitungan: bukti interaktif untuk muggle" (Goldwasser, Kalai, dan Rothblum, J. ACM (62), 2015). Solusi lain mungkin ada, lihat ke dalam.

Ran G.
sumber
1

Ada bidang enkripsi homomorfik baru yang umumnya sesuai dengan kebutuhan Anda:

Enkripsi homomorfik adalah bentuk enkripsi yang memungkinkan perhitungan dilakukan pada ciphertext, sehingga menghasilkan hasil terenkripsi yang, ketika didekripsi, cocok dengan hasil operasi yang dilakukan pada plaintext.

Entitas yang memproses tidak dapat mengetahui "apa pun" tentang cyphertext, hanya muncul sebagai data acak, hanya dapat merusak perhitungan, dan klien perlu beberapa cara untuk mendeteksi / mempertahankan terhadap data / perhitungan yang rusak. ini dapat dilakukan dengan pesan digest dan komputasi toleran kesalahan .

Enkripsi homomorfik hanya diperlihatkan sebagai kemungkinan secara teori agak baru-baru ini sehingga lebih dalam tahap konseptual dan tampaknya tidak banyak diimplementasikan dalam praktik sejauh ini, tetapi akhirnya idenya adalah bahwa itu mungkin muncul sebagai kemampuan (misalnya mirip dengan layanan standar lainnya seperti virtualisasi) pada kelompok komputasi berstandar besar mis. Amazon ECC atau mesin komputasi google .

vzn
sumber
Ini tidak menjawab pertanyaan yang diajukan. Enkripsi homomorfik tidak (dengan sendirinya) memungkinkan B untuk memverifikasi bahwa algoritma berjalan dengan benar dan data tidak dirusak. Enkripsi homomorfik hanya menjamin kerahasiaan, bukan integritas, tetapi pertanyaannya adalah tentang integritas.
DW
pertanyaannya adalah tentang "menjalankan suatu algoritma pada data dari jarak jauh" yang merupakan alasan utama dari enkripsi homomorfik, dan jawaban alamat yang secara langsung bersama dengan kekhawatiran tambahan dari gangguan mana pesan pesan & alamat teknik komputasi toleran kesalahan.
vzn