💻 computer science

ORQ: Complex Analytics on Private Data with Strong Security Guarantees

ORQ is een nieuw systeem dat efficiënte, cryptografisch beveiligde collaboratieve analyse van grote private datasets mogelijk maakt door de kwadratische kosten van beveiligde joins te elimineren via on-the-fly aggregatie, waardoor het TPC-H Scale Factor 10 prestaties bereikt onder multi-party computation zonder afhankelijk te zijn van vertrouwde derde partijen of informatielekken.

Oorspronkelijke auteurs: Eli Baum, Sam Buxbaum, Nitin Mathai, Muhammad Faisal, Vasiliki Kalavri, Mayank Varia, John Liagouris

Gepubliceerd 2026-06-24

📖 5 min leestijd🧠 Diepgaand

CC BY 4.0

Oorspronkelijke auteurs: Eli Baum, Sam Buxbaum, Nitin Mathai, Muhammad Faisal, Vasiliki Kalavri, Mayank Varia, John Liagouris

Oorspronkelijk artikel gelicentieerd onder CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ Dit is een AI-gegenereerde uitleg van het onderstaande artikel. Het is niet geschreven of goedgekeurd door de auteurs. Raadpleeg het oorspronkelijke artikel voor technische nauwkeurigheid. Lees de volledige disclaimer

Stel je voor dat ik de kapitein ben van een schip, en ik heb drie andere kapiteins. Elk van ons houdt een geheime kaart met waardevolle schatlocaties vast, maar niemand van ons vertrouwt de anderen genoeg om de kaarten te laten zien. Je wilt samenwerken om de beste route te vinden die alle kaarten combineert, maar je wilt niet onthullen waar jouw specifieke schatten zich bevinden, of zelfs hoeveel schatten je hebt.

Dit is het probleem dat Orq oplost.

Het Probleem: De "Kwadratische Explosie"

In de wereld van beveiligde computing is er een techniek genaamd Multiparty Computation (MPC). Hiermee kunnen mensen samen dingen berekenen zonder hun privédata te onthullen. Denk aan een groep mensen die samen een wiskundig probleem oplost waarbij iedereen zijn getallen op een papiertje schrijft, maar ze geven alleen "versleutelde" versies van die getallen aan elkaar door.

Echter, er is een grote flessenhals: Joins.
Stel je voor dat je twee lijsten met namen hebt. Je wilt weten wie er op beide lijsten voorkomt.

De Oude Manier: Als je dit veilig wilt doen zonder iets te onthullen, moeten de computers elke enkele naam in Lijst A controleren tegen elke enkele naam in Lijst B. Als Lijst A 1.000 namen heeft en Lijst B ook 1.000 namen, moet de computer 1.000.000 controles uitvoeren (1.000 x 1.000).
De "Cascaderende" Nachtmerrie: Als je drie lijsten wilt samenvoegen, explodeert het aantal controles naar 1.000.000.000. Als je er vier hebt, is het een biljoen. Dit wordt een "kwadratische blowup" genoemd. Het is alsof je een naald in een hooiberg probeert te vinden, maar elke keer als je kijkt, verdubbelt de hooiberg in grootte. Eerdere systemen gaven ofwel op, lekten geheimen om deze explosie te vermijden, of hadden een "vertrouwde" derde partij (zoals een rechter) nodig om toezicht te houden.

De Oplossing: Orq (De "Slimme Sorteerder")

De onderzoekers hebben een systeem gebouwd genaamd Orq dat de regels van het spel verandert. In plaats van blindelings elke combinatie te controleren, gebruikt Orq een slimme truc: het sorteert de lijsten eerst.

Denk aan het organiseren van een rommelige bibliotheek.

De Oude Manier: Je loopt naar elk boek in de bibliotheek en vraat: "Gaat dit boek over katten?" Je doet dit voor elk boek, zelfs als ze allemaal in de verkeerde sectie liggen.
De Orq-manier: Je organiseert de boeken eerst op alfabetische volgorde. Nu, als je alle "Kat"-boeken wilt vinden, ga je gewoon naar de "K"-sectie. Je hoeft de "A" of "Z" secties niet te controleren.

Orq doet dit met data. Het sorteert de geheime data zodat overeenkomende items direct naast elkaar terechtkomen. Dit verandert de onmogelijke "controleer alles"-taak in een beheersbare "controleer buren"-taak.

Het Geheime Ingrediënt: "On-the-Fly" Aggregatie

Het paper benadrukt een specifiek inzicht: in de meeste echte vragen (zoals "Hoeveel geld hebben we verdiend?"), hebben we niet de volledige lijst van elke afzonderlijke transactie nodig. We hebben alleen het totaal nodig.

Orq gebruikt een techniek genaamd Join-Aggregation.

Stel je een estafette voor: In plaats van de hele race te rennen, halverwege te stoppen om elke stap te tellen, en dan weer verder te rennen, combineert Orq het rennen en het tellen tot één vloeiende beweging.
Terwijl de data door het systeem beweegt, voegt Orq de tabellen samen en telt de getallen op (aggregeert) op exact hetzelfde moment. Het creëert nooit de enorme, tussenliggende lijst van alle mogelijke combinaties. Het houdt de grootte van de data begrensd, als een emmer die nooit overstroomt, ongeacht hoeveel water je erin giet.

De Resultaten: Snelheid en Schaal

De onderzoekers hebben Orq getest in twee omgevingen:

LAN (Local Area Network): Computers in hetzelfde gebouw.
WAN (Wide Area Network): Computers over het internet verspreid (zoals in verschillende landen).

Wat ze ontdekten:

Snelheid: Orq is spectaculair sneller dan eerdere systemen. In sommige gevallen was het 800 keer sneller.
Schaal: Ze waren in staat om de beroemde TPC-H benchmark (een standaardtest voor databaseprestaties) uit te voeren met een "Scale Factor 10". Dit betekent dat ze 58 miljoen rijen aan data volledig onder veilige encryptie hebben verwerkt.
- Context: Eerdere beveiligde systemen konden dit veel aan data alleen verwerken als ze geheimen lekten of een vertrouwde derde partij gebruikten. Orq deed dit met nul lekkage en zonder vertrouwde derde partij.
Beveiliging: Het werkt zelfs als sommige van de computers "malicious" (kwaadwillend/proberen te bedriegen) of "semi-honest" (de regels volgen maar proberen te spieken) zijn.

De Kernboodschap

Orq is als een nieuwe, super-efficiënte motor voor een beveiligde auto. Voorheen was het proberen te rijden met een beveiligde auto met een zware lading (complexe data) zo traag en gevaarlijk dat mensen ofwel niet reden, of de veiligheidssloten eraf haalden (data lekten). Orq heeft de motor opnieuw ontworpen zodat je snel kunt rijden, een enorme lading kunt vervoeren en de veiligheidssloten stevig op hun plek houdt.

Ze hebben de code zelfs open-source gemaakt, zodat iedereen deze "motor" kan gebruiken om zijn eigen beveiligde data-analyse tools te bouwen.

Technische Samenvatting: Orq – Complexe Analytics op Privédata met Sterke Beveiligingsgaranties

1. Probleemstelling

Het artikel behandelt de uitdaging van het uitvoeren van complexe relationele analytics (specifiek multi-way joins en aggregaties) op grote privé datasets binnen een uitbestede Secure Multiparty Computation (MPC) omgeving. In deze setting verdelen data-eigenaren geheime shares van hun data naar een set onbetrouwbare, niet-collerende rekenpartijen (servers).

De kernbottleneck in eerdere MPC-systemen is het cascaderende effect van oblivious joins. Om de obliviousness te behouden (het verbergen van toegangspatronen en datadistributie), moeten standaard oblivious joins op tabellen met $n$ records een worst-case output produceren van omvang $n^2$ (het Cartesisch product). Voor queries die meerdere joins bevatten ( $k$ joins), leidt dit tot een tijd- en ruimtecomplexiteit van $O(n^{k+1})$ , wat complexe queries onhandelbaar maakt voor grote datasets.

Bestaande oplossingen kampen met een trilemma:

Kwadratische Kosten: Het volledige Cartesisch product berekenen (duur).
Stille Verwijdering (Silent Dropping): Een sub-kwadratische bovengrens afdwingen door records stilzwijgend te verwijderen (incorrect).
Lekkage: De grootte van het join-resultaat lekken naar de servers (onveilig).

Eerdere werken in uitgestelde omgevingen (bijv. Secrecy, Scape) lijden ofwel aan kwadratische kosten, ofwel lekken ze de grootte van het resultaat. Bovendien vertrouwen veel bestaande systemen op Trusted Compute Bases (TCB's) of specifieke databezitsmodellen (bijv. peer-to-peer waarbij eigenaren ook rekenpartijen zijn) die niet generaliseren naar het uitgestelde model waarbij servers nooit de plaintext zien.

2. Methodologie

Orq introduceert een holistisch systeemruntime ontworpen om complexe queries te evalueren met een $O(n \log n)$ complexiteit, waarbij de kwadratische explosie wordt vermeden zonder informatie te lekken.

2.1 Kerninzicht: Data-onafhankelijke Grenzen

De auteurs merken op dat in veel praktische scenario's voor collaboratieve analytics de grootte van het query-resultaat worst-case begrensd is door de inputgrootte ( $O(n)$ ), onafhankelijk van de datadistributie. Dit geldt zelfs voor many-to-many joins, mits de querystructuur een decomposeerbare aggregatie toestaat. Orq maakt gebruik van deze observatie om de omvang van tussenresultaten te beperken.

2.2 De Composiete Join-Aggregatie Operator

De centrale innovatie is een gefuseerde Join-Aggregation operator die het materialiseren van het Cartesisch product voorkomt.

Mechanisme: In plaats van eerst te joinen en daarna te aggregeren, voert Orq een "MapReduce-stijl" evaluatie uit. Het past een pre-aggregatie (partiële evaluatie) toe op de inputtabellen om duplicaten af te handelen, voert de join uit, en past vervolgens een post-aggregatie toe.
Implementatie: De operator concateneert inputtabellen, sorteert ze obliviously op de join-sleutels, en gebruikt een butterfly-stijl Aggregation Network (AggNet) om waarden te propageren en aggregaties in een enkele control flow te berekenen.
Ondersteuning: Het ondersteunt inner-, outer-, semi- en anti-joins, evenals willekeurige user-defined aggregaties (sum, count, min, max, avg).
Afhandeling van Duplicaten: Voor many-to-many joins pre-aggregeert Orq één input om unieke sleutels (multipliciteit) te creëren, voert de join uit, en post-aggregeert vervolgens om multipliciteiten te combineren. Dit zorgt ervoor dat de omvang van de tussenliggende tabel nooit de cardinaliteit van de grotere input overschrijdt.

2.3 Oblivious Primitives en Sorting

Om de join-aggregatie operator te ondersteunen, implementeert Orq state-of-the-art oblivious primitives:

Sorteren: Orq biedt gevectoriseerde, data-parallelle implementaties van Quicksort en Radixsort.
- Quicksort: Gebruikt een iteratief, shuffle-then-sort paradigma om het aantal communicatierondes te reduceren tot $O(\log n)$ .
- Radixsort: Gebruikt een hybride aanpak die eager bit-permutatie combineert met oblivious shuffling.
- TableSort: Een wrapper die de sorteerpermutatie extraheert uit een gepadde sort en deze toepast op alle kolommen van een tabel, om redundant sorteren van meerdere kolommen te voorkomen.
Shuffling: Gegeneraliseerde oblivious shuffling primitives compatibel met diverse MPC-protocollen.
Vectorisatie: Alle operators zijn geïmplementeerd met een kolomgeoriënteerd dataformaat, waardoor onafhankelijke berichten binnen een fase gebatcht kunnen worden en in een enkele communicatieronde verzonden kunnen worden.

2.4 Systeemarchitectuur

Dataflow API: Gebruikers definiëren queries met een dataflow-stijl API (vergelijkbaar met Apache Spark) in plaats van SQL, wat een beknopte expressie van complexe pipelines mogelijk maakt.
Protocol-agnostisch: Operators zijn gebouwd als black-box abstracties over MPC-primitives ( $+, \times, \oplus, \land$ $+, \times, \oplus, \land$ ). Orq ondersteunt drie protocollen:
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).
Communicatielaag: Een aangepaste TCP-gebaseerde laag met lock-free ringbuffers om netwerkkosten te amortiseren, met name in WAN-omgevingen.

3. Belangrijkste Bijdragen

Orq Systeem: Een compleet systeem voor complexe relationele analytics in de uitgestede MPC-setting, met ondersteuning voor multi-way joins en aggregaties met sterke beveiligingsgaranties (geen lekkage van resultaatgroottes).
Nieuwe Join-Aggregatie Operator: Een techniek die aggregaties deelt en vroegtijdig toepast om de omvang van tussenresultaten te beperken, waarmee een $O(n \log n)$ complexiteit wordt bereikt voor joins die voorheen $O(n^2)$ vereisten.
Protocol-agnostische Primitives: Een uniforme implementatie van oblivious operators (joins, sorts, aggregations) die geïnstantieerd kunnen worden met semi-honest of malicious MPC-protocollen.
Schaalbare Sorting: Gevectoriseerde data-parallelle implementaties van oblivious sorting die tot 537 miljoen rijen kunnen verwerken, wat aanzienlijk beter presteert dan de huidige stand van de techniek.
Uitgebreide Evaluatie: De eerste end-to-end MPC-executie van de volledige TPC-H benchmark (Scale Factor 10) zonder lekkage of vertrouwde compute.

4. Experimentele Resultaten

De auteurs hebben Orq geëvalueerd op LAN- en WAN-deployments over diverse workloads, inclusief de volledige TPC-H benchmark en queries uit eerdere werken.

Prestaties t.o.v. de Stand van de Techniek:
- T.o.v. Secrecy: Orq bereikt een tot wel 827 $\times$ lagere latentie. Secrecy gebruikt $O(n^2)$ joins en single-threaded executie; Orq gebruikt $O(n \log n)$ en vectorisatie.
- T.o.v. SecretFlow: Orq is 1.1 $\times$ tot 1.5 $\times$ sneller op join-queries en 58 $\times$ tot 85 $\times$ sneller op non-join queries, ondanks het feit dat SecretFlow de grootte van join-resultaten lekt. Orq bereikt dit zonder enige lekkage.
- T.o.v. MP-SPDZ: De sorting van Orq is tot wel 189 $\times$ sneller dankzij data-parallelisme.
Schaalbaarheid:
- Orq verwerkt Scale Factor 10 TPC-H queries (gemiddeld 58M rijen) volledig onder MPC.
- De duurste query (Q21) voltooit in 42 minuten (LAN, malicious security) en 18 uur (WAN, malicious security).
- Sorting-protocollen schalen naar 537 miljoen rijen (Quicksort, SH-HM) en 134 miljoen rijen (Radixsort, Mal-HM).
Bandbreedte: Orq vertoont tot twee ordes van grootte minder bandbreedteverbruik vergeleken met Secrecy vanwege de asymptotische verbeteringen.
Preprocessing: Het artikel benchmarkt de Beaver triple generatie, waarbij wordt getoond dat sub-kwadratische protocollen (Doerner et al.) aanzienlijke bandbreedtebesparingen bieden ten opzichte van traditionele methoden, ondanks een hogere computationele overhead.

5. Betekenis en Claims

Het artikel claimt dat Orq een belangrijke stap voorwaarts is in het praktisch maken van secure analytics voor real-world, grootschalige collaboratieve data-analyse.

Doorbreken van de Kwadratische Barrière: Orq demonstreert dat efficiënte, volledig oblivious evaluatie van complexe multi-way joins mogelijk is zonder de grootte van resultaten te lekken of te vertrouwen op vertrouwde hardware.
Praktische Bruikbaarheid op Schaal: Door succesvol de volledige TPC-H benchmark op Scale Factor 10 uit te voeren (voorheen alleen haalbaar met lekkage of vertrouwde compute), bewijst Orq dat MPC enterprise-scale workloads kan afhandelen.
Generaliteit: Het systeem is niet beperkt tot specifieke databezitsmodellen of dreigingsmodellen, en ondersteunt zowel semi-honest als malicious adversaries in uitgestede settings.
Open Source: De auteurs hebben Orq als open-source vrijgegeven om verder onderzoek en adoptie te faciliteren.

De auteurs merken op dat zij momenteel een dataflow API vereisen (in plaats van een automatische SQL-planner), maar dat de prestaties en beveiligingseigenschappen van het systeem een nieuwe baseline vestigen voor secure relationele analytics. Toekomstig werk omvat het integreren van automatische query planning en het verder optimaliseren van malicious checks voor WAN-omgevingen.