ORQ: Complex Analytics on Private Data with Strong Security Guarantees

ORQ è un sistema innovativo che consente un'analisi collaborativa efficiente e crittograficamente sicura di grandi dataset privati eliminando il costo quadratico delle join sicure attraverso l'aggregazione on-the-fly, raggiungendo così le prestazioni di TPC-H Scale Factor 10 mediante computazione multi-party senza fare affidamento su terze parti fidate o sulla fuga di informazioni.

L'essenziale

Immagina di essere il capitano di una nave e di avere altri tre capitani con te. Ognuno di voi possiede una mappa segreta con la posizione di tesori preziosi, ma nessuno di voi si fida abbastanza degli altri da mostrare la propria mappa. Vorresti collaborare per trovare il percorso migliore che combini tutte le vostre mappe, ma non vuoi rivelare dove si trovano i tuoi tesori specifici, né nemmeno quanti tesori hai.

Questo è il problema che Orq risolve.

Il Problema: L' "Esplosione Quadratica"

Nel mondo del calcolo sicuro, esiste una tecnica chiamata Multiparty Computation (MPC). Essa permette a delle persone di computare cose insieme senza rivelare i propri dati privati. Pensa a un gruppo di persone che risolve un problema matematico dove ognuno scrive i propri numeri su un foglio di carta, ma passano intorno solo versioni "criptate" di quei numeri.

Tuttavia, c'è un grande collo di bottiglia: i Join.
Immagina di avere due liste di nomi. Vuoi trovare tutti coloro che compaiono in entrambe le liste.

• Il Vecchio Modo: Se provi a fare questo in modo sicuro senza rivelare nulla, i computer devono controllare ogni singolo nome della Lista A contro ogni singolo nome della Lista B. Se la Lista A ha 1.000 nomi e la Lista B ha 1.000 nomi, il computer deve fare 1.000.000 di controlli (1.000 x 1.000).
• L'Incubo "a Cascata": Se hai tre liste da unire, i controlli esplodono a 1.000.000.000. Se ne hai quattro, arrivi a un trilione. Questo è chiamato "esplosione quadratica". È come cercare un ago in un pagliaio, ma ogni volta che guardi, il pagliaio raddoppia di dimensioni. I sistemi precedenti o rinunciavano per evitare questa esplosione, o filtravano segreti per evitarla, o avevano bisogno di una terza parte "fidata" (come un giudice) che sorvegliasse il processo.

La Soluzione: Orq (Il "Semplificatore Intelligente")

I ricercatori hanno costruito un sistema chiamato Orq che cambia le regole del gioco. Invece di controllare alla cieca ogni combinazione, Orq usa un trucco intelligente: Ordina le liste per prima cosa.

Pensa a come organizzare una biblioteca disordinata.

1. Il Vecchio Modo: Ti avvicini a ogni libro della biblioteca e chiedi: "Questo libro parla di gatti?". Lo fai per ogni singolo libro, anche se sono tutti nella sezione sbagliata.
2. Il Modo Orq: Prima organizzi i libri in ordine alfabetico. Ora, se vuoi trovare tutti i libri sui "Gatti", ti basta andare alla sezione "G". Non hai bisogno di controllare le sezioni "A" o "Z".

Orq fa questo con i dati. Ordina i dati segreti in modo che gli elementi corrispondenti finiscano uno accanto all'altro. Questo trasforma l'impossibile compito di "controllare tutto" in un gestibile compito di "controllare i vicini".

Il Segreto: Aggregazione "On-the-Fly"

Il documento evidenzia un'intuizione specifica: nella maggior parte delle domande del mondo reale (come "Quanto denaro abbiamo guadagnato?"), in realtà non abbiamo bisogno di vedere la lista finale di ogni singola transazione. Ci serve solo il totale.

Orq utilizza una tecnica chiamata Join-Aggregation.

• Immagina una Staffetta: Invece di correre l'intera gara, fermarsi a contare ogni passo e poi correre di nuovo, Orq combina la corsa e il conteggio in un unico movimento fluido.
• Mentre i dati si muovono attraverso il sistema, Orq unisce le tabelle e somma i numeri (aggrega) esattamente nello stesso momento. Non crea mai la massiccia lista intermedia di tutte le possibili combinazioni. Mantiene la dimensione dei dati limitata, come un secchio che non trabocca mai, indipendentemente da quanta acqua ci versi dentro.

I Risultati: Velocità e Scala

I ricercatori hanno testato Orq in due ambienti:

1. LAN (Local Area Network): Computer nella stessa area/edificio.
2. WAN (Wide Area Network): Computer attraverso internet (come in paesi diversi).

Cosa hanno scoperto:

• Velocità: Orq è drammaticamente più veloce dei sistemi precedenti. In alcuni casi, è stato 800 volte più veloce.
• Scala: Sono stati in grado di eseguire il famoso benchmark TPC-H (un test standard per le prestazioni dei database) con un "Scale Factor 10". Ciò significa che hanno elaborato 58 milioni di righe di dati interamente sotto crittografia sicura.
  • Contesto: I sistemi sicuri precedenti potevano gestire questa quantità di dati solo se filtravano segreti o usavano una terza parte fidata. Orq l'ha fatto con zero perdite di dati (leakage) e senza una terza parte fusa.
• Sicurezza: Funziona anche se alcuni dei computer sono "malicious" (cercano di imbrogliare) o "semi-honest" (seguono le regole ma cercano di sbirciare).

Conclusione

Orq è come un nuovo, super-efficiente motore per un'auto sicura. Prima, cercare di guidare un'auto sicura con un carico pesante (dati complessi) era così lento e pericoloso che le persone o non guidavano affatto o toglievano i blocchi di sicurezza (filtrando i dati). Orq ha riprogettato il motore in modo da poter guidare velocemente, trasportare un carico enorme e mantenere i blocchi di sicurezza saldamente al loro posto.

Hanno inoltre reso il codice open-source, in modo che chiunque possa usare questo "motore" per costruire i propri strumenti di analisi dei dati sicuri.

Sommario tecnico

Riassunto Tecnico: Orq – Analisi Complessa su Dati Privati con Forti Garanzie di Sicurezza

1. Definizione del Problema

Il documento affronta la sfida di eseguire analisi relazionali complesse (specificamente join multi-via e aggregazioni) su grandi dataset privati in un contesto di Multiparty Computation (MPC) esternalizzata (outsourced). In questo scenario, i proprietari dei dati distribuiscono partizioni segrete (secret shares) dei loro dati a un insieme di parti computazionali (server) non fidate e non colludenti.

Il collo di bottiglia principale nei sistemi MPC precedenti è l'effetto a cascata dei join obbliviosi (oblivious joins). Per mantenere l'obliviosità (nascondere i pattern di accesso e la distribuzione dei dati), i join obbliviosi standard su tabelle con $n$ record devono produrre una dimensione di output nel caso peggiore pari a $n^2$ (il prodotto cartesiano). Per query che coinvolgono più join ($k$ join), ciò porta a una complessità di tempo e spazio di $O(n^{k+1})$, rendendo intrattabili le query complesse per dataset di grandi dimensioni.

Le soluzioni esistenti affrontano un trilemma:

1. Costo Quadratico: Calcolare l'intero prodotto cartesiano (costoso).
2. Scarto Silenzioso (Silent Dropping): Imporre un limite sub-quadratico scartando silenziosamente i record (errato).
3. Leakage (Perdita di Informazioni): Rivelare la dimensione del risultato del join ai server (insicuro).

I lavori precedenti in contesti esternalizzati (ad esempio, Secrecy, Scape) soffrono o di costi quadratici o della rivelazione delle dimensioni dei risultati. Inoltre, molti sistemi esistenti si affidano a basi di calcolo fidate (TCB) o modelli specifici di proprietà dei dati (ad esempio, peer-to-peer dove i proprietari sono anche parti computazionali) che non si generalizzano al modello esternalizzato in cui i server non vedono mai il testo in chiaro.

2. Metodologia

Orq introduce un runtime di sistema olistico progettato per valutare query complesse con una complessità di $O(n \log n)$, evitando l'esplosione quadratica senza rivelare informazioni.

2.1 Intuizione Centrale: Limiti Indipendenti dai Dati

Gli autori osservano che in molti scenari pratici di analisi collaborativa, la dimensione del risultato della query è limitata nel caso peggiore dalla dimensione dell'input ($O(n)$), indipendentemente dalla distribuzione dei dati. Ciò vale anche per i join many-to-many, a condizione che la struttura della query consenta un'aggregazione decomponibile. Orq sfrutta questa osservazione per limitare le dimensioni dei risultati intermedi.

2.2 L'Operatore Composito Join-Aggregation

L'innovazione centrale è un operatore di Join-Aggregation fuso che evita la materializzazione del prodotto cartesiano.

• Meccanismo: Invece di eseguire prima il join e poi l'aggregazione, Orq esegue una valutazione in stile "MapReduce". Applica una pre-aggregazione (valutazione parziale) sulle tabelle di input per gestire i duplicati, esegue il join e poi applica una post-aggregazione.
• Implementazione: L'operatore concatena le tabelle di input, le ordina in modo obblivioso sulle chiavi di join e utilizza una rete di aggregazione (Aggregation Network - AggNet) di tipo butterfly per propagare i valori e calcolare le aggregazioni in un unico flusso di controllo.
• Supporto: Supporta inner, outer, semi- e anti-join, oltre ad aggregazioni arbitrarie definite dall'utente (sum, count, min, max, avg).
• Gestione dei Duplicati: Per i join many-to-many, Orq pre-aggrega un input per creare chiavi uniche (molteplicità), esegue il join e poi post-aggrega per combinare le molteplicità. Ciò assicura che la dimensione della tabella intermedia non superi mai la cardinalità del più grande input.

2.3 Primitiva Oblivious e Ordinamento

Per supportare l'operatore join-aggregation, Orq implementa primitive obbliviose allo stato dell'arte:

• Ordinamento (Sorting): Orq fornisce implementazioni vettorializzate e data-parallel di Quicksort e Radixsort.
  • Quicksort: Utilizza un paradigma iterativo di shuffle-then-sort per ridurre i round di comunicazione a $O(\log n)$.
  • Radixsort: Utilizza un approccio ibrido che combina bit-permutation eager con lo shuffling obblivioso.
  • TableSort: Un wrapper che estrae la permutazione di ordinamento da un sort con padding e la applica a tutte le colonne di una tabella, evitando l'ordinamento ridondante di più colonne.
• Shuffling: Primitive di shuffling obblivioso generalizzate compatibili con vari protocolli MPC.
• Vettorizzazione: Tutti gli operatori sono implementati utilizzando un formato di dati a colonne, consentendo ai messaggi indipendenti all'interno di una fase di essere raggruppati (batched) e inviati in un singolo round di comunicazione.

2.4 Architettura del Sistema

• API Dataflow: Gli utenti definiscono le query utilizzando un'API in stile dataflow (simile ad Apache Spark) invece di SQL, permettendo l'espressione concisa di pipeline complesse.
• Agnosticismo rispetto al Protocollo: Gli operatori sono costruiti come astrazioni black-box sopra le primitive MPC ($+, \times, \oplus, \land$). Orq supporta tre protocolli:
  1. Semi-honest, dishonest majority (ABY, 2-party).
  2. Semi-honest, honest majority (Araki et al., 3-party).
  3. Malicious-secure, honest majority (Fantastic Four, 4-party).
• Livello di Comunicazione: Un livello personalizzato basato su TCP con buffer circolari lock-free per ammortizzare i costi di rete, particolarmente in ambienti WAN.

3. Contributi Chiave

1. Sistema Orq: Un sistema completo per l'analisi relazionale complessa nell'ambiente MPC esternalizzato, che supporta join multi-via e aggregazioni con forti garanzie di sicurezza (nessuna perdita di informazioni sulla dimensione dei risultati).
2. Nuovo Operatore Join-Aggregation: Una tecnica che decompone e applica prontamente le aggregazioni per limitare le dimensioni dei risultati intermedi, raggiungendo una complessità di $O(n \log n)$ per i join che precedentemente richiedevano $O(n^2)$.
3. Primitive Protocol-Agnostic: Un'implementazione unificata di operatori obbliviosi (join, sort, aggregazioni) che possono essere istanziati con protocolli MPC semi-honest o malicious.
4. Sorting Scalabile: Implementazioni data-parallel vettorializzate di ordinamento obblivioso che gestiscono fino a 537 milioni di righe, superando significativamente lo stato dell'arte.
5. Valutazione Esaustiva: La prima esecuzione end-to-end in MPC del benchmark completo TPC-H (Scale Factor 10) senza leakage o l'uso di hardware fidato.

4. Risultati Sperimentali

Gli autori hanno valutato Orq su implementazioni LAN e WAN attraverso diversi carichi di lavoro, inclusa la suite completa TPC-H e query provenienti da lavori precedenti.

• Performance rispetto allo Stato dell'Arte:
  • Vs. Secrecy: Orq ottiene una latenza fino a 827$\times$ inferiore. Secrecy utilizza join $O(n^2)$ ed esecuzione single-threaded; Orq utilizza $O(n \log n)$ e vettorizzazione.
  • Vs. SecretFlow: Orq è da 1.1$\times$ a 1.5$\times$ più veloce sulle query di join e da 58$\times$ a 85$\times$ più veloce sulle query non-join, nonostante SecretFlow riveli le dimensioni dei risultati del join. Orq raggiunge questo risultato senza alcun leakage.
  • Vs. MP-SPDZ: L'ordinamento di Orq è fino a 189$\times$ più veloce grazie alla data-parallelism.
• Scalabilità:
  • Orq elabora le query TPC-H con Scale Factor 10 (media di 58 milioni di righe) interamente sotto MPC.
  • La query più costosa (Q21) completa in 42 minuti (LAN, sicurezza malicious) e 18 ore (WAN, sicurezza malicious).
  • I protocolli di sorting scalano fino a 537 milioni di righe (Quicksort, SH-HM) e 134 milioni di righe (Radixsort, Mal-HM).
• Bandwidth: Orq mostra un consumo di banda fino a due ordini di grandezza inferiore rispetto a Secrecy grazie ai miglioramenti asintotici.
• Preprocessing: Il documento valuta la generazione di Beaver triple, mostrando che i protocolli sub-quadratici (Doerner et al.) offrono risparmi significativi di banda rispetto ai metodi tradizionali, nonostante l'overhead computazionale più elevato.

5. Significato e Claim

Il documento sostiene che Orq rappresenti un passo avanti significativo nel rendere pratiche le analisi sicure per l'analisi collaborativa di dati su larga scala.

• Rottura della Barriera Quadratica: Orq dimostra che è possibile un'esecuzione efficiente e completamente oblivious di join multi-via complessi senza rivelare le dimensioni dei risultati o fare affidamento su hardware fidato.
• Praticità su Scala: Eseguendo con successo l'intero benchmark TPC-H con Scale Factor 10 (precedentemente raggiungibile solo con leakage o compute fidato), Orq prova che l'MPC può gestire carichi di lavoro di livello enterprise.
• Generalità: Il sistema non è limitato a specifici modelli di proprietà dei dati o modelli di minaccia, supportando sia avversari semi-honest che malicious in contesti esternalizzati.
• Open Source: Gli autori hanno rilasciato Orq come open-source per facilitare ulteriore ricerca e adozione.

Gli autori notano che, sebbene richiedano attualmente un'API dataflow (invece di un pianificatore SQL automatico), le prestazioni e le proprietà di sicurezza del sistema stabiliscono un nuovo standard per l'analisi relazionale sicura. Il lavoro futuro include l'integrazione di una pianificazione automatica delle query e l'ulteriore ottimizzazione dei controlli malicious per gli ambienti WAN.