ORQ: Complex Analytics on Private Data with Strong Security Guarantees

ORQ est un système novateur qui permet une analyse collaborative efficace et cryptographiquement sécurisée de grands ensembles de données privées en éliminant le coût quadratique des jointures sécurisées grâce à l'agrégation à la volée, atteignant ainsi une performance de type TPC-H Scale Factor 10 sous calcul multi-parties sans dépendre de tiers de confiance ou de fuite d'informations.

L'essentiel

Imaginez que vous êtes le capitaine d'un navire, et que vous avez trois autres capitaines avec vous. Chacun de vous détient une carte secrète avec des emplacements de trésors précieux, mais aucun de vous ne fait assez confiance aux autres pour montrer ses cartes. Vous voulez travailler ensemble pour trouver la meilleure route qui combine toutes vos cartes, mais vous ne voulez pas révéler où se trouvent vos trésors spécifiques, ni même combien de trésors vous possédez.

C'est le problème qu'Orq résout.

Le Problème : L'« Explosion Quadratique »

Dans le monde de l'informatique sécurisée, il existe une technique appelée Calcul Multi-Parties (MPC - Multiparty Computation). Elle permet à des personnes de calculer des choses ensemble sans révéler leurs données privées. Imaginez un groupe de personnes résolvant un problème mathématique où chacun écrit ses nombres sur une feuille de papier, mais ils ne font s'échanger que des versions « brouillées » de ces nombres.

Cependant, il y a un goulot d'étranglement majeur : les Jointures (Joins).
Imaginez que vous avez deux listes de noms. Vous voulez trouver tous ceux qui apparaissent sur les deux listes.

• L'ancienne méthode : Si vous essayez de faire cela de manière sécurisée sans rien révéler, les ordinateurs doivent vérifier chaque nom de la Liste A par rapport à chaque nom de la Liste B. Si la Liste A contient 1 000 noms et la Liste B contient 1 000 noms, l'ordinateur doit effectuer 1 000 000 de vérifications (1 000 x 1 000).
• Le cauchemar en « cascade » : Si vous avez trois listes à joindre, les vérifications explosent à 1 000 000 000. Si vous en avez quatre, c'est un billion. C'est ce qu'on appelle l'« explosion quadratique ». C'est comme essayer de trouver une aiguille dans une botte de foin, mais chaque fois que vous regardez, la botte de foin double de taille. Les systèmes précédents soit abandonnaient pour éviter cette explosion, soit laissaient fuiter des secrets pour l'éviter, soit nécessitaient un tiers de confiance (comme un juge) pour surveiller le processus.

La Solution : Orq (Le « Trieur Intelligent »)

Les chercheurs ont conçu un système appelé Orq qui change les règles du jeu. Au lieu de vérifier aveuglément chaque combinaison, Orq utilise une astuce ingénieuse : il trie d'abord les listes.

Pensez-y comme à l'organisation d'une bibliothèque désordonnée.

1. L'ancienne méthode : Vous approchez chaque livre de la bibliothèque et demandez : « Est-ce que ce livre parle de chats ? » Vous faites cela pour chaque livre, même s'ils sont tous dans la mauvaise section.
2. La méthode Orq : Vous organisez d'abord les livres par ordre alphabétique. Maintenant, si vous voulez trouver tous les livres sur les « Chats », vous n'avez qu'à aller dans la section « C ». Vous n'avez pas besoin de vérifier les sections « A » ou « Z ».

Orq fait cela avec les données. Il trie les données secrètes de sorte que les éléments correspondants se retrouvent juste à côté les uns des autres. Cela transforme la tâche impossible de « tout vérifier » en une tâche gérable de « vérifier les voisins ».

La Recette Secrète : L'Agrégation « À la Volée »

L'article met en évidence une intuition spécifique : dans la plupart des questions du monde réel (comme « Combien d'argent avons-nous gagné ? »), nous n'avons pas réellement besoin de voir la liste finale de chaque transaction individuelle. Nous avons seulement besoin du total.

Orq utilise une technique appelée Jointure-Agrégation (Join-Aggregation).

• Imaginez une course de relais : Au lieu de courir toute la course, de s'arrêter pour compter chaque pas, puis de courir à nouveau, Orq combine la course et le comptage en un seul mouvement fluide.
• À mesure que les données circulent dans le système, Orq joint les tables et additionne les chiffres (agrège) exactement au même moment. Il ne crée jamais la liste intermédiaire massive de toutes les combinaisons possibles. Il maintient la taille des données limitée, comme un seau qui ne déborde jamais, peu importe la quantité d'eau que vous y versez.

Les Résultats : Vitesse et Échelle

Les chercheurs ont testé Orq dans deux environnements :

1. LAN (Réseau Local) : Des ordinateurs dans le même bâtiment.
2. WAN (Réseau Étendu) : Des ordinateurs à travers Internet (comme dans différents pays).

Ce qu'ils ont découvert :

• Vitesse : Orq est considérablement plus rapide que les systèmes précédents. Dans certains cas, il est 800 fois plus rapide.
• Échelle : Ils ont pu exécuter le célèbre benchmark TPC-H (un test standard de performance de base de données) avec un « Facteur d'Échelle 10 ». Cela signifie qu'ils ont traité 58 millions de lignes de données entièrement sous chiffrement sécurisé.
  • Contexte : Les systèmes sécurisés précédents ne pouvaient gérer autant de données qu'en laissant fuiter des secrets ou en utilisant un tiers de confiance. Orq l'a fait avec zéro fuite et sans tiers de confiance.
• Sécurité : Cela fonctionne même si certains des ordinateurs sont « malveillants » (tentant de tricher) ou « semi-honnêtes » (suivant les règles mais essayant d'espionner).

Ce qu'il faut retenir

Orq est comme un nouveau moteur ultra-efficace pour une voiture sécurisée. Avant, essayer de conduire une voiture sécurisée avec une charge lourde (des données complexes) était si lent et dangereux que les gens soit ne conduisaient plus, soit retiraient les verrous de sécurité (laissant fuiter les données). Orq a redessiné le moteur pour que vous puissiez conduire vite, transporter une charge massive et garder les verrous de sécurité fermement en place.

Ils ont même rendu le code open-source, afin que n'importe qui puisse utiliser ce « moteur » pour construire ses propres outils d'analyse de données sécurisées.

Résumé technique

Résumé Technique : Orq – Analyses complexes sur des données privées avec de fortes garanties de sécurité

1. Énoncé du problème

Le document traite du défi consistant à effectuer des analyses relationnelles complexes (spécifiquement des jointures multi-voies et des agrégations) sur de grands ensembles de données privées dans un environnement de calcul multipartite sécurisé (MPC) externalisé. Dans ce cadre, les propriétaires de données distribuent des parts secrètes de leurs données à un ensemble de serveurs de calcul non fiables et non collusoires.

Le goulot d'étranglement principal des systèmes MPC antérieurs est l'effet de cascade des jointures obligatoires (oblivious joins). Pour maintenir l'obliviosité (masquer les modèles d'accès et la distribution des données), les jointures obligatoires standards sur des tables de $n$ enregistrements doivent produire une taille de sortie de pire cas égale à $n^2$ (le produit cartésien). Pour les requêtes impliquant plusieurs jointures ($k$ jointures), cela conduit à une complexité temporelle et spatiale de $O(n^{k+1})$, rendant les requêtes complexes intraitables pour de grands ensembles de données.

Les solutions existantes sont confrontées à un trilemme :

1. Coût quadratique : Calculer le produit cartésien complet (coûteux).
2. Suppression silencieuse : Imposer une limite sous-quadratique en supprimant silencieusement des enregistrements (incorrect).
3. Fuite d'information : Fuiter la taille du résultat de la jointure aux serveurs (peu sûr).

Les travaux antérieurs dans les contextes externalisés (par exemple, Secrecy, Scape) souffrent soit de coûts quadratiques, soit de fuites sur la taille des résultats. De plus, de nombreux systèmes existants reposent sur des bases de calcul de confiance (TCB) ou des modèles de propriété de données spécifiques (par exemple, le pair-à-pair où les propriétaires sont aussi les parties de calcul) qui ne se généralisent pas au modèle externalisé où les serveurs ne voient jamais le texte clair.

2. Méthodologie

Orq introduit un runtime de système holistique conçu pour évaluer des requêtes complexes avec une complexité de $O(n \log n)$, évitant l'explosion quadratique sans fuiter d'informations.

2.1 Insight central : Limites indépendantes des données

Les auteurs observent que dans de nombreux scénarios pratiques d'analyse collaborative, la taille du résultat de la requête est bornée par la taille de l'entrée ($O(n)$), indépendamment de la distribution des données. Cela reste vrai même pour les jointures many-to-many, à condition que la structure de la requête permette une agrégation décomposable. Orq exploite cette observation pour borner les tailles de résultats intermédiaires.

2.2 L'opérateur de Jointure-Agrégation Composé

L'innovation centrale est un opérateur de fusion Jointure-Agrégation qui évite de matérialiser le produit cartésien.

• Mécanisme : Au lieu de joindre d'abord puis d'agréger, Orq effectue une évaluation de type "MapReduce". Il applique une pré-agrégation (évaluation partielle) sur les tables d'entrée pour gérer les doublons, effectue la jointure, puis applique une post-agrégation.
• Implémentation : L'opérateur concatène les tables d'entrée, les trie de manière obligatoire sur les clés de jointure, et utilise un réseau d'agrégation (AggNet) de type papillon pour propager les valeurs et calculer les agrégats dans un flux de contrôle unique.
• Support : Il supporte les jointures inner, outer, semi et anti, ainsi que des agrégations arbitraires définies par l'utilisateur (somme, compte, min, max, moyenne).
• Gestion des doublons : Pour les jointures many-to-many, Orq pré-agrège une entrée pour créer des clés uniques (multiplicité), effectue la jointure, puis post-agrège pour combiner les multiplicités. Cela garantit que la taille de la table intermédiaire ne dépasse jamais la cardinalité de la plus grande entrée.

2.3 Primitives Obligatoires et Tri

Pour supporter l'opérateur de jointure-agrégation, Orq implémente des primitives obligatoires de pointe :

• Tri : Orq fournit des implémentations vectorisées et parallèles aux données de Quicksort et Radixsort.
  • Quicksort : Utilise un paradigme itératif de "shuffle-then-sort" pour réduire les cycles de communication à $O(\log n)$.
  • Radixsort : Utilise une approche hybride combinant une permutation de bits impatiente (eager) avec un mélange obligatoire (oblivious shuffling).
  • TableSort : Un wrapper qui extrait la permutation de tri d'un tri paddé et l'applique à toutes les colonnes d'une table, évitant le tri redondant de multiples colonnes.
• Mélange (Shuffling) : Primitives de mélange obligatoire généralisées compatibles avec divers protocoles MPC.
• Vectorisation : Tous les opérateurs sont implémentés en utilisant un format de données colonnaires, permettant aux messages indépendants au sein d'une étape d'être groupés et envoyés dans un seul cycle de communication.

2.4 Architecture du Système

• API de Flux de Données (Dataflow) : Les utilisateurs définissent les requêtes via une API de type flux de données (similaire à Apache Spark) plutôt que le SQL, permettant l'expression concise de pipelines complexes.
• Indépendance de Protocole : Les opérateurs sont construits comme des abstractions boîtes noires sur les primitives MPC ($+, \times, \oplus, \land$). Orq supporte trois protocoles :
  1. Semi-honnête, majorité malhonnête (ABY, 2-parties).
  2. Semi-honnête, majorité honnête (Araki et al., 3-parties).
  3. Sécurité malveillante, majorité honnête (Fantastic Four, 4-parties).
• Couche de Communication : Une couche personnalisée basée sur TCP avec des tampons circulaires sans verrou (lock-free ring buffers) pour amortir les coûts réseau, particulièrement dans les environnements WAN.

3. Contributions Clés

1. Système Orq : Un système complet pour les analyses relationnelles complexes dans un contexte de MPC externalisé, supportant les jointures multi-voies et les agrégations avec de fortes garanties de sécurité (pas de fuite sur la taille des résultats).
2. Nouvel Opérateur de Jointure-Agrégation : Une technique qui décompose et applique de manière impatiente les agrégations pour borner les tailles de résultats intermédiaires, atteignant une complexité de $O(n \log n)$ pour des jointures qui nécessitaient auparavant $O(n^2)$.
3. Primitives Indépendantes de Protocole : Une implémentation unifiée d'opérateurs obligatoires (jointures, tris, agrégations) pouvant être instanciée avec des protocoles MPC semi-honnêtes ou malveillants.
4. Tri Scalable : Des implémentations vectorisées et parallèles aux données de tris obligatoires capables de gérer jusqu'à 537 millions de lignes, surpassant nettement l'état de l'art.
5. Évaluation Complète : La première exécution MPC de bout en bout du benchmark complet TPC-H (Scale Factor 10) sans fuite ni recours à un calcul de confiance.

4. Résultats Expérimentaux

Les auteurs ont évalué Orq sur des déploiements LAN et WAN à travers diverses charges de travail, incluant le benchmark complet TPC-H et des requêtes issues de travaux antérieurs.

• Performance vs État de l'Art :
  • Vs Secrecy : Orq atteint une latence jusqu'à 827$\times$ plus faible. Secrecy utilise des jointures en $O(n^2)$ et une exécution mono-thread ; Orq utilise $O(n \log n)$ et la vectorisation.
  • Vs SecretFlow : Orq est 1,1$\times$ à 1,5$\times$ plus rapide sur les requêtes de jointure et 58$\times$ à 85$\times$ plus rapide sur les requêtes sans jointure, malgré le fait que SecretFlow fuite la taille des résultats de jointure. Orq atteint cela sans aucune fuite.
  • Vs MP-SPDZ : Le tri d'Orq est jusqu'à 189$\times$ plus rapide grâce au parallélisme des données.
• Scalabilité :
  • Orq traite les requêtes TPC-H de Scale Factor 10 (moyenne de 58M de lignes) entièrement sous MPC.
  • La requête la plus coûteuse (Q21) se termine en 42 minutes (LAN, sécurité malveillante) et 18 heures (WAN, sécurité malveillante).
  • Les protocoles de tri passent à l'échelle jusqu'à 537 millions de lignes (Quicksort, SH-HM) et 134 millions de lignes (Radixsort, Mal-HM).
• Bande Passante : Orq présente une consommation de bande passante jusqu'à deux ordres de grandeur inférieure à celle de Secrecy grâce aux améliorations asymptotiques.
• Prétraitement : L'article évalue la génération de triplets de Beaver, montrant que les protocoles sous-quadratiques (Doerner et al.) offrent des économies de bande passante significatives par rapport aux méthodes traditionnelles, malgré un surcoût de calcul.

5. Signification et Revendications

L'article affirme qu'Orq représente une étape majeure pour rendre l'analyse sécurisée pratique pour l'analyse de données collaborative à grande échelle.

• Briser la Barrière Quadratique : Orq démontre qu'une évaluation complète et obligatoire de jointures complexes multi-voies est possible sans fuiter la taille des résultats ni dépendre de matériel de confiance.
• Praticité à l'Échelle : En exécutant avec succès le benchmark complet TPC-H à Scale Factor 10 (précédemment réalisable uniquement avec fuite ou calcul de confiance), Orq prouve que le MPC peut gérer des charges de travail de niveau entreprise.
• Généralité : Le système n'est pas restreint à des modèles de propriété de données ou des modèles de menace spécifiques, supportant à la fois les adversaires semi-honnêtes et malveillants dans des contextes externalisés.
• Open Source : Les auteurs ont publié Orq en open-source pour faciliter la recherche et l'adoption futures.

Les auteurs notent que bien qu'ils nécessitent actuellement une API de flux de données (plutôt qu'un planificateur SQL automatique), les performances et les propriétés de sécurité du système établissent une nouvelle référence pour l'analyse relationnelle sécurisée. Les travaux futurs incluent l'intégration d'un planificateur de requêtes automatique et l'optimisation supplémentaire des vérifications malveillantes pour les environnements WAN.