Qu’est-ce que le chiffrement homomorphe hybride et ses applications ?

9.2.2023 10:03

 

TL;DR

Introduire le concept de cryptage homomorphique hybride, ses cas d’utilisation, une brève formulation et uncode de démonstration en C++.

Introduction

Les applications préservant la vie privée sont devenues un sujet important de nos jours en raison des préoccupations croissantes des gens concernant la confidentialité de leurs données, de la prévalence des applications d’apprentissage automatique qui nécessitent l’accès à une grande quantité de données, et des nouvelles réglementations telles que le règlement général sur la protection des données (RGPD), sans parler d’autres préoccupations éthiques et financières. Aujourd’hui, nous allons découvrir une nouvelle technique d’amélioration de la confidentialité appelée chiffrement homomorphe hybride (HHE), qui est une extension du chiffrement homomorphe (HE).

L’HE est une technique de cryptage qui permet d’effectuer des calculs sur des données cryptées. Cependant, l’un des problèmes de HE est que ses cryptogrammes sont plusieurs ordres de grandeur plus grands que les cryptogrammes correspondants. Le HHE vise à résoudre ce problème en combinant les chiffrements symétriques avec le HE afin de réduire la taille des textes chiffrés et les ressources informatiques requises pour la partie qui chiffre et envoie les données (par exemple, un client / propriétaire de données) au prix de calculs plus coûteux pour la partie qui effectue des calculs sur les données chiffrées (par exemple, un serveur, un fournisseur de services en nuage, ou CSP). Par conséquent, HHE peut être plus adapté que HE lorsqu’il s’agit du modèle client-serveur de calculs cryptés, en particulier lorsque le client dispose de ressources informatiques et d’une bande passante internet limitées, par exemple, les téléphones, les appareils IoT, etc.

Avantages :

• Permettre des calculs sur des données cryptées et donc permettre des analyses et des applications de données préservant la vie privée
• Réduire la taille du texte chiffré, et donc réduire les ressources de calcul et de bande passante nécessaires à la partie qui possède, chiffre et envoie les données.

Inconvénients :

• Plus coûteux en termes de calcul dans le domaine du calcul crypté
• Actuellement, il est encore limité à certains types de données et de calculs.

Cas d’utilisation

Comme l’HE, le HHE peut soutenir des applications dans des secteurs où la confidentialité des données est une préoccupation importante, comme la finance, les soins de santé, la réglementation, etc. En outre, le HHE peut renforcer les applications sur des appareils dont la puissance de calcul, la mémoire et la bande passante réseau sont limitées, tels que les appareils embarqués et les appareils IoT.

Exemple d’application : Une application de surveillance à domicile pour les soins de santé, dans laquelle les appareils IoT équipés dans un foyer prennent des photos (ou d’autres signaux), les cryptent et envoient les signaux cryptés au serveur. Le serveur exécute un algorithme d’intelligence artificielle sur les données cryptées reçues et détecte des événements tels que des attaques d’apoplexie, puis envoie les résultats cryptés à l’appareil du ménage qui est chargé de décrypter les résultats et de déclencher une alarme uniquement si le résultat décrypté est positif, par exemple si des personnes ont été victimes d’une attaque d’apoplexie. De cette manière, le ménage peut utiliser le service du serveur tandis que le fournisseur de services ne voit pas les photos ou les données sensibles du ménage.

Entrons dans le vif du sujet

Voici quelques brèves formulations de l’ES et de l’ESH.

Chiffrement homomorphe

Avant d’aborder l’ES, il faut d’abord comprendre ce qu’est l’ES. Avec HE, nous pouvons crypter les données et effectuer des opérations sur les données cryptées. Le résultat du décryptage sera équivalent à celui obtenu en effectuant des opérations similaires sur les données en clair correspondantes. Pour mieux comprendre HE, je vous renvoie à ce qui suit article de blog d’OpenMined.

Nous allons maintenant examiner la définition d’un système de cryptage homomorphe à clé publique, qui est tirée de [1] et qui se compose de quatre algorithmes :

1. HE.KeyGen(1ⁿ) → (pk, sk, evk) : L’algorithme de génération de clés. Ici, n est un paramètre de sécurité ; pk, sk et evk sont respectivement la clé publique, la clé secrète et la clé d’évaluation. Nous utilisons pk pour crypter les données, sk pour décrypter les données cryptées, et evk pour effectuer des calculs sur des données cryptées
2. HE.Enc(pk, m) → c: L’algorithme de cryptage HE où m est la donnée en clair et c est la donnée cryptée HE.
3. HE.Eval(evk, f, c₁, c₂, … cᵢ) → c’ : L’algorithme d’évaluation où f est une fonction telle que l’addition ou la multiplication, et c‘ est le résultat chiffré de l’HE. Nous aurions dû HE.Dec(sk, c’) = f(m₁, m₂, …, mᵢ)
4. HE.Dec(sk, c) → m: L’algorithme de décryptage HE qui prend sk et le texte chiffré c pour créer le message en clair m

Chiffrement homomorphe hybride

Au lieu de chiffrer les données à l’aide d’un schéma HE qui produit un texte chiffré très volumineux (expansion d’ordre multiple par rapport au texte en clair), HHE les chiffre à l’aide d’un algorithme de chiffrement symétrique avec un facteur d’expansion de 1 et envoie les textes chiffrés symétriques au serveur. En outre, le client doit également envoyer une version cryptée homomorphique de sa clé symétrique. Dès réception, le serveur exécute l’algorithme de décryptage symétrique de manière homomorphique pour transformer le texte chiffré symétrique en un texte chiffré homomorphique. Ensuite, le serveur peut effectuer des calculs sur les données cryptées. Plus formellement, nous pouvons définir un schéma HHE (selon [2]) qui consiste en 5 algorithmes comme suit

1. HHE.KeyGen(1ⁿ) →(pk, sk, evk) : Il s’agit simplement de l’algorithme HE.KeyGen qui produit la clé publique HE(pk), la clé secrète(sk) et la clé d’évaluation(evk).
2. HHE.Enc(1ⁿ, pk, m) : L’algorithme de cryptage HHE.
   Tout d’abord, il crée une clé symétrique : SYM.KGen(1ⁿ) → k
   Ensuite, à l’aide de cette clé symétrique, il chiffre le message en clair m : SYM.Enc(k, m) → cₛ. Ici, cₛ est le texte chiffré symétrique qui sera envoyé au serveur. Il convient de noter que cₛ a la même taille que m.
   En outre, HHE.Enc crypte également de manière homomorphique la clé symétrique k en utilisant HE.Enc(pk, k) → cₖ. Par conséquent, cₖ est le texte chiffré HE de la clé symétrique k, et sera également envoyé au serveur avec la mention cₛ
3. HHE.Decomp(evk, cₖ, cₛ) → c: L’algorithme de décomposition HHE qui transforme le texte chiffré symétrique cₛ dans le texte chiffré HE c en évaluant de manière homomorphique l’algorithme de décryptage symétrique à l’aide de cₖ et cₛ : HE.Eval(evk, f=SYM.Dec, cₖ, cₛ) → c
4. HHE.Eval(evk, f, c₁, . . . , cᵢ) → c’: L’algorithme d’évaluation HHE qui renvoie simplement HE.Eval(evk, f, c₁, . . . , cᵢ)
5. HHE.Dec(sk, c) : L’algorithme de décryptage HHE. Il renvoie simplement HE.Dec(sk, c)

Notez qu’à l’étape 2, nous devons envoyer cₖ et cₛ au serveur. Ici, cₖ est le texte chiffré HE et peut être de grande taille. Cependant, il suffit d’envoyer cₖ au serveur une fois, par exemple lors d’une phase d’installation. Le serveur peut l’utiliser à plusieurs reprises dans le HHE.Decomp pour transformer les nouveaux cryptogrammes symétriques en cryptogrammes HE correspondants. C’est la principale différence entre HHE et HE : au lieu d’envoyer à chaque fois des cryptogrammes HE au serveur, ce qui peut être très gourmand en bande passante, HHE envoie des cryptogrammes symétriques légers. Cette astuce permet à HHE de fonctionner avec des appareils aux ressources limitées, car les algorithmes de chiffrement symétriques sont également très légers à exécuter.

Êtes-vous prêt pour un peu de code ?

Avant de plonger dans le code, passons en revue le protocole que nous allons construire : Nous avons deux parties (un client et un serveur) dont les actions peuvent être résumées en 3 étapes principales :

1. Le client crée les clés avec HHE.KeyGen, chiffre les données avec HHE.Enc et envoie au serveur le texte chiffré symétrique de ses données(cₛ), le texte chiffré HE de sa clé symétrique(cₖ), les clés HE à l’exception de la clé secrète sk .
2. Le serveur exécute l’algorithme HHE.Decomp et une transformation linéaire sur les données cryptées HE du client à l’aide de HHE.Eval, obtient le résultat crypté et le renvoie au client.
3. Dès réception, le client décrypte le résultat avec HHE.Dec et obtient le résultat final en clair.

L’intégralité des code de démonstration est en C++ et s’appuie sur l’application Le SEAL de Microsoft et Bibliothèque de pâtes. Tout d’abord, créons deux structures qui représentent le client et le serveur :

struct Client
{
    // the HE keys
    seal::PublicKey he_pk;  // HE public key
    seal::SecretKey he_sk;  // HE secret key
    seal::RelinKeys he_rk;  // HE relinearization key (you don't have to care about this)
    seal::GaloisKeys he_gk; // HE galois key (you don't have to care about this)
    // client's symmetric keys
    std::vector<uint64_t> k;           // the secret symmetric keys
    std::vector<seal::Ciphertext> c_k; // the HE encrypted symmetric keys
    // client's data
    std::vector<uint64_t> m{0, 5, 255, 100, 255}; // the client's secret data
    std::vector<uint64_t> c_s;                    // the symmetric encrypted data
    seal::Ciphertext c_res;                       // the HE encrypted result received from the server
};

struct Server
{
    std::vector<int64_t> w{-1, 2, -3, 4, 5};    // dummy weights
    std::vector<int64_t> b{-5, -5, -5, -5, -5}; // dummy biases
    std::vector<seal::Ciphertext> c;            // the HE encrypted ciphertext of client's data
    seal::SecretKey he_sk;                      // the server's HE secret key
    seal::Ciphertext c_res;                     // the HE encrypted results that will be sent to the client
};

Client client;
Server server;

Étape 1

Le client crée le contexte SEAL qui est responsable de la création des clés HE et d’autres objets SEAL pour le codage, le cryptage et le décryptage des données (BatchEncoder, Encryptor, Decryptor, Evaluator).

std::shared_ptr<seal::SEALContext> context = sealhelper::get_seal_context();
sealhelper::print_parameters(*context);
seal::KeyGenerator keygen(*context);
keygen.create_public_key(client.he_pk);
client.he_sk = keygen.secret_key();
keygen.create_relin_keys(client.he_rk);
seal::BatchEncoder he_benc(*context);
seal::Encryptor he_enc(*context, client.he_pk);
seal::Evaluator he_eval(*context);
seal::Decryptor he_dec(*context, client.he_sk);
bool use_bsgs = false;
std::vector<int> gk_indices = pastahelper::add_gk_indices(use_bsgs, he_benc);
keygen.create_galois_keys(gk_indices, client.he_gk);

Le client exécute ensuite l’algorithme de chiffrement(HHE.Enc) pour créer la clé symétrique(client.k) et le texte chiffré symétrique(client.c_s).

client.k = pastahelper::get_symmetric_key();
pasta::PASTA SymmetricEncryptor(client.k, configs::plain_mod);
client.c_s = SymmetricEncryptor.encrypt(client.m);

Si nous imprimons les valeurs de client.c_s, nous verrons un vecteur de valeurs aléatoires telles que [30446, 62410, 62969, 38863, 43376], contrairement aux données en clair du client [0, 5, 255, 100, 255]. Le client n’enverra au serveur que le vecteur de valeurs aléatoires et jamais ses données en clair.

Ensuite, le client chiffre sa clé symétrique(client.k) à l’aide de HE pour créer client.c_k.

client.c_k = pastahelper::encrypt_symmetric_key(client.k,
                                                configs::USE_BATCH,
                                                he_benc,
                                                he_enc);

Ensuite, le client envoie au serveur client.c_k, client.c_s et les clés HE, à l’exception de la clé secrète.

Étape 2

Après avoir reçu le client.c_k, le serveur crée sa propre clé secrète HE, l’objet HHE et exécute l’algorithme de décomposition qui aboutit à server.c qui est le texte chiffré HE du message en clair du client m. Notez que le client n’envoie jamais sa clé secrète he_sk au serveur, de sorte que le serveur ne sera pas en mesure de décrypter l’information. server.c.

seal::KeyGenerator csp_keygen(*context);
server.he_sk = csp_keygen.secret_key();
pasta::PASTA_SEAL HHE(context, client.he_pk, server.he_sk, client.he_rk, client.he_gk);
server.c = HHE.decomposition(client.c_s, client.c_k, configs::USE_BATCH);

Le serveur code ensuite ses poids w et ses biais b et effectue une multiplication vectorielle par éléments ainsi qu’une addition sur ses poids et biais en clair avec les données cryptées HE server.c.

seal::Plaintext plain_w, plain_b;
he_benc.encode(server.w, plain_w);
he_benc.encode(server.b, plain_b);
server.c_res = sealhelper::he_mult(he_eval, server.c[0], plain_w);
client.c_res = sealhelper::he_add(he_eval, server.c_res, plain_b);

Nous pouvons voir que le résultat final est client.c_res qui est le texte chiffré SEAL que le client recevra.

Étape 3

Enfin, le client déchiffre son c_res à l’aide de sa clé secrète :

std::vector<int64_t> decrypted_res = sealhelper::decrypt(client.c_res,
                                                         client.he_sk,
                                                         he_benc,
                                                         *context,
                                                         client.m.size());

En imprimant decrypted_res, nous verrons que le résultat sera [-5 5 -770 395 1270], ce qui est correct car

[0, 5, 255, 100, 255]
⊙
[-1, 2, -3, 4, 5]
⊕
[-5, -5, -5, -5, -5]
=
[-5, 5, -770, 395, 1270]

où ⊙, ⊕ sont respectivement la multiplication et l’addition de vecteurs par élément.

Le résultat de l’exécution du code de démonstration est visible dans l’image ci-dessous

Orientations futures et conclusions

Dans cet article, nous avons découvert le chiffrement homomorphe hybride, ses avantages par rapport au chiffrement homomorphe ordinaire, un exemple d’utilisation du chiffrement homomorphe hybride et un protocole de démonstration très simple en C++. Dans la pratique, ce protocole peut être étendu à trois parties, ce qui convient à l’analyse de données cryptées ou à l’apprentissage automatique. Vous pouvez en savoir plus sur le protocole HHE tripartite dans un article récemment publié [3] sur notre site Web. Laboratoire NISEC à l’université de Tampere. J’espère que cet article vous sera utile et que vous prendrez plaisir à apprendre quelque chose de nouveau !

Remerciements

Ce travail a été financé par leprojet européen HARPOCRATES ( ).

Référence

[1] Brakerski, Zvika, et Vinod Vaikuntanathan. “Chiffrement efficace entièrement homomorphe à partir de LWE (standard)”. SIAM Journal on computing 43.2 (2014) : 831-871.

[2] Dobraunig, Christoph, et al. “Pasta : un cas de cryptage homomorphique hybride”. Cryptology ePrint Archive (2021).

[3] Alexandros Bakas, Eugene Frimpong, Antonis Michalas. “Déguisement symétrique : Réalisation de services de cryptage homomorphes à partir de primitives symétriques”. EAI SECURECOMM (2022).

Rédigé par : Khoa Nguyen, Université de Tampere