- Dans les logiciels local-first, le chiffrement homomorphe (Homomorphic Encryption) est combiné aux CRDT afin de préserver la sécurité des documents collaboratifs
- Le chiffrement de bout en bout ne permet pas, à lui seul, au serveur de fusionner les données, ce qui impose des limitations en matière de synchronisation et d’efficacité des mises à jour
- Le chiffrement homomorphe est une technique qui permet l’exécution de programmes afin que le serveur puisse fusionner des mises à jour de CRDT sans connaître le contenu
- Mais en raison des limites fondamentales du chiffrement homomorphe (baisse des performances, augmentation de l’espace et du volume de calcul, nécessité de faire fonctionner le code selon le pire cas), son application concrète présente des difficultés majeures
- Diverses approches sont étudiées pour faire coexister les CRDT et le calcul sécurisé, et aucune solution complète n’a encore été trouvée
Le défi du local-first et de la collaboration sécurisée
- En collaboration à distance, les documents sont stockés sous forme de CRDT dans une approche local-first, puis synchronisés afin d’offrir une expérience d’édition collaborative
- Lorsqu’il existe une exigence de sécurité selon laquelle le contenu des documents ne doit jamais être exposé à un tiers, y compris au développeur de l’application, le chiffrement de bout en bout est une méthode couramment utilisée
- Le chiffrement de bout en bout est simple dans son fonctionnement, mais comme le serveur de synchronisation ne peut pas fusionner les données, un travail asynchrone prolongé entraîne des communications de données inefficaces
Qu’est-ce que le chiffrement homomorphe ?
- Le chiffrement homomorphe est une forme spéciale de chiffrement qui permet d’exécuter directement des algorithmes sur des données chiffrées
- Cela permet au serveur de synchronisation d’effectuer la fusion des mises à jour de CRDT sans connaître le contenu des données
- Selon le type d’opérations prises en charge, on distingue le partiellement homomorphe (addition ou multiplication seulement), le somewhat/leveled homomorphic (les deux, mais un nombre limité de fois), et le pleinement homomorphe (sans restriction)
- Plus le nombre d’opérations augmente, plus du bruit s’accumule dans le texte chiffré et rend le déchiffrement difficile, ce qui exige des techniques avancées comme le bootstrapping
- Au niveau des bits chiffrés (0/1), il est possible d’implémenter des circuits booléens généraux en ne combinant que des portes d’opérations de base comme XOR et AND
Exemple concret d’implémentation de CRDT avec chiffrement homomorphe
- Avec la bibliothèque Rust TFHE-rs, un CRDT représentatif appelé Last Write Wins Register a été implémenté à l’aide du chiffrement homomorphe
- Les champs et méthodes (chiffrement/déchiffrement) de la structure en clair et de la structure chiffrée sont presque identiques, mais une différence importante apparaît dans la logique de fusion proprement dite
- Comme les bifurcations de chemin d’exécution, via des instructions if/else ou match, peuvent donner des indices permettant de déchiffrer le texte chiffré, un environnement chiffré impose d’évaluer immédiatement toutes les branches et boucles
- Les comparaisons de conditions importantes et les opérations de fusion sont toutes traitées au niveau bit à bit via des opérateurs FheBool et des méthodes comme
select, de sorte qu’il est impossible pour un observateur externe de détecter dans quelles conditions la valeur a changé
Limites fondamentales du chiffrement homomorphe
- Déséquilibre entre taille des clés et taille des données : dans l’exemple, il faut une clé serveur de 123 Mo pour 32 octets de données (27 Mo même après compression), ce qui crée une forte inefficacité de stockage
- Dégradation des performances : la fusion d’un CRDT chiffré homomorphiquement a été mesurée à environ 1 seconde, soit près de 2 milliards de fois plus lentement que sans chiffrement
- Si les boucles et bifurcations varient selon les valeurs d’entrée, cela entraîne une fuite d’information ; il faut donc toujours consommer calcul et mémoire selon le pire cas
- Par exemple, même lorsqu’une structure comme une last-write-wins map a des paires clé-valeur clairsemées, il faut fusionner toutes les clés dans une taille fixe entièrement remplie, ce qui dégrade fortement l’évolutivité réelle
- Il faut concevoir le système de sorte qu’un observateur externe ne puisse pas déduire, à partir de la structure du texte chiffré ou de l’historique des modifications, si une valeur a changé ni quelle partie a été mise à jour
Conclusion et perspectives
- Les CRDT et le chiffrement homomorphe peuvent théoriquement être combinés de manière naturelle, mais en pratique ils souffrent de contraintes critiques en matière d’efficacité en espace/temps et de structure de programme
- À ce stade, aucune solution entièrement pratique n’a émergé, mais les CRDT eux-mêmes étant une technologie encore relativement jeune, la recherche continue
- Dans les applications collaboratives local-first, le potentiel de solutions innovantes pour équilibrer sécurité et utilisabilité reste bien réel
1 commentaires
Avis Hacker News
Il est vrai que le domaine du chiffrement entièrement homomorphe est vraiment lent et inefficace, mais il faut rappeler qu’il s’agit d’un champ relativement récent, apparu en 2009 ; les progrès accomplis ces 15 dernières années sont réellement impressionnants. Les premiers schémas de chiffrement homomorphe nécessitaient des clés de plusieurs To/Pio, et le bootstrapping (une opération indispensable en chiffrement homomorphe quand les multiplications s’accumulent) prenait des milliers d’heures. Aujourd’hui, les clés font environ 30 Mo et le bootstrapping peut s’effectuer en moins de 0,1 seconde. J’espère que cela continuera à progresser jusqu’au jour où ce sera réellement utilisable en pratique.
Les premiers CRDT (CRDT : Conflict-free Replicated Data Type) étaient eux aussi très peu pratiques, comme WOOT, mais les bases de données CRDT récentes n’ont plus des performances si éloignées d’un LSM classique. Par exemple, les CRDT RDX fonctionnent avec un algorithme proche du merge sort, donc tout est en O(N). Dans la plupart des implémentations, la surcharge de métadonnées est également bien maîtrisée. Voir WOOT, librdx, go-rdx.
De par leur architecture, les CRDT sont forcément lents, et même les meilleurs algorithmes ont un coût structurel élevé. Si on y ajoute le chiffrement homomorphe, la difficulté grimpe encore fortement. C’est vraiment impressionnant, mais je me demande si c’est réellement exploitable. À l’appui de cette critique, la personne cite l’explication suivante : « pour que le serveur calcule une nouvelle map, il doit fusionner toutes les clés une par une, puis envoyer la map complète à chaque pair — car du point de vue du serveur, la map entière est différente à chaque fois ».
CRDT signifie Conflict-free Replicated Data Type, soit un type de données spécial permettant une synchronisation distribuée sans conflit. Voir le lien Wikipédia sur les CRDT.
L’article mentionne un manque de performances, et en effet, sur un M4 MacBook Pro, un registre last write wins exécuté normalement met 0,52 nanoseconde pour une fusion, alors que la version chiffrée homomorphiquement demande 1,06 seconde. Autrement dit, il y a un écart de vitesse d’environ 2 milliards de fois. C’est un chiffre vraiment sidérant.
Le FHE (Full Homomorphic Encryption) est vraiment lent, mais il y a eu des progrès remarquables depuis 2009. Rien que la vitesse du bootstrapping s’est améliorée de plusieurs dizaines de millions de fois. Un AES-128 basé sur chiffrement homomorphe a même déjà été démontré avec tfhe-rs. J’ai l’impression que la possibilité d’introduire du FHE en temps réel pour l’inférence et l’entraînement en IA devient de plus en plus crédible. Voir le lien GitHub de tfhe-aes-128.
Je ne peux pas être d’accord avec l’idée que le serveur ne peut plus comprendre les modifications du client. Le serveur peut envoyer uniquement les changements que l’utilisateur n’a pas encore vus, puis l’utilisateur les déchiffre et les fusionne pour reconstituer la version la plus récente du document. Le chiffrement homomorphe est intéressant, mais il est presque inadapté dès qu’on a besoin de performances ou de bande passante raisonnables. J’ai déjà vu un article sur du calcul complètement confidentiel basé sur chiffrement homomorphe (où un CPU+RAM custom est encodé en texte chiffré, puis une instruction est traitée à chaque signal d’horloge). Cela fonctionne réellement, mais au rythme d’une seule instruction de CPU virtuel par seconde. Si une telle vitesse et un tel coût sont acceptables, autant l’exécuter en local, ou, si l’on est vraiment riche, acheter directement le matériel et traiter cela localement.
Les articles de recherche en informatique et en cryptographie sont souvent très éloignés de la praticité, avec par exemple des travaux qui réduisent la complexité d’une attaque de 2^250 à 2^230, ce qui est absurdement irréaliste. Ce type de recherche reste utile pour la R&D réelle ou pour élargir le champ du possible.
Si le serveur ne peut pas manipuler directement le contenu, il ne peut pas fusionner les documents CRDT et doit à chaque fois recevoir puis renvoyer l’état complet du CRDT. Si un ami est connecté en même temps, on peut envoyer les opérations pour permettre une fusion en temps réel ; sinon, c’est extrêmement inefficace.
Je me demande si l’on peut vraiment faire confiance à des étudiants pour exécuter eux-mêmes sur leur Chromebook, via la combinaison JupyterLite et ottergrader, du code de correction WASM ou JS chiffré avec du FHE. Je me demande aussi quel est le lien avec la signature de code et l’économiseur d’écran de SETI@home.
Il vaut mieux éviter THFE-rs, car Zama exige une licence commerciale en dehors d’un usage de prototypage. Les conditions de licence sont contraignantes. À la place, je recommande les bibliothèques openFHE (C++) et lattigo (golang), qui peuvent toutes deux être utilisées librement à des fins commerciales.
Je pense que le FHE est fondamentalement un mauvais outil pour ce cas d’usage. Le FHE convient aux situations où un serveur central traite des données qu’il possède ou connaît. Ici, plusieurs utilisateurs doivent traiter ensemble des données distribuées, donc le MPC (calcul multipartite : méthode où plusieurs participants effectuent ensemble un calcul, par exemple sur la somme de leurs données secrètes respectives) est bien plus efficace.
J’ai du mal à comprendre les hypothèses posées dans l’article. Je connais les concepts de CRDT et de chiffrement homomorphe, mais je ne vois pas pourquoi les deux côtés devraient être en ligne en même temps pour se synchroniser. Avec un modèle asynchrone de type store-and-forward, les mises à jour en transit peuvent aussi rester chiffrées ; je ne comprends donc pas pourquoi le serveur devrait absolument conserver l’état (qui plus est chiffré), ni pourquoi il faudrait le modifier comme proposé.
L’association de la lenteur et de l’inefficacité du FHE avec le gaspillage d’espace de stockage des CRDT me paraît assez amusante.