Enkripsi Homomorphic Penuh: Pengenalan dan Kasus Penggunaan

Lanjutan8/22/2024, 9:21:34 AM
Artikel ini bertujuan untuk memberikan gambaran umum yang lebih tinggi kepada pembaca tentang apa yang dapat digunakan oleh FHE dan skenario atau pengaturan yang berbeda yang memanfaatkan FHE. Pada blogpost yang akan datang, kami akan merinci lebih lanjut tentang jenis FHE (yang mempengaruhi jenis komputasi yang dapat kita lakukan) dan akhirnya jenis kompilator apa yang dapat kita temukan untuk menerjemahkan program kita menjadi operasi yang dapat dihitung menggunakan FHE.

Ketika seseorang memikirkan tentang enkripsi, penggunaan pertama yang terlintas dalam pikiran adalah enkripsi saat istirahat dan enkripsi selama pengiriman. Yang pertama memungkinkan untuk menyimpan beberapa data di hard drive terenkripsi, perangkat yang dapat dilepas, atau bahkan database cloud dan menawarkan jaminan bahwa hanya pemilik sah yang dapat melihat atau mengedit konten teks biasa. Enkripsi selama pengiriman menjamin bahwa data yang dikirimkan melalui Internet hanya dapat diakses oleh penerima yang ditunjuk, bahkan jika melewati router atau saluran publik. Kedua skenario ini bergantung pada enkripsi, dengan jaminan integritas tambahan bahwa data juga tidak dimanipulasi oleh penyerang jahat di antara mereka. Ini dikenal sebagai enkripsi yang terotentikasi: setelah data terenkripsi, tidak ada orang dalam rantai yang dapat menyimpulkan bit data apa pun (kerahasiaan) dan tidak ada yang dapat mengubah teks sandi tanpa terdeteksi (keutuhan/otentisitas).

Beberapa kasus penggunaan kolaboratif mengharuskan beberapa pemrosesan non-sepele diizinkan bahkan pada ciphertext. Ini adalah domain teknik pelestarian privasi, atau enkripsi yang digunakan, dengan enkripsi homomorfik sepenuhnya (FHE) menjadi salah satunya. Salah satu contohnya adalah pemungutan suara elektronik di cloud: pemilih dapat, misalnya, mengenkripsi surat suara mereka, kemudian beberapa entitas di tengah akan mengumpulkan semua surat suara untuk menghitung jumlah suara, dan hanya hasil akhir yang akan dipublikasikan. Sayangnya, dengan enkripsi yang diautentikasi, entitas di tengah perlu mendekripsi semua surat suara untuk melakukan perhitungan seperti itu, dan akan melihat suara individu dengan jelas, yang cukup rumit. Kita bisa, secara teori, mengocok surat suara (beberapa protokol e-voting benar-benar bergantung pada ini), tetapi, tidak seperti untuk surat suara kertas, mekanisme kriptografi tradisional yang menjamin integritas juga membuatnya lebih sulit untuk memutuskan tautan surat suara terenkripsi dari identitas pengirimnya. Dalam skema e-voting, seseorang dapat menambahkan dinding perangkat keras di sekitar entitas yang menghitung suara. Ini, misalnya, tujuan dari kantong-kantong eksekusi tepercaya. Kantong-kantong seperti itu akan membuat lebih sulit bagi penyerang untuk berinteraksi dengan entitas. Tetapi kemudian kegagalan dalam perangkat keras dapat membocorkan kunci dekripsi, dan, tidak seperti kesalahan perangkat lunak, kerentanan desain perangkat keras tidak dapat ditambal dengan mudah.

Untuk menangani kasus penggunaan seperti ini dan lainnya, kita dapat menggunakan Enkripsi Homomorfik Penuh (FHE). FHE adalah bentuk khusus dari enkripsi yang memungkinkan seseorang untuk menghitung fungsi pada teks sandi tanpa mendekripsi mereka, dan untuk mendapatkan enkripsi output fungsi secara langsung.

Sebagian besar waktu, fungsi f untuk dievaluasi adalah publik, sehingga urutan langkah-langkah pemrosesan untuk mengubah enkripsi f(x) adalah pengetahuan publik, dan dapat dilakukan di awan tanpa melibatkan rahasia apa pun.

Gambar ini menggambarkan 3 skenario untuk evoting: pada gambar terkiri, entitas tepercaya mengocok dan mendekripsi suara individu sebelum mempublikasikan hasilnya. Kita harus percaya pada entitas yang melakukan komputasi agar privasi pemilih terjaga dan suara terhitung dengan benar. Pada gambar tengah, Enklave Tepercaya, yang dipercaya untuk memberikan jaminan integritas dan privasi, digunakan untuk melakukan komputasi yang sama. Pada gambar kanan, digunakan enkripsi homomorfik: suara yang dienkripsi dapat ditambahkan (secara publik) sebelum hasilnya didekripsi. E( ) merupakan operasi enkripsi, sedangkan D( ) menunjukkan dekripsi.

FHE juga kompak, yang berarti bahwa ukuran bit dari ciphertext output dan upaya untuk mendekripsinya hanya bergantung pada jumlah bit dalam hasil plaintext. Hal ini tidak bergantung pada rantai perhitungan yang diterapkan. Hal ini tidak termasuk kriptosistem non-kompak yang sederhana yang hanya akan menggabungkan ciphertext masukan x dengan kode sumber f, dan membiarkan penerima melakukan semua pekerjaan dengan mendekripsi x dan kemudian menerapkan f.

Outsourcing FHE sering disajikan sebagai alternatif untuk enclave yang aman, berdasarkan pada kesulitan masalah matematika daripada pada hambatan praktis. Oleh karena itu, FHE benar-benar tidak rentan terhadap serangan samping pasif, atau korupsi lainnya dari host cloud. Bayangkan seseorang perlu mengoutsourcing beberapa komputasi, tetapi data tersebut sangat sensitif. Orang tersebut mungkin enggan menggunakan cloud VM jika orang lain dapat menjadi root pada mesin tersebut. Mereka mungkin juga ragu untuk menjalankannya di enclave seperti SGX, mengetahui bahwa CPU dan memori host cloud terus dipantau untuk beban, daya, suhu. Mungkin beberapa informasi dapat diekstraksi dari pengukuran ini. Orang tersebut mungkin merasa tenang dengan janji FHE bahwa mengekstraksi setiap bit informasi memerlukan pemecahan masalah matematika pasca-kuantum, independen dari jenis pengukuran apa pun yang dapat kami kumpulkan.

Jika kerahasiaan yang diberikan oleh skema mencegah penyerang membaca bit informasi tunggal tanpa kunci rahasia, homomorfisme penuh enkripsi memungkinkan sebaliknya, penyerang untuk membalikkan bit yang dihitung: dalam sebuah sirkuit, ini akan menjadi setara dengan serangan sisi-aktif saluran, di mana penyerang diberikan sinar laser ajaib yang dapat menargetkan setiap bit. Ini mungkin terdengar sangat menakutkan pada awalnya, tetapi dalam FHE serangan ini sesuai dengan eksekusi yang tidak jujur dari operasi homomorfik. Mereka dapat dihindari dengan menambahkan replikasi atau redundansi dalam komputasi.

FHE sering disajikan dalam gaya kunci publik. Ada:

  1. Sebuah kunci dekripsi: Ini adalah kunci utama dari kriptosistem, dari mana semua kunci lain dapat diturunkan. Kunci dekripsi biasanya dihasilkan secara lokal dan tidak pernah ditransmisikan, dan satu-satunya orang yang dapat mendekripsi sebuah sandi teks FHE adalah pemilik kunci dekripsi.
  2. Sebuah kunci enkripsi: Dalam mode kunci publik, ketika pihak yang memberikan sandi awal bukan pemilik kunci dekripsi, kunci berukuran sedang ini biasanya terdiri dari enkripsi acak nol. Karena FHE mendukung fungsi afinitas, ini cukup untuk mengenkripsi pesan apa pun.
  3. Sebuah kunci evaluasi: Kunci ini akan diberikan kepada pihak mana pun yang akan mengevaluasi fungsi pada teks sandi. Kunci ini juga aman untuk dipublikasikan atau ditransmisikan seperti kunci publik lainnya. Ukuran kunci evaluasi bervariasi dari kosong hingga sangat besar, tergantung pada apakah fungsi yang dievaluasi adalah linear atau sembarang.

Pemilik kunci dekripsi adalah pemilik rahasia paling sensitif dari kriptosistem. Orang ini bertanggung jawab untuk memastikan bahwa rangkaian operasi homomorfik yang dilakukan adalah sah dan bahwa hasil sandi teks akhir aman untuk didekripsi, dan kemudian mendekripsi hasil teks biasa. Jika operasi jahat diperkenalkan dalam rangkaian, kunci dekripsi berpotensi bocor pada saat dekripsi. Untungnya, operasi homomorfik dapat dilakukan secara publik dan diverifikasi.

Skenario FHE

Dalam bagian ini, kita akan menjelaskan beberapa skenario di mana FHE dapat digunakan, serta beberapa pro dan kontra dari setiap pengaturan.

Mode Outsourcing


Dalam gambar ini, simbol kunci oranye melambangkan kunci dekripsi (dan pemiliknya). Ciphertext FHE direpresentasikan oleh gembok dengan warna yang sama dengan kunci dekripsi. Pihak yang berkontribusi dengan data pribadi direpresentasikan oleh silinder: di sini, hanya Alice yang berkontribusi dengan data pribadi. Di pihak Bob, fungsi evaluasi dan kunci evaluasi adalah publik, dan perhitungan, digambarkan dengan kotak hijau, dapat dilakukan secara deterministik. Semua orang dapat melacak perhitungan dan mendeteksi jika ciphertext output yang diklaim salah.

Ini adalah kasus penggunaan pertama secara historis yang diterbitkan untuk FHE. Ini bertujuan untuk mengubah komputasi cloud menjadi komputasi pribadi yang analog dengan benteng aman, tetapi berdasarkan keamanan kriptografi bukan keamanan perangkat keras. Dalam pengaturan seperti itu, Alice memiliki beberapa data pribadi, tetapi memiliki kemampuan komputasi yang terbatas. Bob meniru sebuah contoh cloud dengan kekuatan komputasi yang jauh lebih besar. Bob tidak memberikan kontribusi dengan data pribadi tambahan apa pun. Alice dapat mengalihkan komputasi dengan mengenkripsi input, Bob kemudian mengevaluasi fungsi (publik) yang diinginkan secara homomorfik dan mengirimkan hasil terenkripsi kembali ke Alice.

Dengan kemampuan perangkat keras saat ini, mode outsourcing masih agak lambat untuk digunakan secara umum dalam praktek - kita biasanya dapat menghitung faktor overhead waktu eksekusi sebesar 1 juta dan overhead memori sebesar 1 ribu pada kasus penggunaan non-linear. Namun, perangkat keras FHE saat ini sedang dikembangkan untuk menutup kesenjangan, seperti yang Proyek DARPA DPRIVEatauCryptoLight.

Saat ini, mode outsourcing digunakan dalam praktik untuk kasus penggunaan PIR (Private Information Retrieval), di mana server (Bob) memiliki database publik yang besar, klien (Alice) mengeluarkan permintaan, dan indeks yang ditanyakan harus tetap privat. Skema PIR seperti ini sangat menguntungkan dari operasi yang terenkripsi homomorfik yang linear dan padat, sementara kedalaman perkalian kecil dari sirkuit menjaga biaya komputasi tetap dalam batas yang wajar.

Tabel ini merangkum kelebihan dan kekurangan dari mode outsourcing.

Mode Komputasi Dua Pihak

Gambar ini menggunakan kode warna yang sama seperti sebelumnya. Kali ini, Bob memberikan kontribusi pada komputasi dengan beberapa data pribadi. Komputasi di pihak Bob tidak lagi dapat diverifikasi secara publik, disimbolkan oleh sebuah kotak merah, mode ini seharusnya dibatasi pada kasus penggunaan yang jujur namun ingin tahu.

Dalam pengaturan baru ini, satu-satunya perbedaan adalah bahwa Bob berkontribusi pada komputasi dengan beberapa data pribadi. Dalam hal ini, FHE adalah solusi komputasi dua pihak yang baik, dengan komunikasi minimal, dan memberikan jaminan kuat pada sisi pencari: Bob tidak mengetahui apa pun tentang data Alice, dan Alice mengetahui hasil komputasi.

Salah satu aplikasi potensial untuk skenario ini adalah masalah jutawan, di mana Alice dan Bob adalah dua jutawan yang ingin tahu siapa yang lebih kaya tanpa mengungkapkan kekayaan mereka kepada pihak lain. Solusi untuk masalah ini digunakan dalam aplikasi e-commerce.

Mode Agregasi

Ini adalah penyempurnaan dari mode pengalihan, di mana data dari banyak peserta dapat disatukan secara kompak (dalam arti bahwa output tidak berkembang dengan jumlah peserta) dan dapat diverifikasi secara publik. Penggunaan khas meliputi pembelajaran federasi dan e-voting.

Mode Klien-Server

Pengaturan ini adalah penyempurnaan dari mode komputasi dua pihak, di mana pihak komputasi sekarang menyediakan layanan komputasi yang aman kepada beberapa klien, yang memiliki kunci rahasia mereka sendiri. FHE misalnya dapat digunakan sebagai layanan prediksi model pribadi (misalnya layanan ML dengan model dan input pribadi): server memiliki model pribadi (rahasia tetapi dalam teks biasa) dan setiap klien memiliki data mereka sendiri dan ingin menjalankan prediksi. Sebagai hasilnya, setiap klien mendapatkan prediksi terenkripsi mereka sendiri, dengan kunci rahasia mereka sendiri.

Bagaimana enkripsi homomorfik memastikan bahwa fungsi yang dihitung adalah sah?

Selalu lebih mudah menggunakan Enkripsi Homomorphic dalam skenario kolaboratif di mana setiap peserta memiliki insentif untuk mengikuti protokol dengan jujur. Misalnya, Enkripsi Homomorphic dapat digunakan untuk menghitung statistik antara dua entitas hukum dari grup yang sama di dua negara berbeda: regulasi seperti GDPR memungkinkan beberapa statistik untuk dipublikasikan, tetapi mencegah secara umum pengumpulan semua data individu di tempat yang sama. Dalam kasus ini, penggunaan Enkripsi Homomorphic memungkinkan dan semua peserta memiliki insentif untuk mengikuti protokol dengan jujur. Dalam skenario non-kolaboratif, cara termudah untuk memastikan bahwa fungsi yang relevan telah dihitung adalah dengan memperkenalkan redundansi. Misalnya, dalam skenario outsourcing dan agregasi, komputasi homomorfik sepenuhnya publik dan dapat dibuat deterministik. Selama dua entitas independen atau lebih memiliki hasil sandi keluaran yang sama persis, maka perhitungan tersebut benar dan hasilnya aman untuk didekripsi. Semakin banyak redundansi, semakin tinggi kepercayaan yang dapat kita miliki pada hasil, yang tentu saja merupakan trade-off dengan efisiensi.

Selain itu, ketika pihak komputasi memastikan hasil FHE dengan menandatangani digital ciphertext masukan dan keluaran, semua orang dapat melacak kembali komputasi FHE yang sama dan memeriksa apakah buktinya valid. Setiap upaya penipuan oleh pihak komputasi FHE dapat terungkap secara publik, dan terkait dengan sertifikat yang dapat diverifikasi secara publik yang mengekspos penipuan dan pelakunya - kami menyebut model semacam itu sebagai model keamanan kerahasiaan yang kuat.

tanda tangan fully homomorphicadalah cara lain untuk memverifikasi kebenaran suatu komputasi, tanpa memerlukan verifikator independen, namun umumnya memerlukan banyak sumber daya.

Bagaimana FHE memastikan penerima akhir hanya mendekripsi hasil akhir dan bukan variabel perantara?

Cara paling mudah untuk melakukannya adalah memastikan bahwa pemilik kunci dekripsi tidak memiliki akses ke teks sandi perantara apapun.

Dalam skenario dua pihak, atau dalam skenario klien-server, Alice mengenkripsi input, Bob melakukan komputasi pada teks sandi dan mengirimkan output terenkripsi kembali ke Alice, jelas bahwa Alice hanya akan dapat mendekripsi hasilnya, dia tidak memiliki akses ke variabel lainnya.

Dalam skenario penggabungan awan, seperti e-voting di mana banyak peserta mengirimkan surat suara yang dienkripsi di awan umum, teknik lain digunakan: kunci dekripsi pada umumnya tidak diberikan kepada satu penerima tunggal tetapi dibagi rahasia antara anggota otoritas dekripsi yang berbeda. Dalam hal ini, dekripsi hanya dapat dipicu pada satu kriptoteks tertentu dengan menjalankan komputasi multipihak, yang melibatkan komunikasi online antara anggota otoritas. Jika satu anggota menolak untuk mendekripsi kriptoteks, dekripsi menjadi tidak mungkin. Ini memastikan bahwa hanya kriptoteks yang disetujui oleh semua anggota otoritas yang dapat didekripsi.

Pilar-Pilar Enkripsi Homomorphic

Ada tiga jenis enkripsi homomorfik: enkripsi homomorfik parsial (PHE), enkripsi homomorfik tingkat (LHE), dan enkripsi homomorfik penuh (FHE). Enkripsi homomorfik parsial hanya memungkinkan kita menghitung seperangkat fungsi terbatas (misalnya hanya jumlah, hanya fungsi linear, hanya fungsi bilinear), sedangkan enkripsi homomorfik tingkat dan penuh dapat mengevaluasi sirkuit sembarang, atau, dengan kata lain, fungsi yang alirannya data independen. Untuk LHE, parameter kriptografis bergantung pada fungsi dan bertambah dengan kompleksitas sirkuit, yang pada gilirannya menghasilkan ciphertext dan kunci yang lebih besar. Skema FHE memungkinkan, untuk seperangkat parameter tertentu, dan dengan demikian untuk ukuran kunci dan ciphertext tertentu, kita mengevaluasi fungsi apa pun yang dapat direpresentasikan sebagai sirkuit dengan Gates aritmatika atau biner. Artinya, berbeda dengan LHE, meskipun sirkuit yang dievaluasi semakin besar, parameter skema (dan kunci dan ciphertext) tidak menjadi lebih besar.

Dengan kata lain, ketika pertanyaan diajukan apakah suatu sirkuit teks terbuka tertentu dapat dijalankan secara homomorfik, dan dengan biaya apa (dalam hal waktu dan penggunaan memori), PHE mungkin menjawab tidak untuk pertanyaan tersebut. LHE menjawab ya, tetapi mungkin menetapkan biaya yang sangat tinggi untuk sirkuit kompleks. FHE juga menjawab ya, dan, selain itu, menyediakan kunci, algoritma enkripsi dan dekripsi, dan bagaimana melakukan evaluasi homomorfik pada set Gates universal sebelum sirkuit teks terbuka bahkan ditentukan. Oleh karena itu, FHE adalah satu-satunya mode yang menjamin bahwa memori dan waktu eksekusi evaluasi homomorfik tetap proposional terhadap sirkuit teks terbuka asli. Untuk mencapai hal ini, semua skema FHE yang diketahui saat ini menggunakan sandi teks yang berisik yang semakin berisik saat komputasi dilakukan. Untuk menghindari kebisingan yang merembes ke dalam komputasi yang dilakukan dan menyebabkan kesalahan dekripsi, skema-skema ini secara teratur melakukan operasi yang cukup mahal yang disebut bootstrapping, yang mengurangi kebisingan kembali ke tingkat yang dapat dikelola. Lebih lanjut mengenai spesifik dari setiap jenis skema, tentang bootstrapping, dan tentang bagaimana meminimalkan kebisingan dan biaya lainnya dengan kompilator FHE, akan dijelaskan dalam posting blog kedua dalam seri ini!

Disclaimer:

  1. Artikel ini dicetak ulang dari [kriptografi], Semua hak cipta milik penulis asli [ Nicolas Gama dan Sandra Guasch]. Jika ada keberatan terhadap cetakan ulang ini, silakan hubungi Gate Belajartim, dan mereka akan menanganinya dengan segera.
  2. Penyangkalan Tanggung Jawab: Pandangan dan pendapat yang terdapat dalam artikel ini semata-mata merupakan pandangan penulis dan tidak merupakan nasihat investasi apa pun.
  3. Terjemahan artikel ke dalam bahasa lain dilakukan oleh tim Gate Learn. Kecuali disebutkan, menyalin, mendistribusikan, atau menjiplak artikel yang diterjemahkan dilarang.

Enkripsi Homomorphic Penuh: Pengenalan dan Kasus Penggunaan

Lanjutan8/22/2024, 9:21:34 AM
Artikel ini bertujuan untuk memberikan gambaran umum yang lebih tinggi kepada pembaca tentang apa yang dapat digunakan oleh FHE dan skenario atau pengaturan yang berbeda yang memanfaatkan FHE. Pada blogpost yang akan datang, kami akan merinci lebih lanjut tentang jenis FHE (yang mempengaruhi jenis komputasi yang dapat kita lakukan) dan akhirnya jenis kompilator apa yang dapat kita temukan untuk menerjemahkan program kita menjadi operasi yang dapat dihitung menggunakan FHE.

Ketika seseorang memikirkan tentang enkripsi, penggunaan pertama yang terlintas dalam pikiran adalah enkripsi saat istirahat dan enkripsi selama pengiriman. Yang pertama memungkinkan untuk menyimpan beberapa data di hard drive terenkripsi, perangkat yang dapat dilepas, atau bahkan database cloud dan menawarkan jaminan bahwa hanya pemilik sah yang dapat melihat atau mengedit konten teks biasa. Enkripsi selama pengiriman menjamin bahwa data yang dikirimkan melalui Internet hanya dapat diakses oleh penerima yang ditunjuk, bahkan jika melewati router atau saluran publik. Kedua skenario ini bergantung pada enkripsi, dengan jaminan integritas tambahan bahwa data juga tidak dimanipulasi oleh penyerang jahat di antara mereka. Ini dikenal sebagai enkripsi yang terotentikasi: setelah data terenkripsi, tidak ada orang dalam rantai yang dapat menyimpulkan bit data apa pun (kerahasiaan) dan tidak ada yang dapat mengubah teks sandi tanpa terdeteksi (keutuhan/otentisitas).

Beberapa kasus penggunaan kolaboratif mengharuskan beberapa pemrosesan non-sepele diizinkan bahkan pada ciphertext. Ini adalah domain teknik pelestarian privasi, atau enkripsi yang digunakan, dengan enkripsi homomorfik sepenuhnya (FHE) menjadi salah satunya. Salah satu contohnya adalah pemungutan suara elektronik di cloud: pemilih dapat, misalnya, mengenkripsi surat suara mereka, kemudian beberapa entitas di tengah akan mengumpulkan semua surat suara untuk menghitung jumlah suara, dan hanya hasil akhir yang akan dipublikasikan. Sayangnya, dengan enkripsi yang diautentikasi, entitas di tengah perlu mendekripsi semua surat suara untuk melakukan perhitungan seperti itu, dan akan melihat suara individu dengan jelas, yang cukup rumit. Kita bisa, secara teori, mengocok surat suara (beberapa protokol e-voting benar-benar bergantung pada ini), tetapi, tidak seperti untuk surat suara kertas, mekanisme kriptografi tradisional yang menjamin integritas juga membuatnya lebih sulit untuk memutuskan tautan surat suara terenkripsi dari identitas pengirimnya. Dalam skema e-voting, seseorang dapat menambahkan dinding perangkat keras di sekitar entitas yang menghitung suara. Ini, misalnya, tujuan dari kantong-kantong eksekusi tepercaya. Kantong-kantong seperti itu akan membuat lebih sulit bagi penyerang untuk berinteraksi dengan entitas. Tetapi kemudian kegagalan dalam perangkat keras dapat membocorkan kunci dekripsi, dan, tidak seperti kesalahan perangkat lunak, kerentanan desain perangkat keras tidak dapat ditambal dengan mudah.

Untuk menangani kasus penggunaan seperti ini dan lainnya, kita dapat menggunakan Enkripsi Homomorfik Penuh (FHE). FHE adalah bentuk khusus dari enkripsi yang memungkinkan seseorang untuk menghitung fungsi pada teks sandi tanpa mendekripsi mereka, dan untuk mendapatkan enkripsi output fungsi secara langsung.

Sebagian besar waktu, fungsi f untuk dievaluasi adalah publik, sehingga urutan langkah-langkah pemrosesan untuk mengubah enkripsi f(x) adalah pengetahuan publik, dan dapat dilakukan di awan tanpa melibatkan rahasia apa pun.

Gambar ini menggambarkan 3 skenario untuk evoting: pada gambar terkiri, entitas tepercaya mengocok dan mendekripsi suara individu sebelum mempublikasikan hasilnya. Kita harus percaya pada entitas yang melakukan komputasi agar privasi pemilih terjaga dan suara terhitung dengan benar. Pada gambar tengah, Enklave Tepercaya, yang dipercaya untuk memberikan jaminan integritas dan privasi, digunakan untuk melakukan komputasi yang sama. Pada gambar kanan, digunakan enkripsi homomorfik: suara yang dienkripsi dapat ditambahkan (secara publik) sebelum hasilnya didekripsi. E( ) merupakan operasi enkripsi, sedangkan D( ) menunjukkan dekripsi.

FHE juga kompak, yang berarti bahwa ukuran bit dari ciphertext output dan upaya untuk mendekripsinya hanya bergantung pada jumlah bit dalam hasil plaintext. Hal ini tidak bergantung pada rantai perhitungan yang diterapkan. Hal ini tidak termasuk kriptosistem non-kompak yang sederhana yang hanya akan menggabungkan ciphertext masukan x dengan kode sumber f, dan membiarkan penerima melakukan semua pekerjaan dengan mendekripsi x dan kemudian menerapkan f.

Outsourcing FHE sering disajikan sebagai alternatif untuk enclave yang aman, berdasarkan pada kesulitan masalah matematika daripada pada hambatan praktis. Oleh karena itu, FHE benar-benar tidak rentan terhadap serangan samping pasif, atau korupsi lainnya dari host cloud. Bayangkan seseorang perlu mengoutsourcing beberapa komputasi, tetapi data tersebut sangat sensitif. Orang tersebut mungkin enggan menggunakan cloud VM jika orang lain dapat menjadi root pada mesin tersebut. Mereka mungkin juga ragu untuk menjalankannya di enclave seperti SGX, mengetahui bahwa CPU dan memori host cloud terus dipantau untuk beban, daya, suhu. Mungkin beberapa informasi dapat diekstraksi dari pengukuran ini. Orang tersebut mungkin merasa tenang dengan janji FHE bahwa mengekstraksi setiap bit informasi memerlukan pemecahan masalah matematika pasca-kuantum, independen dari jenis pengukuran apa pun yang dapat kami kumpulkan.

Jika kerahasiaan yang diberikan oleh skema mencegah penyerang membaca bit informasi tunggal tanpa kunci rahasia, homomorfisme penuh enkripsi memungkinkan sebaliknya, penyerang untuk membalikkan bit yang dihitung: dalam sebuah sirkuit, ini akan menjadi setara dengan serangan sisi-aktif saluran, di mana penyerang diberikan sinar laser ajaib yang dapat menargetkan setiap bit. Ini mungkin terdengar sangat menakutkan pada awalnya, tetapi dalam FHE serangan ini sesuai dengan eksekusi yang tidak jujur dari operasi homomorfik. Mereka dapat dihindari dengan menambahkan replikasi atau redundansi dalam komputasi.

FHE sering disajikan dalam gaya kunci publik. Ada:

  1. Sebuah kunci dekripsi: Ini adalah kunci utama dari kriptosistem, dari mana semua kunci lain dapat diturunkan. Kunci dekripsi biasanya dihasilkan secara lokal dan tidak pernah ditransmisikan, dan satu-satunya orang yang dapat mendekripsi sebuah sandi teks FHE adalah pemilik kunci dekripsi.
  2. Sebuah kunci enkripsi: Dalam mode kunci publik, ketika pihak yang memberikan sandi awal bukan pemilik kunci dekripsi, kunci berukuran sedang ini biasanya terdiri dari enkripsi acak nol. Karena FHE mendukung fungsi afinitas, ini cukup untuk mengenkripsi pesan apa pun.
  3. Sebuah kunci evaluasi: Kunci ini akan diberikan kepada pihak mana pun yang akan mengevaluasi fungsi pada teks sandi. Kunci ini juga aman untuk dipublikasikan atau ditransmisikan seperti kunci publik lainnya. Ukuran kunci evaluasi bervariasi dari kosong hingga sangat besar, tergantung pada apakah fungsi yang dievaluasi adalah linear atau sembarang.

Pemilik kunci dekripsi adalah pemilik rahasia paling sensitif dari kriptosistem. Orang ini bertanggung jawab untuk memastikan bahwa rangkaian operasi homomorfik yang dilakukan adalah sah dan bahwa hasil sandi teks akhir aman untuk didekripsi, dan kemudian mendekripsi hasil teks biasa. Jika operasi jahat diperkenalkan dalam rangkaian, kunci dekripsi berpotensi bocor pada saat dekripsi. Untungnya, operasi homomorfik dapat dilakukan secara publik dan diverifikasi.

Skenario FHE

Dalam bagian ini, kita akan menjelaskan beberapa skenario di mana FHE dapat digunakan, serta beberapa pro dan kontra dari setiap pengaturan.

Mode Outsourcing


Dalam gambar ini, simbol kunci oranye melambangkan kunci dekripsi (dan pemiliknya). Ciphertext FHE direpresentasikan oleh gembok dengan warna yang sama dengan kunci dekripsi. Pihak yang berkontribusi dengan data pribadi direpresentasikan oleh silinder: di sini, hanya Alice yang berkontribusi dengan data pribadi. Di pihak Bob, fungsi evaluasi dan kunci evaluasi adalah publik, dan perhitungan, digambarkan dengan kotak hijau, dapat dilakukan secara deterministik. Semua orang dapat melacak perhitungan dan mendeteksi jika ciphertext output yang diklaim salah.

Ini adalah kasus penggunaan pertama secara historis yang diterbitkan untuk FHE. Ini bertujuan untuk mengubah komputasi cloud menjadi komputasi pribadi yang analog dengan benteng aman, tetapi berdasarkan keamanan kriptografi bukan keamanan perangkat keras. Dalam pengaturan seperti itu, Alice memiliki beberapa data pribadi, tetapi memiliki kemampuan komputasi yang terbatas. Bob meniru sebuah contoh cloud dengan kekuatan komputasi yang jauh lebih besar. Bob tidak memberikan kontribusi dengan data pribadi tambahan apa pun. Alice dapat mengalihkan komputasi dengan mengenkripsi input, Bob kemudian mengevaluasi fungsi (publik) yang diinginkan secara homomorfik dan mengirimkan hasil terenkripsi kembali ke Alice.

Dengan kemampuan perangkat keras saat ini, mode outsourcing masih agak lambat untuk digunakan secara umum dalam praktek - kita biasanya dapat menghitung faktor overhead waktu eksekusi sebesar 1 juta dan overhead memori sebesar 1 ribu pada kasus penggunaan non-linear. Namun, perangkat keras FHE saat ini sedang dikembangkan untuk menutup kesenjangan, seperti yang Proyek DARPA DPRIVEatauCryptoLight.

Saat ini, mode outsourcing digunakan dalam praktik untuk kasus penggunaan PIR (Private Information Retrieval), di mana server (Bob) memiliki database publik yang besar, klien (Alice) mengeluarkan permintaan, dan indeks yang ditanyakan harus tetap privat. Skema PIR seperti ini sangat menguntungkan dari operasi yang terenkripsi homomorfik yang linear dan padat, sementara kedalaman perkalian kecil dari sirkuit menjaga biaya komputasi tetap dalam batas yang wajar.

Tabel ini merangkum kelebihan dan kekurangan dari mode outsourcing.

Mode Komputasi Dua Pihak

Gambar ini menggunakan kode warna yang sama seperti sebelumnya. Kali ini, Bob memberikan kontribusi pada komputasi dengan beberapa data pribadi. Komputasi di pihak Bob tidak lagi dapat diverifikasi secara publik, disimbolkan oleh sebuah kotak merah, mode ini seharusnya dibatasi pada kasus penggunaan yang jujur namun ingin tahu.

Dalam pengaturan baru ini, satu-satunya perbedaan adalah bahwa Bob berkontribusi pada komputasi dengan beberapa data pribadi. Dalam hal ini, FHE adalah solusi komputasi dua pihak yang baik, dengan komunikasi minimal, dan memberikan jaminan kuat pada sisi pencari: Bob tidak mengetahui apa pun tentang data Alice, dan Alice mengetahui hasil komputasi.

Salah satu aplikasi potensial untuk skenario ini adalah masalah jutawan, di mana Alice dan Bob adalah dua jutawan yang ingin tahu siapa yang lebih kaya tanpa mengungkapkan kekayaan mereka kepada pihak lain. Solusi untuk masalah ini digunakan dalam aplikasi e-commerce.

Mode Agregasi

Ini adalah penyempurnaan dari mode pengalihan, di mana data dari banyak peserta dapat disatukan secara kompak (dalam arti bahwa output tidak berkembang dengan jumlah peserta) dan dapat diverifikasi secara publik. Penggunaan khas meliputi pembelajaran federasi dan e-voting.

Mode Klien-Server

Pengaturan ini adalah penyempurnaan dari mode komputasi dua pihak, di mana pihak komputasi sekarang menyediakan layanan komputasi yang aman kepada beberapa klien, yang memiliki kunci rahasia mereka sendiri. FHE misalnya dapat digunakan sebagai layanan prediksi model pribadi (misalnya layanan ML dengan model dan input pribadi): server memiliki model pribadi (rahasia tetapi dalam teks biasa) dan setiap klien memiliki data mereka sendiri dan ingin menjalankan prediksi. Sebagai hasilnya, setiap klien mendapatkan prediksi terenkripsi mereka sendiri, dengan kunci rahasia mereka sendiri.

Bagaimana enkripsi homomorfik memastikan bahwa fungsi yang dihitung adalah sah?

Selalu lebih mudah menggunakan Enkripsi Homomorphic dalam skenario kolaboratif di mana setiap peserta memiliki insentif untuk mengikuti protokol dengan jujur. Misalnya, Enkripsi Homomorphic dapat digunakan untuk menghitung statistik antara dua entitas hukum dari grup yang sama di dua negara berbeda: regulasi seperti GDPR memungkinkan beberapa statistik untuk dipublikasikan, tetapi mencegah secara umum pengumpulan semua data individu di tempat yang sama. Dalam kasus ini, penggunaan Enkripsi Homomorphic memungkinkan dan semua peserta memiliki insentif untuk mengikuti protokol dengan jujur. Dalam skenario non-kolaboratif, cara termudah untuk memastikan bahwa fungsi yang relevan telah dihitung adalah dengan memperkenalkan redundansi. Misalnya, dalam skenario outsourcing dan agregasi, komputasi homomorfik sepenuhnya publik dan dapat dibuat deterministik. Selama dua entitas independen atau lebih memiliki hasil sandi keluaran yang sama persis, maka perhitungan tersebut benar dan hasilnya aman untuk didekripsi. Semakin banyak redundansi, semakin tinggi kepercayaan yang dapat kita miliki pada hasil, yang tentu saja merupakan trade-off dengan efisiensi.

Selain itu, ketika pihak komputasi memastikan hasil FHE dengan menandatangani digital ciphertext masukan dan keluaran, semua orang dapat melacak kembali komputasi FHE yang sama dan memeriksa apakah buktinya valid. Setiap upaya penipuan oleh pihak komputasi FHE dapat terungkap secara publik, dan terkait dengan sertifikat yang dapat diverifikasi secara publik yang mengekspos penipuan dan pelakunya - kami menyebut model semacam itu sebagai model keamanan kerahasiaan yang kuat.

tanda tangan fully homomorphicadalah cara lain untuk memverifikasi kebenaran suatu komputasi, tanpa memerlukan verifikator independen, namun umumnya memerlukan banyak sumber daya.

Bagaimana FHE memastikan penerima akhir hanya mendekripsi hasil akhir dan bukan variabel perantara?

Cara paling mudah untuk melakukannya adalah memastikan bahwa pemilik kunci dekripsi tidak memiliki akses ke teks sandi perantara apapun.

Dalam skenario dua pihak, atau dalam skenario klien-server, Alice mengenkripsi input, Bob melakukan komputasi pada teks sandi dan mengirimkan output terenkripsi kembali ke Alice, jelas bahwa Alice hanya akan dapat mendekripsi hasilnya, dia tidak memiliki akses ke variabel lainnya.

Dalam skenario penggabungan awan, seperti e-voting di mana banyak peserta mengirimkan surat suara yang dienkripsi di awan umum, teknik lain digunakan: kunci dekripsi pada umumnya tidak diberikan kepada satu penerima tunggal tetapi dibagi rahasia antara anggota otoritas dekripsi yang berbeda. Dalam hal ini, dekripsi hanya dapat dipicu pada satu kriptoteks tertentu dengan menjalankan komputasi multipihak, yang melibatkan komunikasi online antara anggota otoritas. Jika satu anggota menolak untuk mendekripsi kriptoteks, dekripsi menjadi tidak mungkin. Ini memastikan bahwa hanya kriptoteks yang disetujui oleh semua anggota otoritas yang dapat didekripsi.

Pilar-Pilar Enkripsi Homomorphic

Ada tiga jenis enkripsi homomorfik: enkripsi homomorfik parsial (PHE), enkripsi homomorfik tingkat (LHE), dan enkripsi homomorfik penuh (FHE). Enkripsi homomorfik parsial hanya memungkinkan kita menghitung seperangkat fungsi terbatas (misalnya hanya jumlah, hanya fungsi linear, hanya fungsi bilinear), sedangkan enkripsi homomorfik tingkat dan penuh dapat mengevaluasi sirkuit sembarang, atau, dengan kata lain, fungsi yang alirannya data independen. Untuk LHE, parameter kriptografis bergantung pada fungsi dan bertambah dengan kompleksitas sirkuit, yang pada gilirannya menghasilkan ciphertext dan kunci yang lebih besar. Skema FHE memungkinkan, untuk seperangkat parameter tertentu, dan dengan demikian untuk ukuran kunci dan ciphertext tertentu, kita mengevaluasi fungsi apa pun yang dapat direpresentasikan sebagai sirkuit dengan Gates aritmatika atau biner. Artinya, berbeda dengan LHE, meskipun sirkuit yang dievaluasi semakin besar, parameter skema (dan kunci dan ciphertext) tidak menjadi lebih besar.

Dengan kata lain, ketika pertanyaan diajukan apakah suatu sirkuit teks terbuka tertentu dapat dijalankan secara homomorfik, dan dengan biaya apa (dalam hal waktu dan penggunaan memori), PHE mungkin menjawab tidak untuk pertanyaan tersebut. LHE menjawab ya, tetapi mungkin menetapkan biaya yang sangat tinggi untuk sirkuit kompleks. FHE juga menjawab ya, dan, selain itu, menyediakan kunci, algoritma enkripsi dan dekripsi, dan bagaimana melakukan evaluasi homomorfik pada set Gates universal sebelum sirkuit teks terbuka bahkan ditentukan. Oleh karena itu, FHE adalah satu-satunya mode yang menjamin bahwa memori dan waktu eksekusi evaluasi homomorfik tetap proposional terhadap sirkuit teks terbuka asli. Untuk mencapai hal ini, semua skema FHE yang diketahui saat ini menggunakan sandi teks yang berisik yang semakin berisik saat komputasi dilakukan. Untuk menghindari kebisingan yang merembes ke dalam komputasi yang dilakukan dan menyebabkan kesalahan dekripsi, skema-skema ini secara teratur melakukan operasi yang cukup mahal yang disebut bootstrapping, yang mengurangi kebisingan kembali ke tingkat yang dapat dikelola. Lebih lanjut mengenai spesifik dari setiap jenis skema, tentang bootstrapping, dan tentang bagaimana meminimalkan kebisingan dan biaya lainnya dengan kompilator FHE, akan dijelaskan dalam posting blog kedua dalam seri ini!

Disclaimer:

  1. Artikel ini dicetak ulang dari [kriptografi], Semua hak cipta milik penulis asli [ Nicolas Gama dan Sandra Guasch]. Jika ada keberatan terhadap cetakan ulang ini, silakan hubungi Gate Belajartim, dan mereka akan menanganinya dengan segera.
  2. Penyangkalan Tanggung Jawab: Pandangan dan pendapat yang terdapat dalam artikel ini semata-mata merupakan pandangan penulis dan tidak merupakan nasihat investasi apa pun.
  3. Terjemahan artikel ke dalam bahasa lain dilakukan oleh tim Gate Learn. Kecuali disebutkan, menyalin, mendistribusikan, atau menjiplak artikel yang diterjemahkan dilarang.
今すぐ始める
登録して、
$100
のボーナスを獲得しよう!