Terapkan operasi homomorfik pada data terenkripsi besar
Saat ini bereksperimen pada enkripsi homomorfik menggunakan pustaka PALISADE .
Saya ingin menerapkan operasi sederhana seperti penambahan dan perkalian pada input terenkripsi yang besar. Misalnya input A[3200]dan input B[4096]kedua vektor / array nilai int dienkripsi. Dengan dua masukan tersebut Enc(A)dan Enc(B)saya ingin menerapkan perkalian:
EvalMult(Enc(A[0]), Enc(B[42]))
*0 and 42 denoting the indexes of the corresponding inputs
** no SIMD needed
Sejauh yang saya ketahui, implementasi dari persyaratan yang dijelaskan di atas dapat diselesaikan dengan dua cara berbeda:
Kemas input dalam satu ciphertext (seperti SIMD) dan untuk operasi dia yang dapat saya gunakan
EvalIndexAt()untuk mendapatkan nilai yang benar dari input terenkripsi.Enkripsi setiap nilai dari A dan B secara terpisah.
Saya tidak begitu yakin solusi apa yang dijelaskan yang akan menjadi yang terbaik dalam hal efisiensi . Pendekatan pertama memiliki keunggulan utama ini bahwa hanya satu proses enkripsi untuk seluruh input yang diperlukan tetapi ini datang dengan kerugian bahwa saya selalu harus mengakses elemen yang benar menggunakan EvalAtIndex()metode ini dan semakin besar input semakin lambat komputasi yang EvalAtIndexKeyGen()didapat. (Setidaknya di mesin saya)
Pendekatan kedua tampaknya lebih cocok karena EvalAtIndex()tidak diperlukan tetapi datang dengan biaya mengenkripsi setiap nilai secara terpisah yang membutuhkan waktu yang cukup lama.
Ada rekomendasi pemikiran?
Jawaban
Terima kasih atas pertanyaannya
Manfaat utama dari pendekatan # 1 (SIMD) adalah Anda dapat melakukan penjumlahan dan perkalian vektor (dari 4096 atau lebih bilangan bulat / bilangan real) menggunakan satu penjumlahan atau perkalian homomorfik (sangat efisien). Rotasi (disebut EvalAtIndexdalam PALISADE) adalah operasi tambahan yang memungkinkan seseorang mengakses indeks individu atau melakukan penjumlahan yang efisien (seperti pada produk dalam), perkalian matriks, dll. Pendekatan ini juga memiliki faktor ekspansi ciphertext yang jauh lebih kecil (sebesar 4096x atau lebih) daripada pendekatan # 2. Umumnya opsi # 1 lebih disukai dalam praktik (dan saya tidak dapat memikirkan kasus penggunaan nyata di mana saya ingin pergi dengan opsi # 2).
Untuk meminimalkan biaya perkalian, mungkin Anda bisa mengemas vektor dalam blok yang berdekatan sehingga Anda memerlukan satu rotasi untuk satu blok. Sebagai contoh,
EvalMult(Enc(A[0:5]),Enc(B[42:47))
Teknik lain yang dapat Anda gunakan adalah EvalFastRotation(hanya tersedia untuk CKKS dan BGVrns di PALISADE v1.10.x). Jika Anda memerlukan beberapa rotasi ciphertext yang sama, Anda dapat menghitung sebelumnya untuk ciphertext, dan kemudian menggunakan rotasi yang lebih murah (manfaat terbesar dicapai untuk peralihan kunci BV) - lihathttps://gitlab.com/palisade/palisade-development/-/blob/master/src/pke/examples/advanced-real-numbers.cpp sebagai contoh.
Ada juga cara untuk meminimalkan jumlah kunci yang akan dihasilkan jika Anda memerlukan beberapa rotasi (hanya menghitung secara kasar akar kuadrat dari jumlah rotasi yang diperlukan), misalnya, menggunakan teknik langkah bayi langkah raksasa yang dijelaskan di https://eprint.iacr.org/2018/244 (teknik ini dapat diterapkan di aplikasi berbasis PALISADE Anda).
Anda juga dapat menggunakan urutan khusus untuk mengemas vektor jika pola untuk melakukan perkalian diketahui (dengan cara ini rotasi Anda akan menyiapkan beberapa blok melintasi vektor menggunakan operasi rotasi tunggal). Rotasi bersifat siklis (membungkus) di CKKS dan BGVrns ketika # slot teks biasa (ukuran batch) sama dengan ring dimension/ 2. Jika Anda memiliki vektor yang lebih kecil dari itu, Anda selalu dapat menggandakan / mereplikasi vektor kecil sebanyak yang diperlukan untuk mengisi ring dimension/ 2.
Singkatnya, peningkatan efisiensi terbesar dapat dicapai jika Anda memikirkan masalah Anda dalam kaitannya dengan vektor mirip SIMD. Kemudian Anda dapat merumuskan kembali masalah / model Anda untuk memanfaatkan sepenuhnya perangkat yang disediakan HE. Di satu sisi, ini mirip dengan pemrograman menggunakan instruksi vektor, misalnya, AVX, atau pemrograman berorientasi matriks (seperti di MATLAB).