- Enkripsi Homomorfik Penuh (FHE) adalah teknologi yang memungkinkan komputasi dilakukan langsung pada ciphertext tanpa perlu mendekripsi data
- Saat ini, FHE masih memiliki keterbatasan seperti kepraktisan yang rendah, penurunan kecepatan komputasi sebesar 1.000x~10.000x, dan peningkatan kebutuhan ruang penyimpanan sebesar 40x~1.000x
- Namun, belakangan ini algoritme FHE mengalami peningkatan kecepatan 8x per tahun, dan berpotensi segera memasuki ranah praktis di komputasi cloud, inferensi LLM, smart contract blockchain, dan lainnya
- Jika FHE menjadi umum, ini akan mendorong perubahan industri di mana privasi data menjadi default di seluruh lingkungan komputasi
- Membahas secara komprehensif kriptografi berbasis lattice, LWE, bootstrapping, dan lainnya, sejarah perkembangan algoritme FHE, contoh implementasi nyata, serta tren peningkatan performa
Pendahuluan: Apa itu enkripsi homomorfik penuh
- Enkripsi Homomorfik Penuh (Fully Homomorphic Encryption, FHE) adalah metode yang memungkinkan operasi arbitrer pada ciphertext tanpa dekripsi, sehingga komputasi dapat dilakukan langsung pada data terenkripsi
- Artinya, server dapat menghitung pertanyaan dan hasilnya tanpa mengetahui plaintext, lalu mengirimkannya kembali
- Teknologi ini kini mulai diadopsi di berbagai sistem dunia nyata
Potensi dan keterbatasan FHE: "Hukum Moore-nya FHE"
- FHE dapat menjaga data tetap terenkripsi secara terus-menerus di jaringan, sehingga mewujudkan privasi penuh yang secara mendasar mencegah risiko kebocoran data
- Meski demikian, alasan utama FHE masih sulit dipraktikkan saat ini adalah karena komputasi atas ciphertext 1.000~10.000 kali lebih lambat dibanding komputasi plaintext, dan kebutuhan penyimpanan juga meningkat sekitar 40~1.000 kali lipat, sehingga terjadi penurunan performa yang sangat besar
- Ini mirip dengan masa awal internet pada 1990-an
- Namun, FHE baru-baru ini menjadi 8x lebih cepat setiap tahun, sehingga diperkirakan segera masuk ke berbagai area praktis
Titik kritis: Praktik FHE yang segera tiba
- Jika lompatan kecepatan seperti ini terus berlanjut, FHE di masa depan dapat menjadi praktis di bidang-bidang berikut
- komputasi cloud terenkripsi
- inferensi LLM terenkripsi
- smart contract blockchain dengan jaminan kerahasiaan
- Perubahan ini dapat mengguncang secara fundamental model bisnis internet yang bertumpu pada pengumpulan data pengguna
- Berkat FHE, diharapkan terjadi pergeseran mendasar dari internet yang "berbasis pengawasan" menjadi internet yang "berbasis privasi"
Titik lemah keamanan data dan solusi dari FHE
- Data memiliki 3 keadaan (disimpan, ditransmisikan, digunakan), dan keadaan 'saat digunakan' sering menjadi titik lemah keamanan karena data harus didekripsi
- Cloud, orang dalam, peretas, CPU yang rentan, dan pihak lain dapat mengakses data plaintext di memori
- Sebagian besar insiden kebocoran data besar juga terjadi saat data 'digunakan' atau 'disimpan'
- FHE menjaga data tetap terenkripsi sepanjang seluruh siklus hidupnya, sehingga secara mendasar mengatasi kerentanan ini
Definisi komputasi dengan privasi penuh
- Lingkungan ideal adalah ketika data tetap terenkripsi saat disimpan, ditransmisikan, dan digunakan (diproses)
- Misalnya, server sama sekali tidak pernah melihat pertanyaan dalam bentuk plaintext, menerima pertanyaan terenkripsi, lalu hanya mengembalikan hasil terenkripsi
- Hanya pengguna yang dapat mendekripsi hasil tersebut
Cara kerja FHE: struktur dan konsep matematis
- "Homomorfik" didasarkan pada transformasi matematis yang mempertahankan struktur yang sama (misalnya mirip dengan transformasi Fourier)
- FHE mentransformasikan ruang plaintext dan ruang ciphertext secara dua arah, sehingga hasil dekripsi dari operasi pada ciphertext sama dengan hasil operasi pada plaintext
- Transformasi semacam ini umumnya menggunakan kriptografi berbasis lattice dan LWE (Learning With Errors)
- Kriptografi berbasis lattice adalah persoalan vektor di dimensi yang sangat tinggi, yang diketahui sulit dipecahkan bahkan oleh komputer kuantum (tahan kuantum)
- LWE adalah persoalan membalik sistem linear yang dicampuri noise, yang secara praktis tidak dapat dipecahkan
Manajemen noise dan bootstrapping
- Dalam FHE, noise di dalam ciphertext meningkat seiring operasi dilakukan berulang kali
- Pada operasi penjumlahan, noise bertambah secara linear, sedangkan pada perkalian bertambah secara eksponensial, hingga pada akhirnya membuat dekripsi tidak mungkin dilakukan
- Teknologi kunci untuk mengatasi ini adalah bootstrapping, yaitu teknik mengenkripsi ulang ciphertext dengan 'kunci publik baru' untuk mengatur ulang noise ke tingkat tertentu
- Proses ini menjadi bottleneck performa pada sistem FHE, tetapi terus membaik dengan cepat setiap tahun
Komponen inti tambahan dalam FHE
- relinearization: proses untuk mengatasi masalah derajat kunci yang naik ke orde dua setelah perkalian, lalu mengembalikannya menjadi orde satu
- modulus switching: teknik untuk mengecilkan modulus ciphertext guna mengelola noise
Selain itu, beragam teknik baru terus diajukan seiring perkembangan algoritme
Klasifikasi skema enkripsi homomorfik (HE) dan contoh Python
- Partial HE: hanya mendukung satu operasi (mis. sandi Paillier hanya mendukung penjumlahan)
- Somewhat HE: mendukung penjumlahan dan perkalian, tetapi jumlah pengulangan perkalian terbatas
- FHE: mendukung penjumlahan dan perkalian tanpa batas. Menjamin kelengkapan Turing
Melalui contoh enkripsi Paillier yang diimplementasikan dengan Python, konsep homomorfik parsial dapat dipahami secara intuitif
Sejarah perkembangan FHE dan "Hukum Moore-nya FHE"
- 1978: konsep "privacy homomorphism" pertama kali muncul
- 2009: realisasi pertama FHE oleh Craig Gentry (disertasi doktoral)
- 2011: implementasi pertama, membutuhkan 30 menit per bit (sangat lambat)
- Sejak 2013: bootstrapping dipercepat hingga level beberapa ms
- 2017: dukungan aproksimasi floating point seperti CKKS, mulai masuk serius ke ML/AI
Algoritme FHE meningkat 8x per tahun sejak 2011, dari overhead awal 10¹⁰x menjadi sekitar 10³~10⁴x belakangan ini
Makalah terbaru menurunkan throughput perkalian FHE hingga 1.000x dan latensi hingga 10x, dan bila digabung dengan akselerasi hardware masih ada potensi peningkatan kecepatan lebih dari 1.000x lagi
Masa depan ketika enkripsi menjadi default
- Insiden kebocoran data besar adalah kenyataan yang tak terhindarkan
- Jika dengan FHE server dapat hanya melakukan komputasi pada data terenkripsi tanpa kunci dekripsi, ini akan menjadi standar baru perlindungan privasi
- Memang belum sepenuhnya praktis di semua area, tetapi teknologinya membaik dengan kecepatan yang luar biasa setiap tahun
- Seiring meningkatnya tuntutan privasi pengguna dan penguatan regulasi terkait, FHE pada akhirnya diperkirakan menjadi standar di sebagian besar komputasi cloud
- Komputasi internet di masa depan akan berkembang dalam keadaan selalu terenkripsi
2010-an: HTTPS menjadi default
Ke depan: era ketika FHE menjadi default diperkirakan akan tiba
Referensi dan materi tambahan
- FHE Reference Library: ringkasan komprehensif materi akademik
- Disertasi doktoral Craig Gentry 2009: titik awal FHE
- Vitalik Buterin: analisis mendalam FHE
- Komunitas: FHE.org (hub berfokus pada pengembang)
- GitHub: awesome-he: kumpulan proyek terkait enkripsi homomorfik
1 komentar
Komentar Hacker News
Saya akan bicara dari posisi yang sangat menyukai FHE dan kriptografi. FHE memang makin cepat, tetapi selama masih bergantung pada bootstrapping, mustahil menyamai kecepatan operasi pada plaintext. Overhead sekitar 1000x atau lebih akibat bootstrapping pada dasarnya tidak bisa dihindari, dan ketika orang mulai sadar bahwa itu tidak mungkin dipercepat lagi, mulailah muncul pembicaraan soal akselerasi perangkat keras. Namun itu tidak mudah di masa sekarang ketika hampir semua daya komputasi tersedot ke LLM. Jika memikirkan berapa kali lipat biaya per token saat komputasi dilakukan dengan FHE, secara realistis hampir tidak ada peluang kecuali angkanya jauh di bawah 1000x. Untuk tujuan privasi, pendekatan confidential computing saat ini adalah satu-satunya alternatif yang praktis. Saya tidak suka karena tetap harus mempercayai hardware, tetapi itulah yang terbaik yang kita punya saat ini
Ada alasan yang lebih mendasar lagi mengapa FHE sulit dipakai untuk komputasi arbitrer. Yaitu, ada jenis operasi tertentu yang kompleksitasnya membengkak secara tidak normal pada ciphertext dibanding plaintext. Untuk pencarian database, pada plaintext bisa O(log n), tetapi jika mencari dengan kunci terenkripsi menjadi O(n). Jadi Google Search yang sepenuhnya homomorfik pada dasarnya tidak mungkin diwujudkan. Namun inferensi DNN yang sepenuhnya homomorfik mungkin berbeda ceritanya
Bahkan tanpa bootstrapping pun FHE tidak akan bisa secepat operasi plaintext. Ciphertext berukuran sekitar 1000x lebih besar daripada plaintext. Artinya, dibutuhkan bandwidth memori dan jumlah komputasi yang jauh lebih besar. Kesenjangan ini tidak bisa ditutup
Saya bertanya-tanya apakah ada segmen permintaan tertentu yang benar-benar menginginkan privasi yang bisa diverifikasi, meskipun biaya komputasinya naik 1000x. Mungkin tidak sebesar Dropbox, tetapi saya membayangkan tetap ada pasar tertentu
Saya mengingat kembali masa ketika semuanya berbentuk kartu ekspansi PCIE. GPU juga begitu, dan ada pula akselerator khusus seperti math coprocessor. Sekarang semuanya terintegrasi ke hardware umum sehingga lebih murah dan praktis, tetapi tidak bisa menandingi chip silikon yang dioptimalkan untuk fungsi tertentu. Karena itu saya berpendapat bahwa kartu khusus untuk AI/ML sebaiknya dipisahkan, bukan berbasis GPU. Ada sebagian tumpang tindih arsitektur, tetapi kartu AI berbasis GPU pada dasarnya harus menanggung banyak kompromi. Menurut saya akselerator AI yang sesungguhnya adalah hardware khusus yang masuk ke soket SXM terbaru. Namun soket SXM hanya ada di server dan harganya juga tidak murah
Saya mengakui demam LLM, tetapi saya penasaran apakah benar-benar tidak ada kegunaan lain yang layak untuk FHE. Misalnya, mungkin kita bisa membayangkan algoritme trading yang tidak membutuhkan kecepatan tinggi di-host di server dengan FHE untuk menjamin keamanannya
Alasan FHE penting adalah karena saat ini ada kasus ketika perusahaan dipaksa oleh tekanan pemerintah untuk membobol enkripsi target tertentu. FHE memungkinkan perusahaan dengan tegas mengatakan, "kami sama sekali tidak bisa melihat plaintext." Dalam peran carrier jaringan, sebagian hal ini bisa dilakukan dengan E2E encryption dan sejenisnya, tetapi saat data harus diproses dalam keadaan plaintext, itu masih belum mungkin. Saya percaya privasi adalah hak asasi dasar. Kewenangan pemerintah seharusnya hanya berlaku sangat terbatas terhadap aktivitas demokratis seperti pemungutan suara, seni, pers, ekspresi, dan sebagainya
Sekalipun FHE memungkinkan komputasi arbitrer, sebagian besar layanan digunakan karena mereka menyediakan data tertentu. Jika Google ingin menjamin keamanan atas kueri saya, seluruh indeks pencariannya harus dienkripsi, dan itu secara realistis mustahil. Secara bisnis juga, saya rasa hampir tidak ada insentif untuk mengadopsi layanan berbasis FHE kecuali di bidang yang sangat tepercaya dan sangat berisiko dengan pasar yang amat kecil
Sejauh yang saya tahu, cukup data sensitif saja yang dienkripsi (misalnya data transaksi bank saya). Fungsi yang ingin dihitung itu sendiri tidak perlu dienkripsi, dan bisa digunakan bersama data publik
Pada akhirnya, dari sudut pandang perusahaan besar, sumber pendapatan mereka justru datang dari bisa melihat data atau kueri pengguna secara langsung, jadi tidak ada motivasi untuk mengadopsi FHE sebagai kebiasaan. Di sektor keuangan seperti bank mungkin terdengar keren, tetapi di luar itu belum jelas kapan akan diadopsi
Soal insentif saya setuju. Tetapi bagian pertamanya berbeda. Lookup privat terhadap database plaintext sudah dimungkinkan sejak beberapa tahun lalu. Hanya saja, database plaintext itu harus dipraproses lebih dulu dengan cara yang cukup rumit, atau dalam kasus terburuk seluruh DB harus dipindai secara linear
Sebagai contoh implementasi mesin pencari FHE yang sepenuhnya privat, saya memperkenalkan spiralwiki.com. Dengan cara ini, server sama sekali tidak bisa mengetahui artikel Wikipedia mana yang dibaca pengguna spiralwiki.com
Dari "sudut pandang klien", mungkin ada orang yang mau membayar untuk layanan yang melindungi data mereka secara sempurna seperti FHE, tetapi dalam praktiknya itu akan sangat mahal dan pelanggannya sangat sedikit. Jika dihitung dengan asumsi biaya komputasi puluhan kali lebih tinggi daripada sekarang, bahkan jika layanan pengganti Google yang berfokus pada privasi bisa ditawarkan seharga $100 per tahun, tetap akan sulit menarik banyak pelanggan. Semakin mahal biayanya, semakin sedikit pula pelanggan. Ada alternatif seperti Tor yang meski tidak sempurna tetap memberi perlindungan yang cukup besar secara gratis. Bukan berarti HE tidak berguna, melainkan hanya sangat sedikit orang yang bersedia menanggung biayanya
Disebutkan bahwa internet bisa berubah dari "pengawasan sebagai default" menjadi "privasi sebagai default". Saya sendiri sudah lama ikut menyebarkan teknologi privasi, misalnya dengan membuat tanda tangan digital. Namun kita juga harus melihat kenyataan bahwa Hacker News dan Facebook memegang identitas semua orang. Itu terlalu mudah dan menguntungkan. FHE juga termasuk "teknologi yang diinginkan orang, tetapi secara praktis tidak cepat diadopsi luas". Di kebanyakan kasus, cara lama dianggap sudah cukup baik karena overhead operasional dan beban kompleksitasnya
Ketika saya menambahkan hal seperti tanda tangan digital di akhir email, reaksi yang saya dapat hanya semacam "itu apaan?" Saya penasaran apakah ada yang pernah berhasil meyakinkan pengguna umum agar ikut menggunakan enkripsi sisi klien
Ada pendapat bahwa ketika FHE digabungkan dengan AI, sebagian beban kompleksitasnya bisa ditanggung oleh AI, dan itu mungkin menjadi kombinasi pembunuh yang benar-benar layak dipakai luas
Secara realistis, saya rasa perusahaan tidak punya alasan untuk mengadopsi solusi seperti layanan FHE yang memakai komputasi 1.000.000x lebih banyak, jauh lebih sulit di-debug, dan bahkan tidak bisa menganalisis pola penggunaan
Memulai pembahasan dengan contoh Google bisa menimbulkan salah paham. Biasanya ketika orang mendengar "Google", yang terpikir adalah "pencarian web", tetapi FHE yang dijelaskan dalam dokumen ini mengharuskan seluruh input dienkripsi dengan satu kunci, sehingga konteksnya mungkin tidak cocok untuk layanan pencarian. Indeks pencarian Google ukurannya mencapai beberapa TB, dan saya rasa mustahil mengenkripsi semuanya dengan kunci tertentu. Artinya, FHE hanya berguna ketika pengguna mengendalikan seluruh input. Referensi ke Google justru membingungkan
Dalam kasus seperti CallerID milik Apple, tampaknya tidak perlu mengenkripsi seluruh database secara terpisah untuk tiap pengguna riset homomorphic encryption Apple / pencarian privat Apple
Layanan berbasis homomorphic encryption sejak awal tidak perlu mengetahui kunci enkripsinya terlebih dahulu. Itulah intinya. Sebagai contoh enkripsi yang sangat sederhana, diperkenalkan struktur yang bisa menghasilkan penjumlahan dua ciphertext meskipun kuncinya belum ditentukan. Jika pada skema enkripsi yang lebih kuat kita juga mendukung operasi yang lebih kompleks, maka sangat banyak fungsi yang bisa diwujudkan
Ketika orang bilang Google, yang terbayang bukan cuma pencarian, tetapi juga Gmail, Google Docs, dan banyak layanan lain yang berkaitan dengan privasi. Orang yang hanya terpikir pencarian mungkin memang tidak membaca artikelnya
Saya pikir FHE tidak akan mudah langsung diterapkan pada komputasi umum atau layanan internet. Setidaknya perlu banyak generasi lagi dari hukum Moore sebelum itu menjadi mungkin. Namun ada bidang yang sudah mulai merasakan manfaat FHE, yaitu smart contract, keuangan, dan medis, yang kompleksitasnya lebih rendah tetapi tuntutan keamanan dan tingkat kepercayaannya sangat tinggi. Berkat Moore's law terbaru dan optimalisasi software, kurvanya tampaknya mulai membelok ke arah kepraktisan. Pekerjaan hardware/Devtools Zama disebut sebagai contoh
E2EE git sudah dikembangkan. Saya pernah bertanya kepada pembuatnya apakah itu bisa memenuhi kebutuhan seperti protected branch atau pencegahan force push di server, tetapi tidak ada solusi yang layak jika klien bersifat jahat. Saya penasaran apakah ini suatu hari bisa berkembang menjadi E2EE Github tautan Hacker News terkait
Saat mendengar narasi bahwa kecepatan FHE akan terus meningkat, saya teringat soal matematika lama tentang kecepatan rata-rata. Misalnya, jika menempuh 1 mil tanjakan dengan kecepatan 15 mph, lalu ingin rata-rata kecepatan 30 mph untuk total 2 mil, seberapa cepat Anda harus melaju di 1 mil turunan? Laju perbaikan di masa lalu tidak menjamin kemungkinan di masa depan. Ini bukan batas fisika, melainkan batas algoritme
Bagaimana kalau turunan itu berupa tebing? Jika menghitung kecepatan terminal mobil sekitar 200-300mph, secara perhitungan mungkin saja 1 mil ditempuh dalam 15 detik dengan jatuh bebas. Untuk rata-rata 30mph selama total 2 mil dibutuhkan 4 menit, jadi kecepatan saat tanjakan pun harus disesuaikan dengan sisa waktunya, tetapi dalam kenyataan itu mustahil karena banyak variabel lain
Jika dihitung secara ketat, di turunan cukup 41mph untuk mendapatkan rata-rata total 30mph. Jika diasumsikan ada pembulatan angka atau galat pengukuran dalam pertanyaan, hasilnya akan seperti itu