Mengamankan perhitungan multipartai dari jumlah 1 kali jumlah 0 dalam string bersama

Misalkan ada pihak , masing-masing dengan sedikit . Saya ingin menghitung penggandaan jumlah yang kali dari nol, yaitu, . $N>2$ $p_j$ $b_j\in{\{0,1\}}$ $R=(\sum{b_j})\times(N-\sum{b_j})$

Perhitungan harus aman dalam arti bahwa tidak ada pihak bisa belajar lebih banyak daripada hasil akhir . Sebagai contoh, tidak aman untuk melakukan jumlah yang aman, karena akan diketahui, dan jumlahnya sensitif dalam masalah saya. Jadi, apakah ada protokol perhitungan aman yang ada yang sesuai dengan permintaan? $R$ $\sum{b_j}$

Sunting: Angka dalam masalah besar, setidaknya lebih dari . Maka diperlukan perhitungan multipartai yang aman dan efisien. Protokol penjumlahan aman bisa efisien tetapi SMC generik seperti sirkuit boolean mungkin terlalu intensif komputasi. Jadi saya perlu protokol yang efisien. $N$ $1000$

cr.crypto-security security Richard
sumber

Anda mengetahui hasil kelayakan umum untuk perhitungan aman multi-pihak serta pekerjaan terkini tentang enkripsi sepenuhnya homomorfik? karena keduanya menyelesaikan masalah Anda.

Sasho Nikolov

Mungkin itu harus menjadi jawaban, @SashoNikolov

Suresh Venkat

@ Suresh saya pikir saya akan memberinya kesempatan untuk mengklarifikasi batasan tambahan, karena jika dia tahu tentang jumlah aman bisa dibilang dia harus tahu tentang hasil kelayakan.

Sasho Nikolov

Apakah masalahnya setara dengan menghitung secara aman min {∑b_j, N-∑b_j}? Jika demikian, fokus pada penggandaan sepertinya hanya merupakan gangguan bagi saya.

Tsuyoshi Ito

@TsuyoshiIto itu setara

Sasho Nikolov

Jawaban:

Jawaban ini adalah tentang solusi yang layak berdasarkan enkripsi homomorfik yang TIDAK sepenuhnya homomorfik, karena yang terakhir mungkin sangat tidak efisien (jika ada kriptosistem homomorfik sepenuhnya efisien yang sebanding dengan yang disediakan di bawah ini dalam hal efisiensi, saya akan senang untuk dengar tentang mereka).

Karena Anda hanya memerlukan satu perkalian, maka ada solusi yang berpotensi lebih murah daripada enkripsi homomorfik sepenuhnya: [1] dan [2]. Yang terakhir ini bekerja pada bit-dekomposisi input yang terenkripsi sehingga akan membutuhkan protokol bit-dekomposisi seperti [3] dan [6], tetapi yang pertama bekerja pada seluruh nilai. Hanya untuk kelengkapan, yang pertama telah diperluas untuk operand perkalian di [4], meskipun OP mungkin tidak membutuhkan ini. Solusi ini bersifat non-interaktif dan harus berfungsi dalam kasus dua pihak. $d$

Jika Anda memiliki lebih dari dua pihak dan dapat melakukan beberapa interaksi maka [5] menyediakan "gerbang multiplikasi aman" yang berpotensi lebih efisien dan memungkinkan jumlah perkalian yang tidak terbatas. Ini bekerja pada dasarnya dengan mengonversi nilai yang dienkripsi secara homomorfis menjadi semacam berbagi rahasia, melipatgandakan hasilnya (secara interaktif), kemudian mengubahnya kembali menjadi enkripsi homomorfik.

[1] Mengevaluasi Rumus 2-DNF pada Ciphertext

[2] Cryptocomputing non-interaktif untuk NC1

[3] Perhitungan Multi-partai Putaran-Konstan Tanpa Syarat untuk Kesetaraan, Perbandingan, Bit, dan Eksponensial

[4] Enkripsi Homomorfik Aditif dengan Multiplikasi d-Operand

[5] Komputasi Multipartai dari Enkripsi Homomorfik Ambang

[6] Konversi Biner yang Efisien untuk Nilai Terenkripsi Paillier

Mohammad Alaggan
sumber

Sejujurnya, saya gagal melihat hubungan jawaban ini dengan pertanyaan.

Tsuyoshi Ito

@TsuyoshiIto: Jawaban ini berisi daftar beberapa referensi yang dapat digunakan untuk menyediakan "perhitungan aman untuk perkalian", dan secara khusus dirancang untuk formula yang disediakan OP yang hanya mencakup satu perkalian. Ini juga mencantumkan metode yang relatif 'efisien' sesuai permintaan OP. Saya sebenarnya gagal melihat keberatan Anda sama sekali.

Mohammad Alaggan

Seperti yang saya tulis dalam komentar atas pertanyaan itu, perkalian tidak penting dalam pertanyaan itu. Judul pertanyaan itu salah.

Tsuyoshi Ito

Jadi judulnya harus dimodifikasi. Kalau tidak, mungkin seseorang akan datang nanti untuk pertanyaan ini berharap menemukan sesuatu yang mirip dengan jawaban saya.

Mohammad Alaggan

Jawaban baru (10/24): Saya pikir makalah berikut ini memberikan solusi yang elegan dan efisien untuk masalah Anda:

Mengevaluasi Rumus 2-DNF pada Ciphertext , Dan Boneh, Eu-Jin Goh, Kobbi Nissim, TCC 2005.

Mereka menunjukkan bagaimana membangun algoritma enkripsi kunci-publik dengan dua properti berguna berikut: $E(\cdot)$

Aditif homomorfik. Mengingat dan , siapa pun dapat menghitung . $E(x)$ $E(y)$ $E(x+y)$
Dapat bertambah banyak (sekali). Diberikan dan (tidak ada yang dihasilkan sebagai hasil dari operasi multiplikasi), siapa pun dapat menghitung . Anda dapat menggunakan hasil dalam operasi penjumlahan, tetapi Anda tidak dapat menggunakannya dalam operasi perkalian mana pun (hasil perkalian ternoda, dan nilai-nilai tercemar tidak dapat digunakan sebagai input untuk perkalian lain). $E(x)$ $E(y)$ $E(x \cdot y)$

Konsekuensinya adalah bahwa, diberi kuadrat multivariat polinomial , dan diberikan , siapa pun dapat menghitung enkripsi dari . Ini sangat berguna untuk situasi Anda. $\Psi(x_1,\dots,x_n)$ $E(x_1),\dots,E(x_n)$ $\Psi(x_1,\dots,x_n)$

Khususnya, dalam situasi Anda, kami dapat membentuk polinomial Perhatikan bahwa ini adalah polinomial multivarian kuadratik, sehingga mengingat semua , siapa pun dapat menghitung . Perhatikan juga bahwa , jadi kami mencoba menghitung dengan tepat nilai polinomial ini.

Ψ (b_{1}, b_{2}, \dots, b_{N}) = \sum_{i \neq j} [b_{i} (1 - b_{j})] .

$\Psi(b_1,b_2,\dots,b_N) = \sum_{i \ne j} [b_i (1-b_j)].$

E (b_{i})

$E(b_i)$

E (Ψ (b_{1}, \dots, b_{N}))

$E(\Psi(b_1,\dots,b_N))$

R = Ψ (b_{1}, \dots, b_{N})

$R=\Psi(b_1,\dots,b_N)$

Ini menyarankan protokol alami untuk masalah Anda, menggunakan versi ambang batas skema enkripsi dalam makalah yang dirujuk di atas:

Semua orang bersama-sama menghasilkan keypair publik / pribadi untuk versi ambang batas dari skema ini, sehingga kunci publik diketahui oleh semua orang tetapi kunci pribadi dibagikan di antara semua orang (itu membutuhkan kerja sama semua pihak untuk mendekripsi ciphertext yang dienkripsi di bawah kunci publik ini. ). Kunci publik disiarkan ke semua peserta. $N$ $N$
Setiap peserta menghitung dan menyiarkan ke semua peserta lainnya. Semua orang memeriksa bahwa ini telah dilakukan dengan jujur. $i$ $E(b_i)$ $E(b_i)$
Setiap peserta menghitung menggunakan properti homomorfik dari skema enkripsi ini dan pengetahuan tentang . Semua orang mengecek bahwa mereka mendapat nilai yang sama. $E(R) = E(\Psi(b_1,\dots,b_N))$ $E(b_1),\dots,E(b_N)$
Para peserta bersama-sama menggunakan protokol dekripsi ambang untuk memulihkan dari . (Perhatikan bahwa mereka hanya akan menerapkan protokol dekripsi ambang batas untuk ciphertext yang satu ini; peserta yang jujur akan menolak untuk berpartisipasi dalam mendekripsi ciphertext lainnya.) $N$ $R$ $E(R)$
Semua orang membuktikan entah bagaimana (mungkin melalui bukti ZK) bahwa mereka melakukan setiap langkah dengan benar.

Anda harus mengisi beberapa detail, tetapi saya yakin Anda dapat memperluas sketsa / garis besar ini untuk mendapatkan protokol yang akan menyelesaikan masalah Anda secara efisien dan aman.

Jawaban lama saya:

Saya masih akan mencari protokol multipartai yang aman untuk menghitung jumlah . $S = \sum_j b_j$

Satu-satunya cara yang kurang dari skema Anda adalah itu mengungkapkan satu bit tambahan: itu mengungkapkan apakah atau tidak. Apakah itu sedikit informasi penting dalam pengaturan Anda? $S<N/2$

Anda mengatakan jumlah sensitif dalam aplikasi Anda. Saya harap Anda sadar bahwa mengungkapkan nilai mengungkapkan hingga dua kemungkinan (yaitu, mengingat , kita dapat menghitung nilai sedemikian rupa sehingga ). $S$ $R$ $S$ $R$ $Q$ $S \in \{Q,N-Q\}$

Jika Anda benar-benar harus menyembunyikan informasi ini, berikut adalah pendekatan berbeda yang mungkin dapat Anda lakukan. Untuk setiap pasangan pihak , aman menghitung mana , adalah operasi xor, dan adalah semacam enkripsi aditif-homomorfik tambahan skema. Maka Anda mungkin dapat menghitung dari ini. Ada beberapa detail untuk dikerjakan dan model ancaman mungkin bukan yang Anda harapkan, tetapi mungkin Anda bisa membuat sesuatu seperti ini berhasil. $i,j$ $E(c_{i,j})$ $c_{i,j} = b_i \oplus b_j$ $\oplus$ $E$ $\sum_{i<j} c_{i,j}=R$

DW
sumber

itu ide yang sangat menarik. meskipun tidak menghasilkan produksi dengan tepat, menggunakan xor sebenarnya menyembunyikan info apakah 0 atau 1. Namun satu masalah, apakah xor dihitung dalam plaintext dalam skema? ada perhitungan aman untuk xor?

Richard

@Richard, pemikiran saya adalah bahwa Anda mungkin dapat menggunakan perhitungan aman dua pihak: party memiliki input , party memiliki input , dan mereka ingin bersama-sama menghitung manaIni dapat dilakukan (tanpa menghitung xor dalam plaintext) menggunakan metode standar untuk perhitungan aman 2-pihak. Namun, ada sesuatu yang halus yang berkaitan dengan model ancaman yang saya belum sepenuhnya memikirkan (bagaimana jika pihak adalah berbahaya tetapi partai tidak?), Dan ada akan perlu beberapa cara untuk kekuatan, katakanlah, pihak untuk menggunakan nilai sama di semua interaksi tersebut.

i

$i$

b_{i}

$b_i$

j

$j$

b_{j}

$b_j$

E (c_{i, j})

$E(c_{i,j})$

c_{i, j} = b_{i} \oplus b_{j} .

$c_{i,j}=b_i\oplus b_j.$

i

$i$

j

$j$

i

$i$

b_{i}

$b_i$