BGV- und BFV-Verfahren für Ganzzahloperationen

BGV (Brakerski-Gentry-Vaikuntanathan, 2012) ist ein auf RLWE basierendes FHE-Schema mit festgelegter Stufe. Es unterstützt beliebige Additionen und Multiplikationen auf gepackten Ganzzahl-Klartexten. „Mit festgelegter Stufe“ bedeutet, dass es Schaltkreise bis zu einer bestimmten Tiefe L ohne Bootstrapping verarbeitet.

BGV und BFV codieren Klartexte als Polynome in Z_t[x]/(x^n+1), wobei t ein kleiner Klartext-Modulus ist (z. B. t=65537). Jedes Polynom codiert n Ganzzahlwerte (einen pro Koeffizient). Die Arithmetik auf Chiffraten wird gleichzeitig auf allen n Werten ausgeführt – SIMD-Parallelität.

BGV reduziert das Rauschen durch Modulus Switching: Nach jeder Multiplikation wird der Chiffrat-Modulus q von Q_L auf Q_{L-1} reduziert. Dadurch wird das Rauschen durch Q_L/Q_{L-1} geteilt und innerhalb des entschlüsselbaren Bereichs gehalten. Die Schaltkreistiefe L entspricht L Modulus-Stufen.

BFV (Brakerski/Fan-Vercauteren, 2012) ähnelt BGV, verwendet aber eine andere Strategie zur Rauschverwaltung: Es ist skalierungsinvariant. BFV benötigt kein Modulus Switching, sondern skaliert das Chiffrat nach der Multiplikation neu. Es ist einfacher zu implementieren und wird in Microsoft SEAL verwendet.

Mithilfe des chinesischen Restsatzes über dem Klartextring kann jedes Chiffrat n/2 unabhängige Ganzzahlwerte (Slots) enthalten. Eine Addition von Chiffraten addiert alle n/2 Paare parallel. Eine Multiplikation multipliziert alle Paare. Durchsatz: n/2 Ganzzahloperationen pro Chiffratoperation.

Nach der Multiplikation zweier Chiffrate vom Grad 1 hat das Ergebnis den Grad 2 (3 Komponenten). Die Relinearisierung verwendet Auswertungsschlüssel (Relin-Schlüssel), um zum Grad 1 zurückzukehren, wobei zusätzliches Rauschen entsteht. Dieser Schritt ist nach jeder Multiplikation erforderlich.

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

Eine Chiffratrotation verschiebt die n/2 Klartext-Slots zyklisch. Sie ist nützlich für: Sum-Reduce (alle Slots in einem akkumulieren), Matrix-Vektor-Multiplikation (rotieren und akkumulieren) sowie Faltungen (verschieben und multiplizieren). Dafür werden Galois-Schlüssel benötigt (vorberechnete Rotationsschlüssel).

BFV mit n=8192: Addition etwa 10 µs, Multiplikation etwa 5 ms (mit Relinearisierung). Bootstrapping (falls erforderlich): 30–60 Sekunden. Batch mit 4096 Ganzzahlen: amortisiert etwa 1 µs pro Ganzzahl und Multiplikation. Für Echtzeitverarbeitung unpraktisch, für Offline-Analysen jedoch geeignet.

Bei der Wahl von n und q empfiehlt SEAL n=4096 für 128-Bit-Sicherheit mit Q < 2^109 und n=8192 für größere Schaltkreise. Der HE-Standard (homomorphicencryption.org) stellt Parametertabellen bereit. Verwenden Sie immer empfohlene Parameter – individuelle Werte können die Sicherheit leicht beeinträchtigen.

Verschlüsselte Datenbankabfragen (verschlüsselte Datensätze durchsuchen, ohne sie zu entschlüsseln). Private Genomanalyse (Statistiken über verschlüsselte DNA berechnen). Verschlüsselte Finanzaggregation (verschlüsselte Kontostände summieren, ohne die einzelnen Werte einzusehen). Sichere Modellauswertung.

Welche Technik verwendet BGV, um das Anwachsen des Rauschens nach Multiplikationen zu verwalten?

BGV und BFV führen verschlüsselte Ganzzahlarithmetik auf Grundlage von RLWE aus. Batch-Codierung ermöglicht SIMD-Parallelität. BGV verwendet Modulus Switching, BFV ist skalierungsinvariant. Die Relinearisierung stellt den Grad nach einer Multiplikation wieder her. Als Nächstes folgt CKKS für approximative Arithmetik und ML.