Efficient Mod Approximation and Its Applications to CKKS Ciphertexts

1. Problématique

Le schéma de chiffrement homomorphe (HE) CKKS est largement utilisé pour l'arithmétique approximative sur les nombres réels, permettant le traitement de vecteurs chiffrés via des opérations SIMD (Single Instruction Multiple Data). Cependant, CKKS ne supporte nativement que les opérations d'addition et de multiplication. Il est donc incapable d'exécuter directement des opérations non linéaires ou discontinues, telles que la fonction modulo ($x \mod p$), qui sont pourtant essentielles dans de nombreux protocoles cryptographiques et tâches de traitement de données.

Les défis principaux sont :

• Nature de la fonction : La fonction modulo est discontinue et périodique, ce qui rend son approximation par des polynômes (nécessaire en HE) extrêmement difficile sur tout le domaine d'entrée.
• Limitations des travaux existants : Les méthodes actuelles (comme celles utilisant des séries sinus ou des approximations de Chebyshev sur de petits intervalles) ne fournissent des résultats précis que sur des sous-ensembles restreints du domaine d'entrée, laissant de larges zones avec des erreurs inacceptables.
• Efficacité du stockage : L'utilisation de l'espace des messages (slots) dans CKKS est souvent sous-optimale, en particulier pour les petites entiers ou les données réelles (où la partie imaginaire est inutilisée), entraînant des coûts de communication et de calcul élevés lors du téléchargement de données chiffrées.

2. Méthodologie

L'auteur propose une approche en trois volets pour surmonter ces obstacles :

A. Approximation précise de la fonction Modulo

Au lieu d'essayer d'approximer la fonction modulo sur un intervalle continu large avec une erreur uniforme, l'article propose une méthode basée sur l'interpolation polynomiale et les séries de Chebyshev spécifiquement pour les points entiers dans un intervalle borné $[0, B]$.

• Échantillonnage : La fonction est traitée comme un ensemble de points discrets $(i, i \mod p)$ pour $i \in [0, B]$.
• Séries de Chebyshev : Une série de Chebyshev de première espèce est utilisée pour approximer ces points. Cela permet de minimiser le phénomène de Runge et d'assurer une stabilité numérique grâce à la décroissance rapide des coefficients.
• Stabilité et Mise à l'échelle : Pour éviter l'amplification du bruit de chiffrement lors de l'évaluation homomorphe, les coefficients de Chebyshev sont divisés par un facteur d'échelle $\delta$. Ce facteur est choisi de manière itérative pour garantir que les valeurs intermédiaires lors de l'évaluation (via la méthode de Paterson-Stockmeyer) restent inférieures à 1, évitant ainsi l'explosion de l'erreur.
• Résultat : Une approximation polynomiale précise sur tout l'intervalle d'entrée, avec des erreurs de l'ordre de $10^{-8}$.

B. Schémas d'emballage de données (Data Packing)

Pour améliorer l'utilisation de l'espace des slots CKKS, deux nouveaux schémas sont conçus pour les petites entiers :

1. BitStack :
   • Principe : Empilement binaire. Les données sont représentées sous forme de chaînes binaires concaténées.
   • Dépaquetage : Utilise la fonction modulo homomorphe pour extraire séquentiellement les couches de bits (ex: $a_1 = x \mod 2^{l_1}$, puis soustraction et division).
   • Avantage : Structure très compacte.
   • Inconvénient : Dépaquetage séquentiel, ce qui consomme de la profondeur multiplicative et accumule les erreurs.
2. CRTStack (Basé sur le Théorème des Restes Chinois) :
   • Principe : Utilise un système de congruences avec des moduli premiers entre eux ($P_1, P_2, \dots$) pour combiner les données en un seul entier.
   • Dépaquetage : Les données peuvent être extraites en parallèle en appliquant simplement la fonction modulo avec chaque $P_i$.
   • Avantage : Dépaquetage parallèle, erreurs indépendantes par couche, meilleure précision globale.

C. Combinaison et Optimisation

Les auteurs montrent comment combiner ces méthodes avec des techniques existantes comme VecConcat (concaténation de vecteurs) et ImgConcat (utilisation de la partie imaginaire pour doubler la capacité de stockage des données réelles), permettant une flexibilité maximale pour différents types de données.

3. Contributions Clés

1. Nouvelle approximation du Modulo : Une méthode robuste permettant d'approximer la fonction modulo sur l'ensemble des points entiers d'un intervalle borné avec une haute précision, comblant le vide laissé par les méthodes existantes qui échouent sur la moitié du domaine.
2. BitStack et CRTStack : Deux schémas d'emballage efficaces qui réduisent considérablement la surcharge de calcul et de communication pour le téléchargement de petits entiers chiffrés.
3. Arrondi Homomorphe : Implémentation d'une fonction d'arrondi (Floor, Ceil, Round) pour CKKS basée sur l'approximation du modulo, atteignant une erreur de $10^{-10}$ pour les petits entiers.
4. Conversion Secret Share $\to$ CKKS : Première réalisation complète d'une transformation des partages secrets additifs vers des chiffrés CKKS sans modifier les schémas de partage sous-jacents, comblant ainsi le fossé entre le calcul multipartite sécurisé (MPC) et le chiffrement homomorphe.

4. Résultats Expérimentaux

Les expériences ont été menées sur un processeur Intel Xeon Gold avec la bibliothèque OpenFHE :

• Précision de l'approximation :
  • La méthode proposée atteint une erreur absolue moyenne de l'ordre de $10^{-8}$ (pour un degré polynomial de 45-50), surpassant largement les méthodes de référence (Lee et al. [LLL+21] et OpenFHE standard) qui affichent des erreurs de l'ordre de 1 à 2 sur la même plage.
  • L'erreur diminue avec l'augmentation du degré du polynôme.
• Performance de dépaquetage (BitStack) :
  • La méthode basée sur le modulo proposé est beaucoup plus rapide (environ 15 secondes pour $2^{15}$ éléments) que les méthodes alternatives utilisant la comparaison ou la conversion vers FHEW (qui prennent plus de 900 secondes).
  • L'erreur est réduite de plusieurs ordres de grandeur par rapport aux méthodes de comparaison.
• Comparaison avec Transcipher (Rubato) :
  • Par rapport au cadre Transcipher (Rubato), la méthode proposée réduit le temps de chiffrement côté client et le temps de dépaquetage serveur (156s contre 407s).
  • L'erreur après dépaquetage est un ordre de grandeur plus faible ($4.00 \times 10^{-6}$ contre $7.54 \times 10^{-5}$).
  • La méthode est particulièrement avantageuse dans des scénarios à bande passante modérée.
• Conversion de Partages Secrets :
  • La reconstruction de chiffrés CKKS à partir de partages secrets additifs est réalisée avec une erreur de l'ordre de $10^{-8}$, même avec un nombre croissant de participants.

5. Signification et Impact

Ce travail est significatif pour plusieurs raisons :

• Extension des capacités de CKKS : Il rend possible l'exécution de fonctions discontinues essentielles (modulo, arrondi) directement sur des chiffrés CKKS, élargissant ainsi le champ d'application de ce schéma au-delà de l'arithmétique purement linéaire.
• Efficacité pour les données réelles et petites entiers : Les schémas BitStack et CRTStack offrent des solutions pratiques pour les applications réelles comme l'analyse génomique (petits entiers) ou le traitement d'images, où la réduction de la taille des données chiffrées est critique pour la scalabilité.
• Interopérabilité MPC-HE : La capacité de convertir directement des partages secrets additifs en chiffrés CKKS ouvre la voie à des architectures hybrides plus fluides, permettant de combiner les avantages du MPC (stockage faible coût) et du HE (traitement sans interaction).
• Limitation et Perspective : La méthode est actuellement limitée aux petits entiers (intervalle d'entrée $B$ restreint, typiquement quelques centaines), ce qui l'empêche d'être utilisée pour le bootstrapping de CKKS (qui nécessite de grandes plages). Cependant, elle répond parfaitement aux besoins de nombreuses applications de calcul privé sur des données structurées de petite taille.

En résumé, cet article propose une avancée technique majeure pour rendre le chiffrement homomorphe CKKS plus polyvalent et efficace pour des applications pratiques impliquant des opérations non linéaires et une gestion optimisée de la bande passante.