Schémas BGV et BFV pour les opérations sur les entiers

BGV (Brakerski-Gentry-Vaikuntanathan, 2012) est un schéma FHE à niveaux fondé sur RLWE. Il prend en charge des additions et des multiplications arbitraires sur des textes en clair entiers regroupés. « À niveaux » signifie qu'il traite les circuits jusqu'à une profondeur fixe L sans rafraîchissement.

BGV et BFV encodent les textes en clair sous forme de polynômes dans Z_t[x]/(x^n+1), où t est un petit module de texte en clair (par exemple, t=65537). Chaque polynôme encode n valeurs entières, une par coefficient. Les opérations arithmétiques sur les textes chiffrés s'appliquent simultanément aux n valeurs — parallélisme SIMD.

BGV réduit le bruit par changement de module : après chaque multiplication, le module du texte chiffré q est réduit de Q_L à Q_{L-1}. Cela divise le bruit par Q_L/Q_{L-1}, maintenant le bruit dans des limites permettant le déchiffrement. La profondeur de circuit L correspond à L niveaux de module.

BFV (Brakerski/Fan-Vercauteren, 2012) est similaire à BGV, mais utilise une stratégie différente de gestion du bruit : l'invariance d'échelle. BFV n'exige pas de changement de module ; il remet plutôt le texte chiffré à l'échelle après la multiplication. Il est plus simple à implémenter et est utilisé dans Microsoft SEAL.

Grâce au théorème chinois des restes appliqué à l'anneau des textes en clair, chaque texte chiffré peut contenir n/2 valeurs entières indépendantes (emplacements). Une opération d'addition sur les textes chiffrés additionne en parallèle les n/2 paires. Une multiplication multiplie toutes les paires. Débit : n/2 opérations entières par opération sur un texte chiffré.

Après la multiplication de deux textes chiffrés de degré 1, le résultat est de degré 2 (3 composantes). La relinéarisation utilise des clés d'évaluation (clés de relinéarisation) pour revenir au degré 1, au prix d'un bruit supplémentaire. Cette étape est nécessaire après chaque multiplication.

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

La rotation d'un texte chiffré décale cycliquement les n/2 emplacements du texte en clair. Elle est utile pour : la réduction par somme (accumuler tous les emplacements en un seul), la multiplication matrice-vecteur (effectuer des rotations et accumuler), les convolutions (décaler et multiplier). Elle nécessite des clés de Galois (clés de rotation précalculées).

BFV avec n=8192 : addition d'environ 10 µs, multiplication d'environ 5 ms (avec relinéarisation). Rafraîchissement, si nécessaire : 30 à 60 secondes. Lot de 4096 entiers : environ 1 µs par entier et par multiplication, en coût amorti. Impraticable en temps réel, mais viable pour l'analyse hors ligne.

Pour choisir n et q : SEAL recommande n=4096 pour une sécurité de 128 bits avec Q < 2^109 ; n=8192 pour des circuits plus complexes. La norme HE (homomorphicencryption.org) fournit des tables de paramètres. Utilisez toujours les paramètres recommandés : des choix personnalisés peuvent facilement compromettre la sécurité.

Requêtes de base de données chiffrées (rechercher des enregistrements chiffrés sans les déchiffrer). Analyse génomique privée (calculer des statistiques sur de l'ADN chiffré). Agrégations financières chiffrées (additionner des soldes de comptes chiffrés sans voir les personnes concernées). Évaluation sécurisée de modèles.

Quelle technique BGV utilise-t-il pour gérer l'augmentation du bruit après les multiplications ?

BGV et BFV effectuent des opérations arithmétiques entières chiffrées à l'aide de RLWE. L'encodage par lots fournit un parallélisme SIMD. BGV utilise le changement de module ; BFV utilise l'invariance d'échelle. La relinéarisation rétablit le degré après la multiplication. Ensuite : CKKS pour l'arithmétique approchée et l'apprentissage automatique.