Intersection d'Ensemble Privé Multipartite au-delà du Seuil pour la Détection Collaborative des Intrusions Réseau

Informations Fondamentales

• ID de l'article : 2510.12045
• Titre : Over-Threshold Multiparty Private Set Intersection for Collaborative Network Intrusion Detection
• Auteurs : Onur Eren Arpaci, Raouf Boutaba, Florian Kerschbaum (Université de Waterloo)
• Classification : cs.CR (Cryptographie et Sécurité), cs.NI (Architecture des Réseaux et Internet)
• Date de publication : 14 octobre 2025 (prépublication arXiv)
• Lien de l'article : https://arxiv.org/abs/2510.12045

Résumé

Une fonction importante de la détection collaborative des intrusions réseau est l'analyse des journaux réseau des collaborateurs pour identifier les adresses IP communes. Cependant, le partage en clair des adresses IP est sensible et peut être soumis à des restrictions légales sur la confidentialité, car il s'agit d'informations d'identification personnelle. Cet article propose une méthode de collecte préservant la confidentialité des adresses IP, en présentant un protocole d'intersection d'ensemble privé au-delà du seuil avec un seul collecteur. Dans ce protocole, N participants identifient les adresses IP qui apparaissent dans les ensembles d'au moins t participants, sans révéler d'informations sur les autres adresses IP. Grâce à un schéma de hachage novateur, la complexité de calcul des solutions précédentes de pointe est réduite de $O(M(N \log{M}/t)^{2t})$ à $O(t^2M\binom{N}{t})$, où M représente la taille de l'ensemble de données. Cette réduction rend l'application du protocole aux journaux réseau réels pratiquement viable.

Contexte et Motivation de la Recherche

Définition du Problème

Le problème fondamental auquel fait face la détection collaborative des intrusions réseau est de savoir comment identifier les attaques multi-organisationnelles tout en préservant la confidentialité. Les recherches montrent que 75 % des attaques organisationnelles se propagent à une deuxième organisation en un jour, et plus de 40 % en une heure. Les attaquants exploitent généralement un petit nombre d'adresses IP externes pour attaquer simultanément plusieurs organisations. Si une adresse IP externe se connecte à au moins t organisations dans une fenêtre de temps spécifique, elle peut être classée comme malveillante avec un taux de rappel de 95 %.

Défis de Confidentialité

Les approches traditionnelles exigent que les organisations partagent les journaux réseau en clair, ce qui présente des risques graves pour la confidentialité :

1. Conformité légale : Les adresses IP sont reconnues par le RGPD, la PIPEDA, la CCPA et autres lois comme des informations d'identification personnelle
2. Sensibilité des données : Les données réseau brutes sont plus sensibles que les alertes de sécurité et contiennent de nombreuses informations sensibles non pertinentes
3. Échelle des données : Les données brutes sont plusieurs ordres de grandeur plus volumineuses que les alertes de sécurité, rendant les solutions existantes informatiquement non viables

Limitations des Approches Existantes

• Kissner et Song 26 : Nécessite O(N) tours de communication, complexité de calcul O(N³M³)
• Mahdavi et al. 34 : Bien qu'améliorant la complexité de communication, le coût de calcul reste trop élevé, avec une complexité de O(M(N logM/t)²ᵗ)

Contributions Principales

1. Schéma de hachage novateur : Propose un algorithme de hachage innovant réduisant la complexité de calcul de O(M(N logM/t)²ᵗ) à O(t²M(N choose t)), réalisant une complexité linéaire en M
2. Amélioration de la praticité : Permet au protocole de traiter les journaux réseau à l'échelle réelle, complétant la détection en 170 secondes avec 33 organisations participantes et jusqu'à 144 045 adresses IP
3. Options de déploiement double :
   • Déploiement résistant à la collusion : Offre des garanties de sécurité plus fortes, mais avec des frais de communication plus élevés
   • Déploiement non interactif : Suppose un collecteur non collusif, réduisant considérablement les coûts de communication
4. Preuve de sécurité : Démontre la sécurité du protocole dans le modèle de calcul multipartite semi-honnête
5. Validation pratique : Évaluation utilisant les journaux réseau réels du projet IDS CANARIE

Détails de la Méthode

Définition de la Tâche

Intersection d'Ensemble Privé Multipartite au-delà du Seuil (OT-MP-PSI) :

• Entrée : N participants, chacun détenant un ensemble Si d'au maximum M éléments
• Sortie : Identification des éléments apparaissant dans au moins t ensembles, sans révéler d'informations sur les éléments sous le seuil
• Contrainte : Modèle de sécurité semi-honnête, les participants suivent le protocole mais peuvent tenter d'apprendre des informations supplémentaires

Composants Techniques Principaux

1. Partage Secret de Shamir

Utilise un schéma de seuil (t,n), où n'importe quels t participants peuvent reconstruire le secret V, et moins de t participants ne peuvent obtenir aucune information :

P(x) = c_{t-1}x^{t-1} + c_{t-2}x^{t-2} + ... + c_1x + V

2. Fonction Pseudo-Aléatoire Oubliée (OPRF)

Les participants apprennent H_K(x) sans connaître la clé K, et le détenteur de la clé ne connaît ni l'entrée x ni la valeur de sortie.

3. Partage Secret Pseudo-Aléatoire Oublié (OPR-SS)

Combine les propriétés de sécurité du partage secret et de l'OPRF, permettant aux participants d'obtenir des parts secrètes uniques du détenteur de la clé.

Architecture du Protocole

Déploiement Non Interactif

1. Création de parts : Chaque participant crée des parts secrètes pour chaque élément de son ensemble
2. Mappage de hachage : Utilise le nouveau schéma de hachage pour mapper les parts à des seaux de taille 1
3. Reconstruction : L'agrégateur tente toutes les combinaisons de t participants pour l'interpolation de Lagrange
4. Notification des résultats : L'agrégateur notifie les participants des indices de reconstruction réussis

Déploiement Résistant à la Collusion

Utilise le protocole OPR-SS à la place de la clé partagée, en calculant la fonction de hachage via un protocole OPRF multi-clés, offrant des garanties plus fortes contre la collusion.

Points d'Innovation Technique

Nouveau Schéma de Hachage

Idée centrale : Utilise des seaux de taille 1 pour éviter les collisions de hachage plutôt que de les accommoder :

1. Gestion des collisions : Lorsque plusieurs éléments sont mappés au même seau, utilise un tri pseudo-aléatoire pour sélectionner le plus petit
2. Stratégie multi-tables : Chaque participant crée plusieurs tables, garantissant que les valeurs manquées apparaissent dans d'autres tables
3. Contrôle de la probabilité d'échec : Contrôle la probabilité d'échec à 2⁻⁴⁰ ou moins en utilisant 20 tables

Avantages clés :

• L'agrégateur doit uniquement essayer les combinaisons de participants, et non les combinaisons de parts
• La complexité passe d'exponentielle à linéaire (par rapport à M)
• Évite les grands facteurs constants des méthodes traditionnelles de partitionnement

Techniques d'Optimisation

1. Inversion de tri : Les deux tables consécutives utilisent la même fonction de tri, les tables paires inversent le tri
2. Utilisation des seaux vides : Une deuxième insertion utilise les seaux vides après la première insertion

Configuration Expérimentale

Ensemble de Données

• Données réelles : Journaux de connexion réseau de 54 organisations du projet IDS CANARIE
• Plage temporelle : 1-8 novembre 2023, environ 8 milliards d'entrées de journal par jour
• Échelle des données : Environ 700 Go par jour (compression gzip)
• Traitement : Traitement par lots horaires, extraction des connexions d'IP externes à IP internes

Indicateurs d'Évaluation

• Temps de reconstruction : Temps nécessaire à l'agrégateur pour compléter la reconstruction
• Temps de génération de parts : Temps pour un participant unique de créer des parts
• Complexité de communication : Frais de communication totaux du protocole
• Exactitude : Vérification de la probabilité d'échec

Méthodes de Comparaison

• Mahdavi et al. 34 : Solution OT-MP-PSI actuelle de pointe
• Limite théorique : Comparaison avec la limite de probabilité d'échec calculée

Détails d'Implémentation

• Langage de programmation : Julia, 430 lignes de code
• Bibliothèque cryptographique : SHA.jl, Nettle.jl
• Champ fini : Nombre premier de Mersenne 61 bits
• Environnement matériel : 8 × Processeur Intel Xeon E7-8870, 80 cœurs physiques, 1 To de mémoire

Résultats Expérimentaux

Résultats Principaux

Comparaison de Performance

Par rapport à Mahdavi et al. 34 :

• Amélioration de vitesse : Au moins deux ordres de grandeur, jusqu'à 23 066 fois plus rapide
• Scalabilité : Avec M=10⁵, cette méthode nécessite des centaines de secondes, tandis que la méthode de comparaison nécessite des jours

Performance sur Données Réelles

Performance sur les données CANARIE :

• Temps de reconstruction moyen : 170 secondes
• Temps de reconstruction maximal : 438 secondes (40 organisations, 220 011 adresses IP)
• Nombre moyen d'organisations participantes : 33
• Taille moyenne maximale d'ensemble : 144 045 adresses IP

Analyse de Complexité

Complexité de Calcul

• Agrégateur : O(t²M(N choose t))
• Participants (non interactif) : O(tM)
• Cas particulier : O(M) quand N=t=2, O(N²M) quand N=t

Complexité de Communication

• Déploiement non interactif : O(tMN)
• Déploiement résistant à la collusion : O(tkMN), 5 tours de communication

Vérification d'Exactitude

• Probabilité d'échec théorique : 2⁻⁴⁰
• Vérification expérimentale : Sur 10⁷ essais, le nombre réel d'échecs est bien inférieur à la limite théorique
• Optimisation du nombre de tables : Optimisé de 28 tables théoriques à 20 tables pratiques

Travaux Connexes

Solutions OT-MP-PSI

1. Kissner et Song 26 : Première solution, utilisant la représentation polynomiale en anneau, complexité O(N³M³)
2. Mahdavi et al. 34 : Nombre constant de tours, complexité O(M(N logM/t)²ᵗ)
3. Ma et al. 33 : Adapté aux petits ensembles d'entrée et petits domaines, complexité O(N|S|)

Problèmes Connexes

• Intersection d'Ensemble Privé avec Seuil (TPSI) : Apprentissage de l'intersection si et seulement si la taille de l'intersection dépasse le seuil
• Quorum-PSI : Cas particulier d'OT-MP-PSI, seuls certains participants ont une sortie

Techniques de Hachage

• Hachage par coucou : Utilisé pour éviter les collisions de hachage, largement appliqué aux protocoles PSI
• Hachage par coucou 2D : Conçu pour PSI bipartite, réalisant une complexité O(M)

Conclusion et Discussion

Conclusions Principales

1. Percée de praticité : Rend pour la première fois l'OT-MP-PSI pratiquement viable à l'échelle des journaux réseau réels
2. Amélioration d'efficacité : Réalise des améliorations de performance d'ordres de grandeur grâce au nouveau schéma de hachage
3. Déploiement flexible : Offre deux options de déploiement adaptées à différents besoins de sécurité
4. Validation pratique : Valide la praticité du protocole dans un environnement réseau multi-organisationnel réel

Limitations

1. Modèle semi-honnête : Bien qu'extensible au modèle malveillant, reste vulnérable aux attaques par substitution d'entrée
2. Fuite de taille d'ensemble : Le protocole principal ne traite pas la taille de l'ensemble des participants comme privée
3. Confiance de l'agrégateur : Le déploiement non interactif nécessite de faire confiance à l'agrégateur pour ne pas colluder avec les participants
4. Limitation de seuil : Lorsque t est proche de N/2 et N est grand, l'avantage de complexité peut ne pas être apparent

Directions Futures

1. Sécurité malveillante : Étendre le protocole pour résister aux attaquants actifs
2. Seuil dynamique : Supporter le calcul de seuils multiples sans coût client supplémentaire
3. Optimisation à grande échelle : Optimiser davantage le traitement des combinaisons de participants
4. Amélioration de la confidentialité : Explorer les techniques de confidentialité différentielle pour protéger les informations de taille d'ensemble

Évaluation Approfondie

Points Forts

1. Contribution théorique significative : Le nouveau schéma de hachage représente une percée importante dans la technologie existante, réduisant la complexité exponentielle à linéaire
2. Valeur pratique élevée : Résout un problème clé de confidentialité dans la détection collaborative des intrusions du monde réel
3. Expérimentation suffisante : Combine l'analyse théorique et la validation sur données réelles, avec une configuration expérimentale raisonnable
4. Implémentation d'ingénierie complète : Fournit une implémentation open-source, améliorant la reproductibilité
5. Sécurité rigoureuse : Fournit des preuves de sécurité formelles et deux options de déploiement

Insuffisances

1. Limitation du modèle de sécurité : Le modèle semi-honnête peut ne pas être suffisamment fort dans certains scénarios pratiques
2. Sélection de paramètres : Le choix de 20 tables est basé sur l'optimisation empirique, manquant de guidance théorique suffisante
3. Limites de scalabilité : L'applicabilité à des échelles extrêmement grandes (par exemple, au niveau d'Internet mondial) n'a pas été suffisamment explorée
4. Comparaison de base limitée : Comparaison principalement avec une seule méthode de référence, manquant d'une comparaison de performance plus complète

Impact

1. Valeur académique : Fournit une nouvelle voie technique pour le domaine du calcul multipartite sécurisé
2. Signification pratique : Résout directement les besoins réels du domaine de la sécurité réseau
3. Promotion technologique : Le schéma de hachage peut être applicable à d'autres problèmes de calcul multipartite
4. Potentiel de normalisation : Peut devenir un protocole standard pour la détection collaborative des intrusions

Scénarios d'Application

1. Sécurité réseau multi-organisationnelle : Protection collaborative d'organisations similaires telles que les universités et les hôpitaux
2. Services de sécurité cloud : Analyse de journaux préservant la confidentialité pour les centres d'opérations de sécurité
3. Partage de renseignements sur les menaces : Échange d'indicateurs de menace sous contraintes de confidentialité
4. Exigences de conformité : Collaboration de données conforme au RGPD et autres réglementations de confidentialité

Références

Cet article cite 53 références connexes, couvrant des travaux importants dans plusieurs domaines incluant la cryptographie, la sécurité réseau et le calcul multipartite, fournissant une base théorique solide et un contexte technique complet.

Évaluation Globale : Il s'agit d'un article de haute qualité en cryptographie appliquée qui a réalisé un bon équilibre entre l'innovation théorique et l'application pratique. Le nouveau schéma de hachage proposé représente non seulement une percée théorique importante, mais démontre également une valeur significative dans les applications pratiques. La vérification expérimentale est suffisante, l'analyse de sécurité est rigoureuse, et l'article fournit une contribution technique importante au domaine de la sécurité réseau collaborative.