Tamsayı İşlemleri için BGV ve BFV Şemaları

BGV (Brakerski-Gentry-Vaikuntanathan, 2012), RLWE tabanlı, seviyeli bir FHE şemasıdır. Paketlenmiş tamsayı açık metinleri üzerinde keyfi toplama ve çarpma işlemlerini destekler. "Seviyeli", önyükleme olmadan sabit bir L derinliğine kadar olan devreleri işleyebildiği anlamına gelir.

BGV ve BFV, açık metinleri t'nin küçük bir açık metin modülü olduğu Z_t[x]/(x^n+1) içindeki polinomlar olarak kodlar (örneğin t=65537). Her polinom n tamsayı değerini, yani katsayı başına bir değer, kodlar. Şifreli metinler üzerindeki aritmetik, n değerinin tümü üzerinde aynı anda çalışır — SIMD paralelliği.

BGV, modül değiştirme yoluyla gürültüyü azaltır: her çarpmanın ardından şifreli metin modülü q, Q_L'den Q_{L-1}'e düşürülür. Bu işlem gürültüyü Q_L/Q_{L-1} oranında böler ve gürültüyü şifre çözmenin mümkün olduğu sınırlar içinde tutar. Devre derinliği L, L modül seviyesine karşılık gelir.

BFV (Brakerski/Fan-Vercauteren, 2012), BGV'ye benzer, ancak farklı bir gürültü yönetimi stratejisi kullanır: ölçekten bağımsızlık. BFV modül değiştirme gerektirmez; bunun yerine çarpma sonrasında şifreli metni yeniden ölçeklendirir. Uygulaması daha basittir ve Microsoft SEAL'de kullanılır.

Açık metin halkası üzerinde Çin Kalan Teoremi aracılığıyla her şifreli metin, birbirinden bağımsız n/2 tamsayı değeri (yuva) taşıyabilir. Bir toplama şifreli metin işlemi, n/2 çiftin tümünü paralel olarak toplar. Bir çarpma işlemi, tüm çiftleri çarpar. Verim: her şifreli metin işlemi başına n/2 tamsayı işlemi.

İki derece-1 şifreli metin çarpıldıktan sonra sonuç derece-2 olur (3 bileşen). Yeniden doğrusallaştırma, ek gürültü maliyeti karşılığında dereceyi tekrar 1'e dönüştürmek için değerlendirme anahtarlarını (yeniden doğrusallaştırma anahtarlarını) kullanır. Bu adım her çarpmadan sonra gereklidir.

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))

Şifreli metin döndürme işlemi, n/2 açık metin yuvasını döngüsel olarak kaydırır. Şunlar için kullanışlıdır: toplam indirgeme (tüm yuvaları tek bir yuvada biriktirme), matris-vektör çarpımı (döndürme ve biriktirme) ve evrişimler (kaydırma ve çarpma). Galois anahtarları (önceden hesaplanmış döndürme anahtarları) gerektirir.

n=8192 ile BFV: toplama yaklaşık 10 µs, çarpma yaklaşık 5 ms (yeniden doğrusallaştırma ile). Önyükleme (gerekirse): 30-60 saniye. 4096 tamsayıdan oluşan bir toplu işlem: çarpma başına tamsayı başına ortalama yaklaşık 1 µs. Gerçek zamanlı kullanım için elverişsizdir, ancak çevrimdışı analizler için uygundur.

n ve q seçimi için SEAL, Q < 2^109 olacak şekilde 128 bitlik güvenlik için n=4096'yı, daha büyük devreler için ise n=8192'yi önerir. HE standardı (homomorphicencryption.org) parametre tabloları sağlar. Her zaman önerilen parametreleri kullanın — özel seçimler güvenliği kolayca zayıflatabilir.

Şifreli veritabanı sorguları (şifrelenmiş kayıtları şifreyi çözmeden arama). Özel genom analizi (şifreli DNA üzerinde istatistik hesaplama). Şifreli finansal toplulaştırmalar (kişileri görmeden şifrelenmiş hesap bakiyelerini toplama). Güvenli model değerlendirmesi.

BGV ve BFV, RLWE kullanarak şifreli tamsayı aritmetiği gerçekleştirir. Toplu kodlama, SIMD paralelliği sağlar. BGV modül değiştirme kullanır; BFV ölçekten bağımsızlık kullanır. Yeniden doğrusallaştırma, çarpma sonrasında dereceyi eski hâline getirir. Sırada: yaklaşık aritmetik ve makine öğrenimi için CKKS.