Skema BGV & BFV untuk Operasi Bilangan Bulat

BGV (Brakerski-Gentry-Vaikuntanathan, 2012) adalah skema FHE bertingkat yang didasarkan pada RLWE. Skema ini mendukung penjumlahan dan perkalian arbitrer pada teks biasa bilangan bulat yang dikemas. “Bertingkat” berarti skema ini menangani sirkuit hingga kedalaman tetap L tanpa penyegaran.

BGV dan BFV mengodekan teks biasa sebagai polinom dalam Z_t[x]/(x^n+1), dengan t sebagai modulus teks biasa yang kecil (misalnya, t=65537). Setiap polinom mengodekan n nilai bilangan bulat, satu untuk setiap koefisien. Aritmetika pada teks sandi beroperasi pada semua n nilai secara bersamaan—paralelisme SIMD.

BGV mengurangi derau melalui pergantian modulus: setelah setiap perkalian, modulus teks sandi q diturunkan dari Q_L menjadi Q_{L-1}. Hal ini membagi derau dengan Q_L/Q_{L-1}, sehingga derau tetap berada dalam batas yang dapat didekripsi. Kedalaman sirkuit L sesuai dengan L tingkatan modulus.

BFV (Brakerski/Fan-Vercauteren, 2012) mirip dengan BGV, tetapi menggunakan strategi pengelolaan derau yang berbeda: invarian skala. BFV tidak memerlukan pergantian modulus; sebagai gantinya, skema ini menskalakan ulang teks sandi setelah perkalian. Implementasinya lebih sederhana dan digunakan dalam Microsoft SEAL.

Melalui Teorema Sisa Tiongkok pada cincin teks biasa, setiap teks sandi dapat memuat n/2 nilai bilangan bulat independen (ruang). Operasi penjumlahan teks sandi menjumlahkan semua n/2 pasangan secara paralel. Operasi perkalian mengalikan semua pasangan. Laju pemrosesan: n/2 operasi bilangan bulat untuk setiap operasi teks sandi.

Setelah mengalikan dua teks sandi berderajat-1, hasilnya berderajat-2 (3 komponen). Relinearisasi menggunakan kunci evaluasi (kunci relin) untuk mengubahnya kembali menjadi berderajat-1 dengan menambahkan derau. Langkah ini diperlukan setelah setiap perkalian.

from seal import EncryptionParameters, scheme_type, SEALContext, KeyGenerator, Encryptor, Evaluator, Decryptor parms = EncryptionParameters(scheme_type.bfv) parms.set_poly_modulus_degree(4096) parms.set_coeff_modulus(CoeffModulus.BFVDefault(4096)) parms.set_plain_modulus(PlainModulus.Batching(4096, 20))

Rotasi teks sandi menggeser n/2 ruang teks biasa secara siklik. Berguna untuk: reduksi jumlah (mengakumulasikan semua ruang menjadi satu), perkalian matriks-vektor (memutar dan mengakumulasikan), serta konvolusi (menggeser dan mengalikan). Memerlukan kunci Galois (kunci rotasi yang telah dihitung sebelumnya).

BFV dengan n=8192: penjumlahan sekitar 10 µs, perkalian sekitar 5 ms (dengan relinearisasi). Penyegaran, jika diperlukan: 30-60 detik. Batch berisi 4096 bilangan bulat: sekitar 1 µs per bilangan bulat untuk setiap perkalian setelah dirata-ratakan. Tidak praktis untuk waktu nyata, tetapi layak untuk analitik luring.

Untuk memilih n dan q: SEAL merekomendasikan n=4096 untuk keamanan 128 bit dengan Q < 2^109; n=8192 untuk sirkuit yang lebih besar. Standar HE (homomorphicencryption.org) menyediakan tabel parameter. Selalu gunakan parameter yang direkomendasikan—pilihan khusus dapat dengan mudah melemahkan keamanan.

Kueri basis data terenkripsi (mencari catatan terenkripsi tanpa mendekripsinya). Analisis genom privat (menghitung statistik pada DNA terenkripsi). Penggabungan data keuangan terenkripsi (menjumlahkan saldo rekening terenkripsi tanpa melihat data individu). Evaluasi model yang aman.

BGV dan BFV melakukan aritmetika bilangan bulat terenkripsi menggunakan RLWE. Pengodean batch menyediakan paralelisme SIMD. BGV menggunakan pergantian modulus; BFV menggunakan invarian skala. Relinearisasi mengembalikan derajat setelah perkalian. Berikutnya: CKKS untuk aritmetika hampiran dan ML.