Intersezione di Insiemi Privati Multipartiti Oltre-Soglia per il Rilevamento Collaborativo di Intrusioni di Rete

Informazioni Fondamentali

• ID Articolo: 2510.12045
• Titolo: Over-Threshold Multiparty Private Set Intersection for Collaborative Network Intrusion Detection
• Autori: Onur Eren Arpaci, Raouf Boutaba, Florian Kerschbaum (University of Waterloo)
• Classificazione: cs.CR (Crittografia e Sicurezza), cs.NI (Architetture di Rete e Internet)
• Data di Pubblicazione: 14 ottobre 2025 (preprint arXiv)
• Link dell'Articolo: https://arxiv.org/abs/2510.12045

Riassunto

Una funzione critica nel rilevamento collaborativo di intrusioni di rete è l'analisi dei registri di rete dei collaboratori per identificare indirizzi IP comuni. Tuttavia, la condivisione in chiaro degli indirizzi IP è sensibile e potrebbe essere soggetta a vincoli legali sulla privacy, poiché costituisce informazione personale identificabile. Questo articolo propone un metodo di raccolta che preserva la privacy degli indirizzi IP, presentando un protocollo di intersezione di insiemi privati oltre-soglia con un singolo aggregatore. Nel protocollo, N partecipanti identificano gli indirizzi IP che compaiono negli insiemi di almeno t partecipanti, senza rivelare alcuna informazione riguardante altri indirizzi IP. Attraverso uno schema di hashing innovativo, la complessità computazionale della soluzione precedentemente all'avanguardia viene ridotta da $O(M(N \log{M}/t)^{2t})$ a $O(t^2M\binom{N}{t})$, dove M rappresenta la dimensione del dataset. Questa riduzione rende praticabile l'applicazione del protocollo ai registri di rete reali.

Contesto di Ricerca e Motivazione

Definizione del Problema

Il problema fondamentale affrontato dal rilevamento collaborativo di intrusioni di rete è come identificare attacchi multi-istituzionali preservando la privacy. La ricerca dimostra che il 75% degli attacchi istituzionali si diffonde a una seconda istituzione entro un giorno, e oltre il 40% entro un'ora. Gli attaccanti solitamente utilizzano un piccolo numero di indirizzi IP esterni per attaccare simultaneamente più istituzioni; se un indirizzo IP esterno si connette ad almeno t istituzioni entro una finestra temporale specifica, può essere classificato come malevolo con un tasso di richiamo del 95%.

Sfide di Privacy

I metodi tradizionali richiedono che le istituzioni condividano i registri di rete in chiaro, presentando rischi di privacy significativi:

1. Conformità Legale: Gli indirizzi IP sono riconosciuti come informazione personale identificabile da GDPR, PIPEDA, CCPA e altre leggi
2. Sensibilità dei Dati: I dati di rete grezzi sono più sensibili degli avvisi di sicurezza, contenendo numerose informazioni sensibili non pertinenti
3. Scala dei Dati: I dati grezzi sono diversi ordini di grandezza più grandi degli avvisi di sicurezza, rendendo le soluzioni esistenti computazionalmente non praticabili

Limitazioni dei Metodi Esistenti

• Kissner e Song 26: Richiedono O(N) turni di comunicazione, complessità computazionale O(N³M³)
• Mahdavi et al. 34: Sebbene migliorino la complessità di comunicazione, il costo computazionale rimane eccessivo, con complessità O(M(N logM/t)²ᵗ)

Contributi Fondamentali

1. Schema di Hashing Innovativo: Propone un algoritmo di hashing innovativo che riduce la complessità computazionale da O(M(N logM/t)²ᵗ) a O(t²M(N choose t)), realizzando una complessità lineare rispetto a M
2. Miglioramento della Praticabilità: Consente al protocollo di elaborare registri di rete su scala reale, completando il rilevamento in 170 secondi con 33 istituzioni partecipanti e fino a 144.045 indirizzi IP
3. Opzioni di Distribuzione Duale:
   • Distribuzione resistente alla collusione: Fornisce garanzie di sicurezza più forti, ma con overhead di comunicazione più elevato
   • Distribuzione non interattiva: Presuppone un aggregatore non collusivo, riducendo significativamente i costi di comunicazione
4. Prova di Sicurezza: Dimostra la sicurezza del protocollo nel modello di calcolo multipartito semi-onesto
5. Verifica Pratica: Valutazione utilizzando registri di rete reali dal progetto CANARIE IDS

Spiegazione Dettagliata del Metodo

Definizione del Compito

Intersezione di Insiemi Privati Multipartiti Oltre-Soglia (OT-MP-PSI):

• Input: N partecipanti, ciascuno che possiede un insieme Si di al massimo M elementi
• Output: Identifica elementi che compaiono in almeno t insiemi, senza rivelare informazioni su elementi al di sotto della soglia
• Vincoli: Modello di sicurezza semi-onesto, i partecipanti seguono il protocollo ma potrebbero tentare di apprendere informazioni aggiuntive

Componenti Tecnici Fondamentali

1. Condivisione Segreta di Shamir

Utilizza uno schema di soglia (t,n) dove qualsiasi t parti possono ricostruire il segreto V, mentre meno di t parti non possono ottenere alcuna informazione:

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

2. Funzione Pseudocasuale Oblivia (OPRF)

I partecipanti apprendono H_K(x) senza conoscere la chiave K; il detentore della chiave non conosce l'input x o i valori di output.

3. Condivisione Segreta Pseudocasuale Oblivia (OPR-SS)

Combina le proprietà di sicurezza della condivisione segreta e OPRF, consentendo ai partecipanti di ottenere quote segrete univoche dal detentore della chiave.

Architettura del Protocollo

Distribuzione Non Interattiva

1. Creazione di Quote: Ogni partecipante crea quote segrete per ogni elemento nel suo insieme
2. Mappatura di Hashing: Utilizza il nuovo schema di hashing per mappare le quote a bucket di dimensione 1
3. Ricostruzione: L'aggregatore tenta tutte le combinazioni di t partecipanti per l'interpolazione di Lagrange
4. Notifica dei Risultati: L'aggregatore notifica ai partecipanti gli indici ricostruiti con successo

Distribuzione Resistente alla Collusione

Sostituisce la chiave condivisa con il protocollo OPR-SS, calcolando la funzione di hashing tramite il protocollo OPRF multi-chiave, fornendo garanzie più forti contro la collusione.

Punti di Innovazione Tecnica

Nuovo Schema di Hashing

Idea Fondamentale: Utilizza bucket di dimensione 1 per evitare collisioni di hashing, piuttosto che per contenere collisioni:

1. Gestione delle Collisioni: Quando più elementi si mappano allo stesso bucket, utilizza l'ordinamento pseudocasuale per selezionare il più piccolo
2. Strategia Multi-Tabella: Ogni partecipante crea più tabelle, garantendo che i valori mancanti compaiano in altre tabelle
3. Controllo della Probabilità di Fallimento: Controlla la probabilità di fallimento al di sotto di 2⁻⁴⁰ utilizzando 20 tabelle

Vantaggi Chiave:

• L'aggregatore deve tentare solo combinazioni di partecipanti, non combinazioni di quote
• La complessità passa da esponenziale a lineare (rispetto a M)
• Evita i grandi fattori costanti dei metodi di binning tradizionali

Tecniche di Ottimizzazione

1. Inversione di Ordinamento: Le tabelle consecutive pari utilizzano la stessa funzione di ordinamento, le tabelle pari invertono l'ordinamento
2. Utilizzo di Bucket Vuoti: Il secondo inserimento sfrutta i bucket vuoti dopo il primo inserimento

Configurazione Sperimentale

Dataset

• Dati Reali: Registri di connessione di rete di 54 istituzioni dal progetto CANARIE IDS
• Intervallo Temporale: 1-8 novembre 2023, circa 8 miliardi di voci di registro al giorno
• Scala dei Dati: Circa 700GB al giorno (compresso con gzip)
• Metodo di Elaborazione: Elaborazione in batch orari, estrazione di connessioni da IP esterni a IP interni

Metriche di Valutazione

• Tempo di Ricostruzione: Tempo impiegato dall'aggregatore per completare la ricostruzione
• Tempo di Generazione di Quote: Tempo per un singolo partecipante di creare quote
• Complessità di Comunicazione: Overhead di comunicazione totale del protocollo
• Correttezza: Verifica della probabilità di fallimento

Metodi di Confronto

• Mahdavi et al. 34: Soluzione OT-MP-PSI attualmente all'avanguardia
• Limite Teorico: Confronto con il limite di probabilità di fallimento calcolato

Dettagli di Implementazione

• Linguaggio di Programmazione: Julia, 430 righe di codice
• Libreria Crittografica: SHA.jl, Nettle.jl
• Campo Finito: Primo di Mersenne a 61 bit
• Ambiente Hardware: 8×processori Intel Xeon E7-8870, 80 core fisici, 1TB di memoria

Risultati Sperimentali

Risultati Principali

Confronto delle Prestazioni

Rispetto a Mahdavi et al. 34:

• Miglioramento di Velocità: Almeno due ordini di grandezza, fino a 23.066 volte
• Scalabilità: Con M=10⁵, questo metodo richiede centinaia di secondi, mentre il metodo di confronto richiede giorni

Prestazioni su Dati Reali

Prestazioni sui dati CANARIE:

• Tempo Medio di Ricostruzione: 170 secondi
• Tempo Massimo di Ricostruzione: 438 secondi (40 istituzioni, 220.011 indirizzi IP)
• Istituzioni Partecipanti Medie: 33
• Dimensione Media Massima dell'Insieme: 144.045 indirizzi IP

Analisi della Complessità

Complessità Computazionale

• Aggregatore: O(t²M(N choose t))
• Partecipanti (Non Interattivo): O(tM)
• Caso Speciale: N=t=2 è O(M), N=t è O(N²M)

Complessità di Comunicazione

• Distribuzione Non Interattiva: O(tMN)
• Distribuzione Resistente alla Collusione: O(tkMN), 5 turni di comunicazione

Verifica della Correttezza

• Probabilità Teorica di Fallimento: 2⁻⁴⁰
• Verifica Sperimentale: Su 10⁷ prove, il numero effettivo di fallimenti è ben al di sotto del limite teorico
• Ottimizzazione del Numero di Tabelle: Ottimizzato dalle 28 tabelle teoriche alle 20 tabelle pratiche

Lavori Correlati

Soluzioni OT-MP-PSI

1. Kissner e Song 26: Prima soluzione, utilizza rappresentazione polinomiale, complessità O(N³M³)
2. Mahdavi et al. 34: Numero costante di turni, complessità O(M(N logM/t)²ᵗ)
3. Ma et al. 33: Applicabile a piccoli insiemi di input e piccoli domini, complessità O(N|S|)

Problemi Correlati

• Intersezione di Insiemi Privati con Soglia (TPSI): Apprendimento dell'intersezione se e solo se la dimensione dell'intersezione supera la soglia
• Quorum-PSI: Caso speciale di OT-MP-PSI, solo specifici partecipanti hanno output

Tecniche di Hashing

• Hashing a Cuckoo: Utilizzato per evitare collisioni di hashing, ampiamente applicato nei protocolli PSI
• Hashing a Cuckoo 2D: Progettato specificamente per PSI a due parti, realizza complessità O(M)

Conclusioni e Discussione

Conclusioni Principali

1. Svolta nella Praticabilità: Primo a rendere OT-MP-PSI praticabile su scala di registri di rete reali
2. Miglioramento dell'Efficienza: Realizza miglioramenti di prestazioni di ordini di grandezza attraverso il nuovo schema di hashing
3. Distribuzione Flessibile: Fornisce due opzioni di distribuzione per adattarsi a diversi requisiti di sicurezza
4. Verifica Pratica: Convalida la praticabilità del protocollo in ambienti di rete multi-istituzionali reali

Limitazioni

1. Modello Semi-Onesto: Sebbene estensibile al modello malevolo, rimane vulnerabile agli attacchi di sostituzione di input
2. Perdita di Dimensione dell'Insieme: Il protocollo principale non tratta la dimensione dell'insieme dei partecipanti come informazione privata
3. Fiducia nell'Aggregatore: La distribuzione non interattiva richiede fiducia che l'aggregatore non colludere con i partecipanti
4. Limitazioni di Soglia: Quando t è vicino a N/2 e N è grande, il vantaggio di complessità potrebbe non essere evidente

Direzioni Future

1. Sicurezza Malevola: Estendere il protocollo per resistere agli attaccanti attivi
2. Soglia Dinamica: Supportare il calcolo di soglie multiple senza costi aggiuntivi per i client
3. Ottimizzazione su Larga Scala: Ulteriore ottimizzazione dell'elaborazione delle combinazioni di partecipanti
4. Privacy Aumentata: Esplorare tecniche di privacy differenziale per proteggere le informazioni sulla dimensione dell'insieme

Valutazione Approfondita

Punti di Forza

1. Contributo Teorico Significativo: Il nuovo schema di hashing rappresenta un'importante svolta nella tecnologia esistente, riducendo la complessità da esponenziale a lineare
2. Alto Valore Pratico: Affronta il problema critico di privacy nel rilevamento collaborativo di intrusioni nel mondo reale
3. Esperimenti Completi: Fornisce sia analisi teorica che verifica su dati reali, con configurazione sperimentale ragionevole
4. Implementazione Ingegneristica Completa: Fornisce implementazione open-source, migliorando la riproducibilità
5. Sicurezza Rigorosa: Fornisce prova di sicurezza formale e due opzioni di distribuzione

Insufficienze

1. Limitazioni del Modello di Sicurezza: Il modello semi-onesto potrebbe non essere sufficientemente forte in alcuni scenari pratici
2. Scelta dei Parametri: La scelta di 20 tabelle si basa su ottimizzazione empirica, con guida teorica insufficiente
3. Confini di Scalabilità: L'applicabilità a scale estremamente grandi (come a livello di Internet globale) non è stata sufficientemente esplorata
4. Confronti di Base Limitati: Principalmente confrontato con un metodo di base, mancano confronti di prestazioni più completi

Impatto

1. Valore Accademico: Fornisce un nuovo percorso tecnico per il campo del calcolo multipartito sicuro
2. Significato Pratico: Affronta direttamente le esigenze reali nel campo della sicurezza di rete
3. Promozione Tecnologica: Lo schema di hashing potrebbe essere applicabile ad altri problemi di calcolo multipartito
4. Potenziale di Standardizzazione: Potrebbe diventare il protocollo standard per il rilevamento collaborativo di intrusioni

Scenari di Applicazione

1. Sicurezza di Rete Multi-Istituzionale: Protezione collaborativa di istituzioni simili come università e ospedali
2. Servizi di Sicurezza Cloud: Analisi di registri che preserva la privacy nei centri operativi di sicurezza
3. Condivisione di Intelligence su Minacce: Scambio di indicatori di minaccia sotto vincoli di privacy
4. Requisiti di Conformità: Collaborazione di dati conforme a normative sulla privacy come GDPR

Riferimenti Bibliografici

Questo articolo cita 53 riferimenti correlati, coprendo lavori importanti in crittografia, sicurezza di rete, calcolo multipartito e altri campi, fornendo una base teorica solida e uno sfondo tecnico completo.

Valutazione Complessiva: Questo è un articolo di alta qualità di crittografia applicata che raggiunge un buon equilibrio tra innovazione teorica e applicazione pratica. Il nuovo schema di hashing proposto non solo rappresenta un'importante svolta teorica, ma dimostra anche un valore significativo nelle applicazioni pratiche. La verifica sperimentale dell'articolo è completa, l'analisi di sicurezza è rigorosa e fornisce importanti contributi tecnici al campo della sicurezza di rete collaborativa.