Saya mengambil kursus CS355 (Kriptografi Tingkat Lanjut) di Stanford beberapa waktu lalu. Kami diajar oleh tiga mahasiswa PhD Dan, Dima Kogan, Florian Tramer dan Saba Eskandarian. Ketiga dosen PhD tersebut masing-masing mempunyai ciri khas dan arah penelitiannya juga sangat berbeda. Dima berfokus pada teknologi perlindungan privasi PIR (Private Information Retri), Florian berfokus pada penelitian ML dan blockchain, dan Saba berfokus pada bukti tanpa pengetahuan.
Kursus CS355 mencakup hampir semua konten di bidang kriptografi dari zaman dahulu hingga sekarang. Dari fungsi satu arah yang paling awal (Fungsi Satu Arah), hingga persamaan elips (ECC) dan Pemasangan, dan terakhir ke beberapa MPC yang lebih populer, pengetahuan nol, pengambilan informasi pribadi (PIR), algoritme yang sepenuhnya homomorfik, dll. dalam beberapa tahun terakhir. Karena kelas baru saja berakhir dua hari yang lalu, saya menyusun serangkaian catatan sementara isi pengetahuannya masih dalam ingatan saya yang dangkal. Isi kursusnya sangat menarik, sisa isinya akan saya bagikan kepada Anda nanti jika saya punya waktu ~
Dalam edisi ini, kita akan membahas tentang Enkripsi Homomorfik Sepenuhnya (FHE) yang baru-baru ini populer dan teknologi Enkripsi berbasis Lattice yang menyertainya.
Apa itu enkripsi yang sepenuhnya homomorfik?
Saya yakin teman-teman sudah banyak yang mendengar yang namanya Fully Homomorphic Encryption (FHE). Dalam beberapa tahun terakhir, semakin banyak topik tentang perlindungan privasi pribadi, dan serangkaian teknologi aplikasi kriptografi termasuk enkripsi homomorfik juga telah dipopulerkan secara luas.
Untuk lebih memahami topik ini, saya ingin memperkenalkan secara singkat definisi enkripsi homomorfik sepenuhnya.
Tinjauan sistem enkripsi
Sebelum kita mulai, mari kita tinjau sistem enkripsi paling tradisional.
Kita semua tahu bahwa jika Anda ingin membangun sistem enkripsi, Anda sering kali memerlukan kunci. Melalui kunci ini, kita dapat mengenkripsi informasi teks biasa menjadi teks tersandi di salah satu ujung, dan kemudian menggunakan kunci tersebut untuk mengubah teks tersandi kembali ke tampilan aslinya di ujung lainnya. Tanpa adanya Key ini maka orang lain akan sulit mengetahui informasi apa saja yang kita sampaikan.
Ilustrasi di atas pada dasarnya menunjukkan gambaran keseluruhan dari semua sistem enkripsi umum. Semua sistem enkripsi, jika kita menggunakan metode deskripsi yang lebih formal, pasti melakukan tiga hal:
Teman yang tahu sesuatu tentang algoritma enkripsi pasti tahu yang umum Beberapa algoritma enkripsi, seperti AES, RSA, dll. Semua orang juga harus tahu bahwa secara umum sistem enkripsi dibagi menjadi dua jenis: sistem enkripsi simetris dan sistem enkripsi asimetris. Tiga langkah yang kami jelaskan di sini sebenarnya dapat diterapkan pada sistem enkripsi apa pun. Jika simetris, maka kunci yang digunakan untuk enkripsi dan dekripsi adalah sama. Jika sistemnya asimetris, maka kunci publik digunakan untuk enkripsi, dan kunci privat yang berbeda digunakan untuk dekripsi.
Dalam penelitian kriptografi, setiap kali kita melihat definisi suatu sistem baru, kita sering kali harus menyatakan properti yang seharusnya dimiliki sistem tersebut.
Arti penting dari keamanan semantik adalah bahwa pengamat tidak dapat membedakan dua pesan terenkripsi. Jadi jika penyusup menguping jaringan dan melihat informasi terenkripsi yang saya kirim, selama sistem enkripsi yang saya gunakan aman secara semantik, maka saya yakin penyusup tidak dapat memperoleh informasi apa pun tentang konten terenkripsi dari teks tersandi.
Setelah memenuhi dua properti di atas, sistem enkripsi menjadi baik.
### Enkripsi Homomorfik: Properti Khusus yang Tidak Disengaja
Setelah memahami apa itu sistem enkripsi, kita dapat memperhatikan ciphertext yang terlihat seperti kode kacau yang dihasilkan secara acak. Kita semua tahu bahwa kita tidak akan mendapatkan informasi apapun hanya dengan melihat ciphertext itu sendiri. Tapi apakah ini berarti jika tidak ada kunci dan hanya ciphertext saja, kita tidak bisa berbuat apa-apa?
Kita semua tahu jawabannya: tidak juga.
Untuk sifat ini, kami menyebutnya homomorfisme aditif. Ini berarti bahwa ciphertext terenkripsi mempertahankan hubungan aljabar yang halus dengan teks asli sebelumnya. Jika kita menjumlahkan ciphertextnya, kita bisa mendapatkan ciphertext baru yang dienkripsi dengan menjumlahkan teks aslinya. Dengan cara yang sama, dapat disimpulkan bahwa algoritma enkripsi homomorfik aditif juga ada. Kita dapat mengalikan ciphertext yang dihasilkan dengan algoritma perkalian homomorfik, kemudian memperoleh ciphertext yang sesuai dengan hasil perkalian teks aslinya. Dalam keseluruhan proses, kita tidak perlu mengetahui informasi apa pun terkait kunci tersebut, kita cukup menggabungkan ciphertext yang terlihat seperti kode acak yang kacau.
Misalnya: Sistem pemungutan suara anonim
Selanjutnya, mari kita berikan contoh untuk menjelaskan dengan jelas kepraktisan enkripsi homomorfik.
Kita semua tahu seperti apa pemungutan suara online - jika bos sebuah perusahaan ingin memulai gelombang pemungutan suara, pilih apakah perusahaan tersebut harus mengadopsi sistem 996. Kemudian atasan dapat meminta TI untuk menyiapkan server dan membiarkan karyawan menyampaikan pilihannya: pilih 0 berarti tidak mau, dan pilih 1 berarti mau. Setelah periode pemungutan suara terakhir, bos dapat menjumlahkan semua suara. Jika total suara akhir melebihi setengah jumlah karyawan, perusahaan akan memulai 996.
Mekanisme pemungutan suara ini tampaknya sangat sederhana, tetapi ada masalah privasi yang besar: jika bos ingin semua karyawannya menjadi 996, tetapi dia hanya dengan sengaja memulai pemungutan suara ini untuk memancing penegakan hukum untuk melihat karyawan mana yang tidak mau bekerja lembur, maka bos Diam-diam dia bisa mempercayakan adiknya untuk menguping di Internet, mencatat pilihan yang diajukan oleh setiap karyawan, dan akhirnya melihat siapa yang memilih 0. Akibatnya karyawan sangat takut dan tidak berani mengungkapkan perasaannya.
Jika kita dapat menggunakan algoritma enkripsi homomorfik aditif, maka masalah ini dapat diselesaikan dengan mudah.
Tentu saja sistem ini masih sangat belum lengkap, misalnya departemen IT bisa langsung membantu bos mendekripsi suara semua orang dan mencatatnya ke dalam dokumen. Ada alat kriptografi lain yang dapat membantu kita mengatasi masalah ini. Karena alasan ruang, penjelasan lebih lanjut tidak akan diberikan di sini.
Namun pada titik ini, kita seharusnya sudah bisa merasakan kekuatan algoritma enkripsi homomorfik. Kita dapat memahaminya seperti ini: melalui algoritma enkripsi homomorfik, pengguna dapat melakukan semacam komputasi proxy yang aman (Secure Delegated Computation) dengan server jarak jauh (cloud) yang tidak tepercaya. Pengguna dapat menggunakan teknologi enkripsi homomorfik untuk mengenkripsi masukan pribadi sensitif mereka dan mempercayakannya ke cloud. Kemudian cloud dapat melakukan perhitungan tingkat tertentu pada data terenkripsi, dan akhirnya mendapatkan hasil terenkripsi yang diinginkan pengguna, dan mengembalikannya ke cloud.user. Terakhir, pengguna dapat menggunakan kunci dekripsi untuk membuka hasilnya. Sepanjang keseluruhan perjanjian, pihak yang didelegasikan (cloud) tidak pernah dapat melihat informasi berguna apa pun terkait masukan pribadi.
### Klasifikasi sistem enkripsi homomorfik
Setelah memahami secara kasar dua sifat homomorfik paling dasar, konsep lainnya menjadi sangat mudah dipahami. Dari perspektif sistematis, sistem enkripsi homomorfik secara kasar dibagi menjadi empat kategori: homomorfisme parsial, homomorfisme perkiraan, homomorfisme penuh seri terbatas, dan homomorfisme lengkap.
Selanjutnya, mari kita lihat definisi spesifik dari setiap kategori secara bergantian.
Enkripsi Homomorfik Sebagian
Tahap paling dasar dari enkripsi homomorfik disebut enkripsi homomorfik parsial, yang didefinisikan sebagai teks tersandi yang hanya memiliki satu sifat homomorfik. Tahap ini mencakup dua mode homomorfisme aditif dan homomorfisme perkalian yang kami jelaskan di atas.
Kami mendapatkan ciphertext yang sesuai dengan perkalian kedua pesan ini! Ini adalah properti homomorfisme perkalian. Kita dapat terus melapiskan ciphertext baru di atas ciphertext ini, sehingga kita bisa mendapatkan perkalian antar ciphertext.
Perkiraan Enkripsi Homomorfik (Enkripsi Agak Homomorfik)
Seperti yang kami katakan di paragraf sebelumnya, jika kita ingin mengalikan masukan pribadi dan mendapatkan kombinasi linier di antara masukan tersebut, algoritma enkripsi homomorfik parsial sederhana (RSA, ElGamal) tidak dapat diselesaikan. Jadi kita perlu sampai ke tahap berikutnya.
Tahap selanjutnya dari enkripsi homomorfik parsial adalah kira-kira enkripsi homomorfik, yang selangkah lebih dekat ke enkripsi homomorfik penuh yang ingin kita capai. Jika kita memiliki algoritma enkripsi yang kurang lebih homomorfik, maka kita dapat menghitung penjumlahan dan perkalian pada ciphertext secara bersamaan. Namun perlu diperhatikan bahwa karena tahap ini mendekati homomorfik, maka jumlah penjumlahan dan perkalian yang dapat dilakukan sangat terbatas, dan fungsi F yang dapat dihitung juga berada dalam rentang yang terbatas.
Tidak banyak contoh umum tentang enkripsi homomorfik pada tahap ini. Jika kita mengatakan contoh yang paling mudah dipahami, itu adalah algoritma enkripsi grup siklik berdasarkan pasangan.
Di atas kita membahas secara singkat algoritma enkripsi ElGamal berdasarkan kelompok siklik biasa. Kita semua tahu bahwa algoritma ini bersifat additive homomorphic, artinya dapat memperoleh kombinasi linier antara ciphertext yang berubah-ubah. Faktanya, pada beberapa gugus siklik khusus, kita juga dapat menemukan beberapa sifat homomorfisme perkalian yang lemah.
Keterbatasan ini membuktikan bahwa sistem tersebut mendekati homomorfik, karena kita tidak dapat menghitung fungsi F dengan logika dan kedalaman sembarang.
Enkripsi Homomorfik Tingkat Penuh
Setelah mencapai tahap berikutnya, kita selangkah lebih dekat ke tujuan homomorfisme penuh.
Tahap ini disebut enkripsi homomorfik seri terbatas. Pada tahap ini, kita sudah dapat melakukan kombinasi penjumlahan dan perkalian apa pun pada ciphertext tanpa ada batasan berapa kali.
Enkripsi Homomorfik Sepenuhnya (FHE)
Setelah banyak panggilan, akhirnya sampai pada enkripsi homomorfik penuh (FHE) yang kita tunggu-tunggu.
Seperti namanya, sistem enkripsi yang sepenuhnya homomorfik tidak memiliki batasan pada metode perhitungan. Kita dapat menggabungkan ciphertext secara sewenang-wenang untuk membentuk ciphertext baru tanpa kunci, dan teks ciphertext baru, terlepas dari kompleksitas komputasinya, dapat dikembalikan dengan sempurna ke teks aslinya.
Ketika kita mencapai tahap ini, perhitungan agen aman yang disebutkan sebelumnya menjadi layak dilakukan. Jika kita dapat menemukan sistem enkripsi homomorfik penuh yang lebih efisien, kita dapat dengan aman mem-proxy semua penghitungan lokal ke cloud tanpa membocorkan data apa pun!
Definisi sistem enkripsi yang sepenuhnya homomorfik
Sebelum memulai pembahasan sejarah sistem homomorfik penuh di bawah ini, kita dapat mendefinisikan secara sistematis definisi formal sistem homomorfik penuh. Sistem enkripsi yang sepenuhnya homomorfik memiliki total empat algoritma:
## Tinjauan sejarah enkripsi sepenuhnya homomorfik
Sebelum mulai mempelajari bagaimana algoritma enkripsi homomorfik sepenuhnya diimplementasikan, ada baiknya kita melihat bagaimana konsep enkripsi homomorfik sepenuhnya muncul.
Konsep FHE (sepenuhnya homomorfik) sebenarnya diusulkan pada akhir tahun 1970-an. Pada tahun 1978, Rivest, Adleman dan Dertouzos, beberapa nama besar di bidang kriptografi, pertama kali menyebutkan dalam makalah mereka On Data Banks and Privacy Homomorphisms gagasan tentang sistem yang dapat melakukan perhitungan tertentu pada ciphertext dan secara tidak langsung beroperasi pada teks aslinya. Kemudian, ide ini dirangkum kembali dan diberi nama enkripsi homomorfik sepenuhnya.
Terlihat bahwa konsep enkripsi homomorfik penuh telah diusulkan sejak lama. Anehnya, pada tahun 1976, dua tahun sebelum makalah tersebut diterbitkan, protokol pertukaran kunci Diffle-Hellman baru saja diusulkan! Hal ini menunjukkan bahwa imajinasi para ahli kriptografi masih sangat kaya.
Ketika konsep FHE diusulkan, seluruh komunitas akademis tergerak olehnya dan memulai pencarian selama puluhan tahun, mencoba menemukan algoritma sempurna dengan sifat homomorfik sepenuhnya. Namun selama beberapa dekade terakhir, orang telah mencoba semua pilihan yang ada, namun mereka tidak dapat menemukan pilihan yang memenuhi semua syarat untuk menjadi homomorfik sepenuhnya dan keamanannya dapat dibuktikan dengan mudah.
Hingga tahun 2009, PhD Craig Gentry yang sedang kuliah di Stanford tiba-tiba mendapat ide dan menerobos kesulitan algoritma FHE. Dalam tesis doktoralnya, ia memberikan sistem enkripsi homomorfik sepenuhnya yang masuk akal dan aman untuk pertama kalinya! Sistem ini didasarkan pada asumsi kisi ideal. Sistem sepenuhnya homomorfik yang diusulkan oleh Gentry09 sering disebut sebagai sistem enkripsi homomorfik penuh generasi pertama.
Dalam makalah Gentry, ia juga menyebutkan konsep penting yang disebut Bootstrapping. Bootstrapping adalah teknik pemrosesan khusus untuk ciphertext, setelah diproses dapat “menyegarkan” ciphertext dengan noise yang mendekati nilai kritis menjadi ciphertext baru dengan noise yang sangat rendah. Melalui Bootstrapping, noise dari sistem seri hingga tidak akan pernah melebihi nilai kritisnya, sehingga menjadi sistem yang sepenuhnya homomorfik. Dengan cara ini, kita dapat menghitung F secara homomorfik dengan ukuran berapa pun.
Setelah terobosan besar Gentry, seluruh lingkaran kriptografi kembali menjadi gila, dan semua orang mulai berebut untuk menemukan sistem homomorfik penuh yang lebih efisien dan serbaguna berdasarkan ide yang diajukan oleh Gentry.
Pada tahun 2011, dua orang besar, Brakerski dan Vaikuntanathan, mengusulkan sistem enkripsi homomorfik baru, yang didasarkan pada Learning With Errors (LWE), asumsi lain dari enkripsi kisi. Pada tahun yang sama, Brakerski, Gentry dan Vaikuntanathan menyelesaikan sistem tersebut dan menerbitkannya secara resmi. Sistem homomorfik sepenuhnya yang mereka temukan disebut sistem BGV. Sistem BGV adalah sistem enkripsi homomorfik tingkat terbatas, namun dapat diubah menjadi sistem homomorfik sepenuhnya melalui Bootstrapping. Dibandingkan dengan sistem yang dikemukakan oleh Gentry09, sistem BGV menggunakan asumsi LWE yang lebih realistis. Secara umum, kami menyebut sistem BGV sebagai sistem enkripsi homomorfik generasi kedua.
Pada tahun 2013, Gentry kembali lagi. Gentry, Sahai dan Waters telah meluncurkan sistem enkripsi GSW yang sepenuhnya homomorfik. Sistem GSW mirip dengan BGV karena memiliki sifat homomorfik seri terbatas yang didasarkan pada asumsi LWE yang lebih sederhana dan dapat sepenuhnya homomorfik melalui Bootstrapping. Kami biasanya menyebut sistem GSW sebagai sistem enkripsi homomorfik generasi ketiga.
Setelah tahun 2013, cryptosphere pada dasarnya berkembang pesat. Berdasarkan sistem homomorfik penuh tiga generasi yang asli, berbagai desain baru telah muncul, didedikasikan untuk mengoptimalkan dan mempercepat efisiensi pengoperasian sistem BGV dan GSW. IBM mengembangkan perpustakaan komputasi homomorfik sumber terbuka HElib berdasarkan sistem BGV, dan berhasil memindahkannya ke platform seluler utama. Pada saat yang sama, ada proyek open source lain TFHE yang juga patut diperhatikan. TFHE didasarkan pada sistem GSW, dengan berbagai optimasi dan akselerasi ditambahkan, dan sekarang sangat terkenal.
Selain mengembangkan perpustakaan tradisional yang sepenuhnya homomorfik, banyak tim juga mempelajari cara mempercepat penghitungan algoritme enkripsi sepenuhnya homomorfik dengan lebih baik melalui perangkat keras heterogen seperti GPU, FPGA, dan ASIC. Misalnya, cuFHE adalah sistem enkripsi homomorfik penuh akselerasi GPU berbasis CUDA yang terkenal.
Dari sudut pandang saat ini, sudah 11 tahun sejak Gentry membuka pintu sistem homomorfik sepenuhnya. Saat ini, penelitian tentang FHE sedang booming di industri, dan banyak orang mempelajari sistem yang sepenuhnya homomorfik dari berbagai perspektif dan persyaratan aplikasi. Hingga saat ini, kami telah memiliki berbagai metode implementasi FHE yang layak, namun yang masih diupayakan adalah efisiensi pengoperasian sistem FHE. Mengambil perpustakaan FHE mutakhir saat ini sebagai contoh, menghitung beberapa logika yang relatif sederhana secara homomorfik pada platform seluler mungkin memerlukan waktu paling sedikit puluhan milidetik dan paling lama puluhan detik. Satuan waktu ini sangat lambat untuk sistem komputer.
Bagaimana membuat sistem FHE berjalan lebih efisien pada platform heterogen masih menjadi misteri yang belum terpecahkan. Jika masalah ini terpecahkan, maka mengubah semua penghitungan komputer menjadi homomorfik sepenuhnya dan meminta agen melakukan penghitungan di cloud pihak ketiga akan menjadi masa depan yang mudah.
Hubungan antara FHE dan MPC
Sebelum mengakhiri artikel, saya ingin menambahkan sedikit penjelasan tentang hubungan FHE dan MPC. MPC adalah singkatan dari Secure Multi-Party Computation, yang merupakan komputasi multi-pihak yang tepercaya. Hal ini biasanya berarti bahwa banyak pihak memiliki masukan pribadi mereka sendiri dan tidak ingin mengungkapkannya kepada orang lain, namun mereka ingin menggunakan masukan mereka sendiri untuk menghitung fungsi F bersama-sama dan membagikan hasil penghitungannya.
MPC sebenarnya merupakan bidang yang sangat terkenal dan telah dipelajari sejak lama. Sejak kriptografer Yao Qizhi meluncurkan Garbled Circuits-nya pada abad terakhir, bidang MPC telah mendapat pengakuan luas dan banyak terobosan. Sekarang kami telah memiliki banyak perpustakaan MPC yang dapat digunakan, dan juga memiliki efisiensi pengoperasian tertentu.
Teman-teman yang mengetahui MPC mungkin memiliki banyak pertanyaan setelah melihat sejarah sulit dari sistem enkripsi yang sepenuhnya homomorfik: Mengapa enkripsi yang sepenuhnya homomorfik tidak dapat digantikan langsung oleh protokol MPC?
Memang benar bahwa protokol MPC dapat sepenuhnya menggantikan protokol FHE. Kita hanya perlu menggunakan input pengguna dan pribadi sebagai pihak dalam suatu protokol, dan kemudian menggunakan server komputasi proxy jarak jauh sebagai pihak lain, yang memenuhi persyaratan untuk pelaksanaan protokol MPC.Hanya melalui interaksi tertentu, komputasi proxy dapat dilakukan terealisasi Dan server tidak dapat melihat input pribadi.
Namun ada satu hal yang sangat penting yang telah kita abaikan: karena MPC bersifat interaktif, pengguna dan server perlu menghitung dan berkomunikasi bersama untuk menyelesaikan protokol. Hal ini bertentangan dengan persyaratan paling mendasar dari komputasi agen FHE. Jika pengguna harus tetap online sepanjang waktu untuk menyelesaikan perjanjian dan juga membayar sebagian dari daya komputasi, maka sebenarnya perhitungan tersebut tidak "diproxy" sama sekali, dan kedua belah pihak hanya melakukan lebih banyak perhitungan demi keamanan informasi. . Hal ini juga menjelaskan mengapa bidang MPC telah membuat terobosan besar, namun bidang FHE masih belum diketahui, karena kedua sistem tersebut menyelesaikan masalah yang sangat berbeda.
## Pemberhentian berikutnya: Sistem enkripsi GSW yang sepenuhnya homomorfik
Melihat hal ini, setiap orang pasti memiliki pemahaman yang sangat mendalam tentang sistem enkripsi yang sepenuhnya homomorfik.
Pemberhentian selanjutnya, kita dapat mempelajari tentang sistem enkripsi homomorfik GSW yang disebutkan di atas. Meskipun ini adalah generasi ketiga dari sistem yang sepenuhnya homomorfik, menurut saya di antara tiga sistem Gentry09, BGV, dan GSW, GSW adalah yang memiliki asumsi paling sedikit, struktur paling sederhana, dan paling mudah dipahami. Dan saat ini sudah banyak perpustakaan open source (seperti TFHE) yang dibangun berdasarkan sistem GSW.
Karena alasan ruang, kami akan mengakhiri artikel ini di sini. Pada artikel selanjutnya, kita akan mempelajari terlebih dahulu dasar-dasar sistem GSW: sistem enkripsi berbasis kisi dan masalah LWE. Setelah masalah LWE dipahami, masalah yang dipecahkan oleh GSW menjadi sangat jelas.
Lihat Asli
Halaman ini mungkin berisi konten pihak ketiga, yang disediakan untuk tujuan informasi saja (bukan pernyataan/jaminan) dan tidak boleh dianggap sebagai dukungan terhadap pandangannya oleh Gate, atau sebagai nasihat keuangan atau profesional. Lihat Penafian untuk detailnya.
Eksplorasi awal enkripsi homomorfik sepenuhnya: definisi dan tinjauan sejarah FHE
Penulis: Steven Yue
Saya mengambil kursus CS355 (Kriptografi Tingkat Lanjut) di Stanford beberapa waktu lalu. Kami diajar oleh tiga mahasiswa PhD Dan, Dima Kogan, Florian Tramer dan Saba Eskandarian. Ketiga dosen PhD tersebut masing-masing mempunyai ciri khas dan arah penelitiannya juga sangat berbeda. Dima berfokus pada teknologi perlindungan privasi PIR (Private Information Retri), Florian berfokus pada penelitian ML dan blockchain, dan Saba berfokus pada bukti tanpa pengetahuan.
Kursus CS355 mencakup hampir semua konten di bidang kriptografi dari zaman dahulu hingga sekarang. Dari fungsi satu arah yang paling awal (Fungsi Satu Arah), hingga persamaan elips (ECC) dan Pemasangan, dan terakhir ke beberapa MPC yang lebih populer, pengetahuan nol, pengambilan informasi pribadi (PIR), algoritme yang sepenuhnya homomorfik, dll. dalam beberapa tahun terakhir. Karena kelas baru saja berakhir dua hari yang lalu, saya menyusun serangkaian catatan sementara isi pengetahuannya masih dalam ingatan saya yang dangkal. Isi kursusnya sangat menarik, sisa isinya akan saya bagikan kepada Anda nanti jika saya punya waktu ~
Dalam edisi ini, kita akan membahas tentang Enkripsi Homomorfik Sepenuhnya (FHE) yang baru-baru ini populer dan teknologi Enkripsi berbasis Lattice yang menyertainya.
Apa itu enkripsi yang sepenuhnya homomorfik?
Saya yakin teman-teman sudah banyak yang mendengar yang namanya Fully Homomorphic Encryption (FHE). Dalam beberapa tahun terakhir, semakin banyak topik tentang perlindungan privasi pribadi, dan serangkaian teknologi aplikasi kriptografi termasuk enkripsi homomorfik juga telah dipopulerkan secara luas.
Untuk lebih memahami topik ini, saya ingin memperkenalkan secara singkat definisi enkripsi homomorfik sepenuhnya.
Tinjauan sistem enkripsi
Sebelum kita mulai, mari kita tinjau sistem enkripsi paling tradisional.
Kita semua tahu bahwa jika Anda ingin membangun sistem enkripsi, Anda sering kali memerlukan kunci. Melalui kunci ini, kita dapat mengenkripsi informasi teks biasa menjadi teks tersandi di salah satu ujung, dan kemudian menggunakan kunci tersebut untuk mengubah teks tersandi kembali ke tampilan aslinya di ujung lainnya. Tanpa adanya Key ini maka orang lain akan sulit mengetahui informasi apa saja yang kita sampaikan.
Dalam penelitian kriptografi, setiap kali kita melihat definisi suatu sistem baru, kita sering kali harus menyatakan properti yang seharusnya dimiliki sistem tersebut.
Arti penting dari keamanan semantik adalah bahwa pengamat tidak dapat membedakan dua pesan terenkripsi. Jadi jika penyusup menguping jaringan dan melihat informasi terenkripsi yang saya kirim, selama sistem enkripsi yang saya gunakan aman secara semantik, maka saya yakin penyusup tidak dapat memperoleh informasi apa pun tentang konten terenkripsi dari teks tersandi.
Setelah memenuhi dua properti di atas, sistem enkripsi menjadi baik.
Setelah memahami apa itu sistem enkripsi, kita dapat memperhatikan ciphertext yang terlihat seperti kode kacau yang dihasilkan secara acak. Kita semua tahu bahwa kita tidak akan mendapatkan informasi apapun hanya dengan melihat ciphertext itu sendiri. Tapi apakah ini berarti jika tidak ada kunci dan hanya ciphertext saja, kita tidak bisa berbuat apa-apa?
Kita semua tahu jawabannya: tidak juga.
Untuk sifat ini, kami menyebutnya homomorfisme aditif. Ini berarti bahwa ciphertext terenkripsi mempertahankan hubungan aljabar yang halus dengan teks asli sebelumnya. Jika kita menjumlahkan ciphertextnya, kita bisa mendapatkan ciphertext baru yang dienkripsi dengan menjumlahkan teks aslinya. Dengan cara yang sama, dapat disimpulkan bahwa algoritma enkripsi homomorfik aditif juga ada. Kita dapat mengalikan ciphertext yang dihasilkan dengan algoritma perkalian homomorfik, kemudian memperoleh ciphertext yang sesuai dengan hasil perkalian teks aslinya. Dalam keseluruhan proses, kita tidak perlu mengetahui informasi apa pun terkait kunci tersebut, kita cukup menggabungkan ciphertext yang terlihat seperti kode acak yang kacau.
Misalnya: Sistem pemungutan suara anonim
Selanjutnya, mari kita berikan contoh untuk menjelaskan dengan jelas kepraktisan enkripsi homomorfik.
Kita semua tahu seperti apa pemungutan suara online - jika bos sebuah perusahaan ingin memulai gelombang pemungutan suara, pilih apakah perusahaan tersebut harus mengadopsi sistem 996. Kemudian atasan dapat meminta TI untuk menyiapkan server dan membiarkan karyawan menyampaikan pilihannya: pilih 0 berarti tidak mau, dan pilih 1 berarti mau. Setelah periode pemungutan suara terakhir, bos dapat menjumlahkan semua suara. Jika total suara akhir melebihi setengah jumlah karyawan, perusahaan akan memulai 996.
Mekanisme pemungutan suara ini tampaknya sangat sederhana, tetapi ada masalah privasi yang besar: jika bos ingin semua karyawannya menjadi 996, tetapi dia hanya dengan sengaja memulai pemungutan suara ini untuk memancing penegakan hukum untuk melihat karyawan mana yang tidak mau bekerja lembur, maka bos Diam-diam dia bisa mempercayakan adiknya untuk menguping di Internet, mencatat pilihan yang diajukan oleh setiap karyawan, dan akhirnya melihat siapa yang memilih 0. Akibatnya karyawan sangat takut dan tidak berani mengungkapkan perasaannya.
Jika kita dapat menggunakan algoritma enkripsi homomorfik aditif, maka masalah ini dapat diselesaikan dengan mudah.
Tentu saja sistem ini masih sangat belum lengkap, misalnya departemen IT bisa langsung membantu bos mendekripsi suara semua orang dan mencatatnya ke dalam dokumen. Ada alat kriptografi lain yang dapat membantu kita mengatasi masalah ini. Karena alasan ruang, penjelasan lebih lanjut tidak akan diberikan di sini.
Namun pada titik ini, kita seharusnya sudah bisa merasakan kekuatan algoritma enkripsi homomorfik. Kita dapat memahaminya seperti ini: melalui algoritma enkripsi homomorfik, pengguna dapat melakukan semacam komputasi proxy yang aman (Secure Delegated Computation) dengan server jarak jauh (cloud) yang tidak tepercaya. Pengguna dapat menggunakan teknologi enkripsi homomorfik untuk mengenkripsi masukan pribadi sensitif mereka dan mempercayakannya ke cloud. Kemudian cloud dapat melakukan perhitungan tingkat tertentu pada data terenkripsi, dan akhirnya mendapatkan hasil terenkripsi yang diinginkan pengguna, dan mengembalikannya ke cloud.user. Terakhir, pengguna dapat menggunakan kunci dekripsi untuk membuka hasilnya. Sepanjang keseluruhan perjanjian, pihak yang didelegasikan (cloud) tidak pernah dapat melihat informasi berguna apa pun terkait masukan pribadi.
Setelah memahami secara kasar dua sifat homomorfik paling dasar, konsep lainnya menjadi sangat mudah dipahami. Dari perspektif sistematis, sistem enkripsi homomorfik secara kasar dibagi menjadi empat kategori: homomorfisme parsial, homomorfisme perkiraan, homomorfisme penuh seri terbatas, dan homomorfisme lengkap.
Selanjutnya, mari kita lihat definisi spesifik dari setiap kategori secara bergantian.
Enkripsi Homomorfik Sebagian
Tahap paling dasar dari enkripsi homomorfik disebut enkripsi homomorfik parsial, yang didefinisikan sebagai teks tersandi yang hanya memiliki satu sifat homomorfik. Tahap ini mencakup dua mode homomorfisme aditif dan homomorfisme perkalian yang kami jelaskan di atas.
Kami mendapatkan ciphertext yang sesuai dengan perkalian kedua pesan ini! Ini adalah properti homomorfisme perkalian. Kita dapat terus melapiskan ciphertext baru di atas ciphertext ini, sehingga kita bisa mendapatkan perkalian antar ciphertext.
Perkiraan Enkripsi Homomorfik (Enkripsi Agak Homomorfik)
Seperti yang kami katakan di paragraf sebelumnya, jika kita ingin mengalikan masukan pribadi dan mendapatkan kombinasi linier di antara masukan tersebut, algoritma enkripsi homomorfik parsial sederhana (RSA, ElGamal) tidak dapat diselesaikan. Jadi kita perlu sampai ke tahap berikutnya.
Tahap selanjutnya dari enkripsi homomorfik parsial adalah kira-kira enkripsi homomorfik, yang selangkah lebih dekat ke enkripsi homomorfik penuh yang ingin kita capai. Jika kita memiliki algoritma enkripsi yang kurang lebih homomorfik, maka kita dapat menghitung penjumlahan dan perkalian pada ciphertext secara bersamaan. Namun perlu diperhatikan bahwa karena tahap ini mendekati homomorfik, maka jumlah penjumlahan dan perkalian yang dapat dilakukan sangat terbatas, dan fungsi F yang dapat dihitung juga berada dalam rentang yang terbatas.
Tidak banyak contoh umum tentang enkripsi homomorfik pada tahap ini. Jika kita mengatakan contoh yang paling mudah dipahami, itu adalah algoritma enkripsi grup siklik berdasarkan pasangan.
Di atas kita membahas secara singkat algoritma enkripsi ElGamal berdasarkan kelompok siklik biasa. Kita semua tahu bahwa algoritma ini bersifat additive homomorphic, artinya dapat memperoleh kombinasi linier antara ciphertext yang berubah-ubah. Faktanya, pada beberapa gugus siklik khusus, kita juga dapat menemukan beberapa sifat homomorfisme perkalian yang lemah.
Keterbatasan ini membuktikan bahwa sistem tersebut mendekati homomorfik, karena kita tidak dapat menghitung fungsi F dengan logika dan kedalaman sembarang.
Enkripsi Homomorfik Tingkat Penuh
Setelah mencapai tahap berikutnya, kita selangkah lebih dekat ke tujuan homomorfisme penuh.
Tahap ini disebut enkripsi homomorfik seri terbatas. Pada tahap ini, kita sudah dapat melakukan kombinasi penjumlahan dan perkalian apa pun pada ciphertext tanpa ada batasan berapa kali.
Enkripsi Homomorfik Sepenuhnya (FHE)
Setelah banyak panggilan, akhirnya sampai pada enkripsi homomorfik penuh (FHE) yang kita tunggu-tunggu.
Seperti namanya, sistem enkripsi yang sepenuhnya homomorfik tidak memiliki batasan pada metode perhitungan. Kita dapat menggabungkan ciphertext secara sewenang-wenang untuk membentuk ciphertext baru tanpa kunci, dan teks ciphertext baru, terlepas dari kompleksitas komputasinya, dapat dikembalikan dengan sempurna ke teks aslinya.
Ketika kita mencapai tahap ini, perhitungan agen aman yang disebutkan sebelumnya menjadi layak dilakukan. Jika kita dapat menemukan sistem enkripsi homomorfik penuh yang lebih efisien, kita dapat dengan aman mem-proxy semua penghitungan lokal ke cloud tanpa membocorkan data apa pun!
Definisi sistem enkripsi yang sepenuhnya homomorfik
Sebelum memulai pembahasan sejarah sistem homomorfik penuh di bawah ini, kita dapat mendefinisikan secara sistematis definisi formal sistem homomorfik penuh. Sistem enkripsi yang sepenuhnya homomorfik memiliki total empat algoritma:
Sebelum mulai mempelajari bagaimana algoritma enkripsi homomorfik sepenuhnya diimplementasikan, ada baiknya kita melihat bagaimana konsep enkripsi homomorfik sepenuhnya muncul.
Konsep FHE (sepenuhnya homomorfik) sebenarnya diusulkan pada akhir tahun 1970-an. Pada tahun 1978, Rivest, Adleman dan Dertouzos, beberapa nama besar di bidang kriptografi, pertama kali menyebutkan dalam makalah mereka On Data Banks and Privacy Homomorphisms gagasan tentang sistem yang dapat melakukan perhitungan tertentu pada ciphertext dan secara tidak langsung beroperasi pada teks aslinya. Kemudian, ide ini dirangkum kembali dan diberi nama enkripsi homomorfik sepenuhnya.
Terlihat bahwa konsep enkripsi homomorfik penuh telah diusulkan sejak lama. Anehnya, pada tahun 1976, dua tahun sebelum makalah tersebut diterbitkan, protokol pertukaran kunci Diffle-Hellman baru saja diusulkan! Hal ini menunjukkan bahwa imajinasi para ahli kriptografi masih sangat kaya.
Ketika konsep FHE diusulkan, seluruh komunitas akademis tergerak olehnya dan memulai pencarian selama puluhan tahun, mencoba menemukan algoritma sempurna dengan sifat homomorfik sepenuhnya. Namun selama beberapa dekade terakhir, orang telah mencoba semua pilihan yang ada, namun mereka tidak dapat menemukan pilihan yang memenuhi semua syarat untuk menjadi homomorfik sepenuhnya dan keamanannya dapat dibuktikan dengan mudah.
Hingga tahun 2009, PhD Craig Gentry yang sedang kuliah di Stanford tiba-tiba mendapat ide dan menerobos kesulitan algoritma FHE. Dalam tesis doktoralnya, ia memberikan sistem enkripsi homomorfik sepenuhnya yang masuk akal dan aman untuk pertama kalinya! Sistem ini didasarkan pada asumsi kisi ideal. Sistem sepenuhnya homomorfik yang diusulkan oleh Gentry09 sering disebut sebagai sistem enkripsi homomorfik penuh generasi pertama.
Dalam makalah Gentry, ia juga menyebutkan konsep penting yang disebut Bootstrapping. Bootstrapping adalah teknik pemrosesan khusus untuk ciphertext, setelah diproses dapat “menyegarkan” ciphertext dengan noise yang mendekati nilai kritis menjadi ciphertext baru dengan noise yang sangat rendah. Melalui Bootstrapping, noise dari sistem seri hingga tidak akan pernah melebihi nilai kritisnya, sehingga menjadi sistem yang sepenuhnya homomorfik. Dengan cara ini, kita dapat menghitung F secara homomorfik dengan ukuran berapa pun.
Setelah terobosan besar Gentry, seluruh lingkaran kriptografi kembali menjadi gila, dan semua orang mulai berebut untuk menemukan sistem homomorfik penuh yang lebih efisien dan serbaguna berdasarkan ide yang diajukan oleh Gentry.
Pada tahun 2011, dua orang besar, Brakerski dan Vaikuntanathan, mengusulkan sistem enkripsi homomorfik baru, yang didasarkan pada Learning With Errors (LWE), asumsi lain dari enkripsi kisi. Pada tahun yang sama, Brakerski, Gentry dan Vaikuntanathan menyelesaikan sistem tersebut dan menerbitkannya secara resmi. Sistem homomorfik sepenuhnya yang mereka temukan disebut sistem BGV. Sistem BGV adalah sistem enkripsi homomorfik tingkat terbatas, namun dapat diubah menjadi sistem homomorfik sepenuhnya melalui Bootstrapping. Dibandingkan dengan sistem yang dikemukakan oleh Gentry09, sistem BGV menggunakan asumsi LWE yang lebih realistis. Secara umum, kami menyebut sistem BGV sebagai sistem enkripsi homomorfik generasi kedua.
Pada tahun 2013, Gentry kembali lagi. Gentry, Sahai dan Waters telah meluncurkan sistem enkripsi GSW yang sepenuhnya homomorfik. Sistem GSW mirip dengan BGV karena memiliki sifat homomorfik seri terbatas yang didasarkan pada asumsi LWE yang lebih sederhana dan dapat sepenuhnya homomorfik melalui Bootstrapping. Kami biasanya menyebut sistem GSW sebagai sistem enkripsi homomorfik generasi ketiga.
Setelah tahun 2013, cryptosphere pada dasarnya berkembang pesat. Berdasarkan sistem homomorfik penuh tiga generasi yang asli, berbagai desain baru telah muncul, didedikasikan untuk mengoptimalkan dan mempercepat efisiensi pengoperasian sistem BGV dan GSW. IBM mengembangkan perpustakaan komputasi homomorfik sumber terbuka HElib berdasarkan sistem BGV, dan berhasil memindahkannya ke platform seluler utama. Pada saat yang sama, ada proyek open source lain TFHE yang juga patut diperhatikan. TFHE didasarkan pada sistem GSW, dengan berbagai optimasi dan akselerasi ditambahkan, dan sekarang sangat terkenal.
Selain mengembangkan perpustakaan tradisional yang sepenuhnya homomorfik, banyak tim juga mempelajari cara mempercepat penghitungan algoritme enkripsi sepenuhnya homomorfik dengan lebih baik melalui perangkat keras heterogen seperti GPU, FPGA, dan ASIC. Misalnya, cuFHE adalah sistem enkripsi homomorfik penuh akselerasi GPU berbasis CUDA yang terkenal.
Dari sudut pandang saat ini, sudah 11 tahun sejak Gentry membuka pintu sistem homomorfik sepenuhnya. Saat ini, penelitian tentang FHE sedang booming di industri, dan banyak orang mempelajari sistem yang sepenuhnya homomorfik dari berbagai perspektif dan persyaratan aplikasi. Hingga saat ini, kami telah memiliki berbagai metode implementasi FHE yang layak, namun yang masih diupayakan adalah efisiensi pengoperasian sistem FHE. Mengambil perpustakaan FHE mutakhir saat ini sebagai contoh, menghitung beberapa logika yang relatif sederhana secara homomorfik pada platform seluler mungkin memerlukan waktu paling sedikit puluhan milidetik dan paling lama puluhan detik. Satuan waktu ini sangat lambat untuk sistem komputer.
Bagaimana membuat sistem FHE berjalan lebih efisien pada platform heterogen masih menjadi misteri yang belum terpecahkan. Jika masalah ini terpecahkan, maka mengubah semua penghitungan komputer menjadi homomorfik sepenuhnya dan meminta agen melakukan penghitungan di cloud pihak ketiga akan menjadi masa depan yang mudah.
Hubungan antara FHE dan MPC
Sebelum mengakhiri artikel, saya ingin menambahkan sedikit penjelasan tentang hubungan FHE dan MPC. MPC adalah singkatan dari Secure Multi-Party Computation, yang merupakan komputasi multi-pihak yang tepercaya. Hal ini biasanya berarti bahwa banyak pihak memiliki masukan pribadi mereka sendiri dan tidak ingin mengungkapkannya kepada orang lain, namun mereka ingin menggunakan masukan mereka sendiri untuk menghitung fungsi F bersama-sama dan membagikan hasil penghitungannya.
MPC sebenarnya merupakan bidang yang sangat terkenal dan telah dipelajari sejak lama. Sejak kriptografer Yao Qizhi meluncurkan Garbled Circuits-nya pada abad terakhir, bidang MPC telah mendapat pengakuan luas dan banyak terobosan. Sekarang kami telah memiliki banyak perpustakaan MPC yang dapat digunakan, dan juga memiliki efisiensi pengoperasian tertentu.
Teman-teman yang mengetahui MPC mungkin memiliki banyak pertanyaan setelah melihat sejarah sulit dari sistem enkripsi yang sepenuhnya homomorfik: Mengapa enkripsi yang sepenuhnya homomorfik tidak dapat digantikan langsung oleh protokol MPC?
Memang benar bahwa protokol MPC dapat sepenuhnya menggantikan protokol FHE. Kita hanya perlu menggunakan input pengguna dan pribadi sebagai pihak dalam suatu protokol, dan kemudian menggunakan server komputasi proxy jarak jauh sebagai pihak lain, yang memenuhi persyaratan untuk pelaksanaan protokol MPC.Hanya melalui interaksi tertentu, komputasi proxy dapat dilakukan terealisasi Dan server tidak dapat melihat input pribadi.
Namun ada satu hal yang sangat penting yang telah kita abaikan: karena MPC bersifat interaktif, pengguna dan server perlu menghitung dan berkomunikasi bersama untuk menyelesaikan protokol. Hal ini bertentangan dengan persyaratan paling mendasar dari komputasi agen FHE. Jika pengguna harus tetap online sepanjang waktu untuk menyelesaikan perjanjian dan juga membayar sebagian dari daya komputasi, maka sebenarnya perhitungan tersebut tidak "diproxy" sama sekali, dan kedua belah pihak hanya melakukan lebih banyak perhitungan demi keamanan informasi. . Hal ini juga menjelaskan mengapa bidang MPC telah membuat terobosan besar, namun bidang FHE masih belum diketahui, karena kedua sistem tersebut menyelesaikan masalah yang sangat berbeda.
Melihat hal ini, setiap orang pasti memiliki pemahaman yang sangat mendalam tentang sistem enkripsi yang sepenuhnya homomorfik.
Pemberhentian selanjutnya, kita dapat mempelajari tentang sistem enkripsi homomorfik GSW yang disebutkan di atas. Meskipun ini adalah generasi ketiga dari sistem yang sepenuhnya homomorfik, menurut saya di antara tiga sistem Gentry09, BGV, dan GSW, GSW adalah yang memiliki asumsi paling sedikit, struktur paling sederhana, dan paling mudah dipahami. Dan saat ini sudah banyak perpustakaan open source (seperti TFHE) yang dibangun berdasarkan sistem GSW.
Karena alasan ruang, kami akan mengakhiri artikel ini di sini. Pada artikel selanjutnya, kita akan mempelajari terlebih dahulu dasar-dasar sistem GSW: sistem enkripsi berbasis kisi dan masalah LWE. Setelah masalah LWE dipahami, masalah yang dipecahkan oleh GSW menjadi sangat jelas.