Secure Sparse Matrix Multiplications and their Applications to Privacy-Preserving Machine Learning

Dit artikel introduceert geoptimaliseerde MPC-algoritmen voor veilige vermenigvuldiging van schaarse matrices, die de communicatiekosten drastisch verlagen en privacy-bewuste machine learning-toepassingen met schaarse data mogelijk maken.

De kern

Stel je voor dat je een gigantische bibliotheek hebt, maar 99,9% van de boeken in die bibliotheek zijn in feite lege bladzijden. Als je die bibliotheek op een normale manier (dichtbevolkt) zou opslaan, zou je enorme schappen nodig hebben voor die lege bladzijden. Dat kost veel ruimte en het kost enorm veel tijd om te zoeken, omdat je elke lege pagina moet controleren.

In de wereld van computers en kunstmatige intelligentie (AI) noemen we dit spare data (spaarzame data). Denk aan een filmrecommodatiesysteem: jij hebt misschien 50 films bekeken, maar er zijn er 50.000 in de database. Voor jou is de lijst met "niet bekeken films" een enorme berg van nullen.

Het probleem is dat wanneer we deze data willen gebruiken voor AI, maar dan geheim houden (zodat niemand je kijkgeschiedenis kan zien), de bestaande computerprogramma's vastlopen. Ze proberen die lege plekken ook nog veilig te verwerken, wat leidt tot een enorme hoeveelheid geheugengebruik en communicatie tussen de computers. Het is alsof je probeert een heel leeg huis te verhuizen door elke lege muur te verpakken in kartonnen dozen.

Hier komt dit onderzoek van Marc Damie en zijn collega's om de hoek kijken. Ze hebben een nieuwe manier bedacht om deze "lege" data veilig en snel te verwerken.

De Analogie: De Geheime Postbode

Laten we de situatie eens uitleggen met een verhaal:

Het oude probleem (Dichte verwerking):
Stel je voor dat drie postbodes (de computers) samen een geheim moeten oplossen. Ze hebben een lijst met adressen, maar 99% van de adressen is "geen huis".
In het oude systeem moeten de postbodes voor elk adres op de lijst (ook de lege ones) een envelop openen, controleren of er iets in zit, en dan weer dichtdoen. Ze doen dit samen, maar ze mogen niet kijken wat erin zit.

• Gevolg: Ze verbranden enorm veel tijd en energie op lege enveloppen. Als de lijst heel groot is, raken ze hun kratten met enveloppen kwijt (geheugenprobleem) en kunnen ze het werk niet afmaken.

De nieuwe oplossing (Spare verwerking):
De auteurs van dit papier hebben een slimme truc bedacht. Ze zeggen: "Waarom verpakken we de lege enveloppen? Laten we alleen de enveloppen met een brief erin meenemen."
Ze gebruiken een geheime sorteertruc.

1. De postbodes gooien alle enveloppen (inclusief de lege) in een grote, ondoorzichtige trommel.
2. Ze laten de trommel draaien en sorteren de enveloppen op een manier die niemand kan zien (geheimhouding).
3. Dankzij deze slimme sorteertruc komen alle enveloppen met een brief (de "niet-nul" waarden) bij elkaar.
4. De postbodes werken alleen die specifieke enveloppen af. De lege enveloppen worden genegeerd.

Het resultaat:
In plaats van 10.000 enveloppen te verwerken, verwerken ze misschien maar 10. Ze besparen hierdoor tot wel 1000 keer meer tijd en ruimte.

Wat hebben ze precies gedaan?

1. Slimme Sorteertrucjes: Ze hebben algoritmen (rekenregels) bedacht die werken met "geheime stukjes" van data. Ze gebruiken een techniek genaamd oblivious sorting (onbewust sorteren). Dit betekent dat de computers de data kunnen sorteren zonder te weten wat de data inhoudt. Het is alsof je een stapel kaarten sorteert op waarde, zonder ooit naar de kaarten te kijken, maar wel wetend dat ze op de juiste plek belanden.
2. Voor Reële Wereldtoepassingen: Ze hebben getoond dat hun methode werkt voor echte dingen zoals:
   • Filmrecommodaties: Het vinden van films die je misschien leuk vindt, zonder dat de computer weet wat je eerder hebt gezien.
   • Toegangcontrole: Het controleren of iemand toegang heeft tot een ziekenhuisdossier, zonder dat de beveiliging ziet wie de patiënten zijn.
   • In deze tests bleek dat de oude methoden vastliepen op het geheugen (ze hadden 19 Terabyte nodig!), terwijl hun nieuwe methode het probleem oplost met slechts 60 Gigabyte.

Het lastige stukje: Wat mag de computer wel weten?

Om deze slimme sorteertruc te laten werken, moeten de computers wel weten hoeveel enveloppen er ongeveer in de trommel zitten. Ze mogen niet weten welke adressen het zijn, maar ze moeten wel weten of er 100 of 1000 enveloppen met een brief zijn.

Als ze dit niet weten, kunnen ze de trommel niet goed instellen. Maar het vertellen van dit aantal kan soms gevoelig zijn (bijvoorbeeld: "Ik heb 1000 films bekeken" zegt iets over mijn hobby's).

De auteurs hebben daarom drie manieren bedacht om dit geheim te houden:

• Anonimiseren: De computers zien niet wie de enveloppen heeft gestuurd, alleen hoeveel er in totaal zijn.
• Opvullen (Padding): Iedereen doet alsof ze evenveel enveloppen hebben (zelfs als ze er maar een paar hebben), door lege enveloppen toe te voegen. Dit is veilig, maar kan veel ruimte verspillen.
• De "Sjabloon" (Matrix Templating): Dit is hun slimste idee. In plaats van naar het maximum te kijken, maken ze een "sjabloon" met verschillende vakjes. De ene groep enveloppen past in een klein vakje, de andere in een groot vakje. Zo hoeven ze niet alles op te vullen tot het grootste mogelijk aantal, maar passen ze de enveloppen slim in een vooraf bepaald patroon. Ze kunnen dit patroon zelfs berekenen zonder te kijken naar de echte data, door gebruik te maken van wiskundige "ruis" (Differential Privacy) die de privacy garandeert.

Conclusie

Kortom: Dit papier lost een groot probleem op in de wereld van privacy. Het maakt het mogelijk om supergrote lijsten met "lege" gegevens (zoals wat mensen niet doen, of wat ze niet kopen) veilig en snel te verwerken voor AI.

Zonder deze uitvinding zouden veel privacy-bewuste AI-toepassingen (zoals een aanbevelingssysteem dat je privacy respecteert) onmogelijk zijn, omdat de computers zouden vastlopen op de hoeveelheid lege ruimte die ze moeten verwerken. Met deze nieuwe methode kunnen we AI bouwen die niet alleen slim is, maar ook respectvol voor onze privacy, zonder dat we onze geheugenruimte opgebruiken.

Technische samenvatting

1. Het Probleem

Multi-party computation (MPC) maakt het mogelijk om machine learning (ML) algoritmen uit te voeren op vertrouwelijke data zonder deze te onthullen. Echter, bestaande MPC-frameworks missen geoptimaliseerde operaties voor spaarse data (data met een zeer hoog percentage nullen, zoals aanbevelingssystemen, genomics of natuurlijke taalverwerking).

• Geheugenproblemen: Het opslaan van grote spaarse datasets in een dichte (dense) vorm (waarbij elke cel een waarde bevat, ook als deze 0 is) vereist een onrealistisch groot geheugen. Bij zeer hoge sparsiteit (bijv. 99,99% nullen) wordt berekening met dichte matrices onmogelijk door geheugenoverloop.
• Communicatiekosten: Dichte MPC-algoritmes hebben communicatiekosten die lineair of kwadratisch zijn met de grootte van de volledige matrix, wat leidt tot enorme overhead bij spaarse data.
• Beperkingen van bestaande oplossingen: Bestaande protocollen voor veilige spaarse vermenigvuldiging vereisen vaak dat de rekenpartijen ook de eigenaren van de data zijn (niet-outsourced) of dat één partij de platte tekst (plaintext) van de spaarse structuur kent. Dit is niet schaalbaar voor moderne ML-toepassingen met duizenden data-eigenaren die hun data uitbesteden aan een groep servers.

2. Methodologie

De auteurs stellen twee nieuwe veilige algoritmes voor voor het vermenigvuldigen van ge-sharede spaarse matrices in een uitbestede (outsourced) setting. Hierbij delen data-eigenaren hun data met een groep reken-servers en disconnecten daarna.

Kernconcepten:

• Representatie: Gebruik van een tuple-representatie (COO-formaat) voor spaarse vectoren en matrices: een lijst van niet-nul waarden met hun coördinaten $(i, v_i)$.
• Primitieven: De algoritmes vertrouwen op veilige optelling, vermenigvuldiging, vergelijking, en vooral oblivious shuffling en oblivious sorting (sorteren zonder de waarden te onthullen).
• Public Knowledge: Veilige spaarse algoritmes vereisen enige publieke kennis over de sparsiteit (bijv. het aantal niet-nul elementen per rij) om efficiënt te zijn. De auteurs minimaliseren deze vereiste kennis.

De Algoritmes:

1. Vector-Vector: Een eenvoudige basis die twee spaarse vectoren concateneert, oblivious sorteert op coördinaten, en waarden vermenigvuldigt als coördinaten overeenkomen.
2. Matrix-Vector: Vermijdt de inefficiëntie van het herhaaldelijk sorteren per rij. In plaats daarvan worden elementen gegroepeerd per kolom, vermenigvuldigd en vervolgens geaggregeerd via sorteren.
3. Matrix-Matrix (bijv. $X^T X$): Generaliseert het probleem door niet-nul elementen van kolom $k$ van $X$ te vermenigvuldigen met niet-nul elementen van rij $k$ van $Y$. Alle scalaire producten worden berekend, gesorteerd op coördinaten en geaggregeerd.

Minimalisatie van Publieke Kennis:
Om de privacy te waarborgen en toch de noodzakelijke structuurinformatie te hebben, stellen de auteurs drie technieken voor:

• Rij-anonimisatie: De exacte sparsiteit per rij wordt verdoezeld; alleen de verdeling over de populatie is bekend.
• Max-row padding: Alle rijen worden opgepadded tot het maximale aantal niet-nul elementen (voegt veel dummy-data toe).
• Matrix Templating: Een geavanceerde techniek waarbij de matrix wordt opgedeeld in sub-matrices gebaseerd op kwantielen van de sparsiteitsverdeling. Rijen worden gepadded tot een lokaal maximum binnen hun sub-matrix, wat veel minder overhead veroorzaakt dan globale padding.

3. Belangrijkste Bijdragen

• Nieuwe Algoritmes: Twee veilige algoritmes voor matrix-vector en matrix-matrix vermenigvuldiging die specifiek zijn ontworpen voor secret-shared spaarse data in een outsourced setting.
• Schaalbaarheid: De algoritmes lossen het geheugenprobleem op dat dichte MPC-methodes ondervinden bij hoge sparsiteit.
• Privacy-geoptimaliseerde Kennis: Een reeks technieken om de vereiste publieke kennis over de datastructuur te minimaliseren en deze op een privacy-bewuste manier (via MPC of Differentiële Privacy) te schatten.
• Implementatie en Validatie: De auteurs hebben de algoritmes geïmplementeerd en getest op real-world ML-toepassingen.

4. Resultaten

De experimenten zijn uitgevoerd op datasets met sparsiteitsniveaus van 99%, 99,9% en 99,99%.

• Communicatiekosten: De auteurs tonen een reductie in communicatiekosten tot een factor 1000 vergeleken met dichte matrixvermenigvuldiging voor realistische probleemgroottes (bij 99,99% sparsiteit).
• Geheugengebruik:
  • Dichte methodes lopen vast bij geheugenoverloop (memory overflow) bij matrices met meer dan 10.000 kolommen (benodigd geheugen zou tot 19 TB kunnen oplopen).
  • De spaarse methodes kunnen schalen tot 1 miljoen kolommen.
• Praktische Toepassingen:
  • Aanbevelingssysteem: Een nearest-neighbors aanbevelingssysteem (Bookcrossing dataset) was onuitvoerbaar met dichte methodes door geheugenbeperkingen, maar werkte met de spaarse methode (gemiddeld 48 minuten).
  • Toegangscontrole: Een ML-model voor het detecteren van verdachte toegangspogingen (Amazon dataset) kon worden getraind. De covariantiematrix-berekening (een matrix-matrix vermenigvuldiging) was onmogelijk met dichte methodes, maar duurde 5 uur met de spaarse methode.

5. Betekenis en Conclusie

Dit werk is van groot belang voor de toekomst van Privacy-Preserving Machine Learning (PPML). Veel ML-toepassingen (zoals aanbevelingssystemen en bio-informatica) genereren van nature extreem spaarse data. Zonder deze specifieke optimaire algoritmes zijn deze toepassingen in een veilige MPC-omgeving onuitvoerbaar of onpraktisch traag.

De auteurs bewijzen dat:

1. Spaarse algoritmes niet alleen communicatiekosten drastisch verlagen, maar ook de enige haalbare route zijn voor grote datasets vanwege geheugenbeperkingen.
2. Het is mogelijk om veilige berekeningen uit te voeren zonder dat data-eigenaren hun exacte datastructuur hoeven te onthullen, mits gebruik wordt gemaakt van geavanceerde padding- en template-technieken.
3. De implementatie open-source beschikbaar is, waardoor deze technieken direct in bestaande MPC-frameworks geïntegreerd kunnen worden.

Samenvattend vult dit onderzoek een cruciale lacune in de MPC-literatuur op en maakt het privacy-bewuste ML op grote, real-world datasets mogelijk.