BGV- og BFV-skemaer til heltalsoperationer

BGV (Brakerski-Gentry-Vaikuntanathan, 2012) er et niveauinddelt FHE-skema baseret på RLWE. Det understøtter vilkårlige additioner og multiplikationer på pakkede heltalsklartekster. "Niveauinddelt" betyder, at det håndterer kredsløb op til en fast dybde L uden bootstrapping.

BGV og BFV koder klartekster som polynomier i Z_t[x]/(x^n+1), hvor t er en lille klartekstmodulus (f.eks. t=65537). Hvert polynomium koder n heltalsværdier, én pr. koefficient. Aritmetik på chiffertekster udføres samtidigt på alle n værdier — SIMD-parallelisme.

BGV reducerer støj ved modulusskift: efter hver multiplikation reduceres chiffertekstens modulus q fra Q_L til Q_{L-1}. Det dividerer støjen med Q_L/Q_{L-1}, så støjen holdes inden for grænser, hvor dekryptering stadig fungerer. Kredsløbsdybden L svarer til L modulusniveauer.

BFV (Brakerski/Fan-Vercauteren, 2012) minder om BGV, men bruger en anden strategi til støjhåndtering: den er skala-invariant. BFV kræver ikke modulusskift; i stedet omskaleres chifferteksten efter multiplikation. Det er enklere at implementere og bruges i Microsoft SEAL.

Via den kinesiske restsætning over klartekstringen kan hver chiffertekst indeholde n/2 uafhængige heltalsværdier (pladser). En addition af chiffertekster lægger alle n/2 par sammen parallelt. En multiplikation multiplicerer alle par. Gennemløb: n/2 heltalsoperationer pr. chiffertekstoperation.

Efter multiplikation af to chiffertekster af grad 1 har resultatet grad 2 (3 komponenter). Relinearisering bruger evalueringsnøgler (relin-nøgler) til at konvertere tilbage til grad 1 på bekostning af øget støj. Dette trin kræves efter hver multiplikation.

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

Rotation af chifferteksten forskyder de n/2 klartekstpladser cyklisk. Det er nyttigt til: sum-reduce (akkumulér alle pladser i én), matrix-vektor-multiplikation (rotér og akkumulér) og foldninger (forskyd og multiplicér). Kræver Galois-nøgler (forudberegnede rotationsnøgler).

BFV med n=8192: addition ~10 µs, multiplikation ~5 ms (med relinear­isering). Bootstrapping (hvis nødvendigt): 30-60 sekunder. Batch på 4096 heltal: amortiseret ~1 µs pr. heltal pr. multiplikation. Upraktisk i realtid, men anvendeligt til offline-analyse.

Valg af n og q: SEAL anbefaler n=4096 for 128-bit-sikkerhed med Q < 2^109 og n=8192 til større kredsløb. HE-standarden (homomorphicencryption.org) indeholder parametertabeller. Brug altid de anbefalede parametre — tilpassede valg kan nemt underminere sikkerheden.

Krypterede databaseforespørgsler (søg i krypterede poster uden at dekryptere dem). Privat genomisk analyse (beregn statistikker på krypteret DNA). Krypterede finansielle sammenlægninger (læg krypterede kontosaldi sammen uden at se de enkelte saldi). Sikker model­evaluering.

BGV og BFV udfører krypteret heltalsaritmetik ved hjælp af RLWE. Batchkodning giver SIMD-parallelisme. BGV bruger modulusskift; BFV bruger skala-invarians. Relinearisering gendanner graden efter multiplikation. Næste emne: CKKS til approksimativ aritmetik og ML.