Appliquer des opérations homomorphes sur des données chiffrées volumineuses

Aug 18 2020

En cours d'expérimentation sur le cryptage homomorphe à l'aide de la bibliothèque PALISADE .

Je souhaite appliquer des opérations simples telles que des ajouts et des multiplications sur de grandes entrées cryptées. Par exemple, l'entrée A[3200]et l'entrée des B[4096]deux vecteurs / tableaux de valeurs int sont chiffrées. Avec ces deux entrées Enc(A)et Enc(B)je veux appliquer une multiplication:

EvalMult(Enc(A[0]), Enc(B[42])) 

*0 and 42 denoting the indexes of the corresponding inputs
** no SIMD needed

En ce qui me concerne, la mise en œuvre des exigences décrites ci-dessus pourrait être résolue de deux manières différentes:

  1. Emballez les entrées dans un seul texte chiffré (comme SIMD) et pour les opérations que je pourrais utiliser EvalIndexAt()pour obtenir la bonne valeur de l'entrée cryptée.

  2. Cryptez chaque valeur de A et B séparément.

Je ne sais pas vraiment quelles solutions seraient les meilleures en termes d' efficacité . La première approche a cet avantage majeur qu'un seul processus de cryptage pour l'ensemble de l'entrée est nécessaire, mais cela présente l'inconvénient que je dois toujours accéder au bon élément en utilisant la EvalAtIndex()méthode et plus les entrées sont grandes, plus le calcul des get est lent EvalAtIndexKeyGen(). (Au moins sur ma machine)

La deuxième approche semble la mieux adaptée car elle EvalAtIndex()n'est pas nécessaire, mais elle entraîne le coût de chiffrement de chaque valeur séparément, ce qui prend un certain temps.

Des recommandations de pensées?

Réponses

1 YuriyPolyakov Aug 19 2020 at 15:00

Merci pour la question.

Le principal avantage de l'approche n ° 1 (SIMD) est que vous pouvez effectuer l'addition et la multiplication de vecteurs (de 4096 entiers / nombres réels ou plus) en utilisant une seule addition ou multiplication homomorphe (très efficace). La rotation (appelée EvalAtIndexdans PALISADE) est une opération supplémentaire qui permet d'accéder à des indices individuels ou de faire une sommation efficace (comme dans le produit interne), une multiplication de matrice, etc. Cette approche a également un facteur d'expansion du texte chiffré beaucoup plus petit (de 4096x ou plus) que approche n ° 2. En général, l'option n ° 1 est préférée dans la pratique (et je ne peux penser à aucun cas d'utilisation réel où je voudrais aller avec l'option n ° 2).

Pour minimiser le coût de la multiplication, vous pourriez peut-être emballer le vecteur dans des blocs contigus de sorte que vous ayez besoin d'une seule rotation pour un bloc. Par exemple,

EvalMult(Enc(A[0:5]),Enc(B[42:47))

Une autre technique que vous pouvez utiliser est EvalFastRotation(disponible uniquement pour CKKS et BGVrns dans PALISADE v1.10.x). Si vous avez besoin de plusieurs rotations du même texte chiffré, vous pouvez précalculer quelque chose pour le texte chiffré, puis utiliser des rotations moins chères (le plus grand avantage est obtenu pour la commutation de clé BV) - voirhttps://gitlab.com/palisade/palisade-development/-/blob/master/src/pke/examples/advanced-real-numbers.cpp à titre d'exemple.

Il existe également des moyens de minimiser le nombre de clés à générer si vous avez besoin de plusieurs rotations (ne calculez qu'en gros une racine carrée du nombre de rotations nécessaires), par exemple, en utilisant la technique du baby-step-giant-step décrite dans https://eprint.iacr.org/2018/244 (ces techniques peuvent être implémentées dans votre application basée sur PALISADE).

Vous pouvez également utiliser un ordre spécial d'emballage d'un vecteur si le modèle pour effectuer la multiplication est connu (de cette façon, votre rotation préparera plusieurs blocs à travers le vecteur en utilisant une seule opération de rotation). Les rotations sont cycliques (bouclage) à la fois dans CKKS et BGVrns lorsque le # emplacements en texte brut (taille du lot) est égal à ring dimension/ 2. Si vous avez un vecteur plus petit que cela, vous pouvez toujours cloner / répliquer le petit vecteur autant de fois que nécessaire remplir ring dimension/ 2.

En résumé, la plus grande amélioration d'efficacité peut être obtenue si vous pensez à votre problème en termes de vecteurs de type SIMD. Ensuite, vous pouvez reformuler votre problème / modèle pour tirer pleinement parti du jeu d'outils fourni par HE. D'une certaine manière, ceci est similaire à la programmation utilisant des instructions vectorisées, par exemple AVX, ou une programmation orientée matrice (comme dans MATLAB).