Secure multiparty computation – Collectieve berekeningen op verspreide gevoelige gegevens

Posted on: 08/06/2021 by: Kristof Verslype

Binnen de cryptografie is er een stelling die zegt dat alles wat met behulp van een centrale partij (Facebook, Amazon, de overheid, … ) mogelijk is, ook zonder die centrale partij mogelijk is. Daarbij kunnen confidentiële gegevens – zoals persoonsgegevens – die als input dienen toch confidentieel blijven voor de andere participanten. De technologie bij uitstek die dit – althans in theorie – mogelijk maakt is secure multiparty computation (SMC) en werd voor het eerst voorgesteld door Andrew Yao, reeds in 1982.

Yao gaf toen het volgende voorbeeld. Twee miljonairs – vandaag zouden we eerder spreken over miljardairs – willen weten wie de rijkste is, zonder hun exacte rijkdom of zelfs maar indicaties van hun vermogen aan de andere of aan een derde partij prijs te geven. Beide partijen willen dus weten of wealth1 < wealth2 waar of fout is, zonder dat er voor de rest informatie lekt, dus zonder dat de ene miljonair verdere informatie over wealth1 prijsgeeft en zonder dat de ander verdere informatie over wealth2 prijsgeeft.

Lange tijd bleef SMC een louter academische aangelegenheid met enkel toy-examples zoals hierboven. Het was (en is) immers erg moeilijk om SMC in de praktijk te brengen, onder meer door de dramatische impact op de efficiëntie en de intensieve communicatie tussen de betrokken partijen. 

Ondertussen zijn we ongeveer 40 jaar verder en is er heel wat onderzoek verricht rond SMC – het blijft trouwens een zeer actief onderzoeksdomein -, waarbij protocollen ontwikkeld werden die efficiënter zijn, die andere veiligheidseigenschappen hebben, die drie of meer partijen toelaten, etc. Daardoor duiken hier en daar – zij het momenteel nog in beperkte mate – praktische SMC toepassingen op.  Toch blijft de generieke SMC technologie in vele gevallen weinig praktisch.

Daarom werden en worden specifiekere protocollen ontwikkeld zoals oblivious transfer, wat toelaat dat een partij een specifiek record uit een lijst opvraagt bij een andere partij, zonder dat die laatste te weten komt het welke. Een ander voorbeeld is private set intersection (PSI), waarbij een partij te weten komt over welke items (vb. burgers of ondernemingen) een andere partij eveneens een dossier heeft, waarbij er verder geen data lekt. Ook onze eigen oblivious join, om data afkomstig van meerdere bronnen voor onderzoeksdoeleinde te kruisen, is zo’n specifiek protocol. In de wereld van de cryptografie slaat SMC doorgaans enkel op de generieke technologie, al merken we dat daarbuiten ook dergelijke specifieke protocollen onder de SMC vlag geplaatst worden.

In de praktijk

SMC wordt hier en daar reeds in de praktijk gebruikt, zoals blijkt uit de drie onderstaande cases.

De bekendste en misschien ook de eerste reële toepassing van (generieke) SMC wordt al sinds 2008 gebruikt en wordt geregeld ingezet voor Deense suikerveilingen. Het is een dubbele veiling, waarbij zowel kopers als verkopers bieden. De veiling, die zonder centrale partij verloopt, moest voldoen aan strikte privacy vereisten, waarbij de biedingen voor altijd confidentieel blijven. De veiling wordt uitgevoerd als een 3-party SMC tussen 1) vertegenwoordigers van Danisco, de enige suikerbietenverwerker in Denemarken, 2) de boerenvereniging (DKS) en 3) de onderzoekers (SIMAP).

Ons tweede voorbeeld is Sharemind. Het wordt commercieel aangeboden en gebruikt SMC voor analyses op gevoelige gegevens afkomstig van verschillende partijen. Die partijen kappen elk afzonderlijk hun data in stukjes die afzonderlijk geen informatie bevatten en uploaden een derde van de stukjes data naar elk van drie verschillende servers. Dit gebeurt op zo’n manier dat de data confidentieel blijft voor de individuele servers, weliswaar onder de veronderstelling dat deze niet samenspannen. Om een query uit te voeren, zullen de drie partijen en de vraagsteller met elkaar interageren (het SMC protocol), waarbij de vraagsteller – en enkel de vraagsteller – toegang krijgt tot het uiteindelijk resultaat door de antwoorden van de drie servers te combineren. Om de efficiëntie en governance te verbeteren, wordt Sharemind ook aangeboden in één enkele appliance, waarbij gebruik gemaakt wordt van hardware (Intel SGX) om de drie zones van elkaar te scheiden. Sharemind heeft zijn eigen taal voor het doen van analyses. We geven ook nog mee dat Sharmind heel wat verschillende cryptografische bouwstenen combineert

graphic

Unbound is ons derde voorbeeld. Het lost met SMC het probleem op van de gecompromitteerde sleutel. De veiligheid van cryptografische operaties (encryptie, decryptie, ondertekenen, …) steunt immers op de veronderstelling dat de geheime/private sleutel ook effectief geheim/privaat blijft. In de praktijk is dit niet steeds even vanzelfsprekend. Unbound reikt een oplossing aan waarbij de sleutel opgesplitst is in twee deeltjes die door verschillende partijen bewaard worden. Wanneer een deeltje gecompromitteerd is, kan de hacker daar nog steeds niets mee aanvangen. Dit verhoogt aanzienlijk de veiligheid, maar impliceert wel dat een cryptografische operatie enkel mogelijk is met medewerking van de partij die het andere deel van de sleutel heeft. De cryptografische operaties worden uitgevoerd m.b.v. SMC waarbij de twee sleuteldeeltjes nooit samenkomen. Unbound biedt in zijn producten ondersteuning voor zowel symmetrische (AES) als publieke sleutelcryptografie (vb. RSA).

Ten slotte kan SMC gebruikt worden voor veilige machine learning, maar daarover meer in een toekomstige blogpost.

Initiatieven in overheidscontext (NL)

Recentelijk zien we hier en daar proof-of-concepts en piloten opduiken in overheidscontext. Nederland zet duidelijk in op SMC in zijn meer algemene definitie waarin dus ook meer specifieke protocollen vervat liggen. Uit een recent en inspirerend rapport van het Nederlands TNO (Nederlandse Organisatie voor Toegepast Natuurwetenschappelijk Onderzoek ) blijkt alvast dat ze heel wat potentieel zien binnen overheidscontext:

Er zijn ontzettend veel toepassingsmogelijkheden voor privacyverbeterende technieken zoals MPC en FL [Federated Learning]. Zo kan de effectiviteit van de zorg vergroot worden door op een privacy vriendelijke manier inzichten uit patiëntdata te verkrijgen. De groeiende financiële criminaliteit kan ingedamd worden door het veilig koppelen van gevoelige data van verschillende financiële organisaties. Daarnaast kan de overheid haar dienstverlening verbeteren door privacy respecterende samenwerkingen tussen verschillende overheidsinstanties.

We blijven even stilstaan bij een case uit de Nederlandse overheidscontext waarover we toch wat – zij het beperkt – technische informatie konden vinden. In Nederland vormt de AOW uitkering een basispensioen. Indien dit onder het bestaansminimum valt, hebben gepensioneerden recht op een aanvulling (de AIO). 34.000 (48%) tot 50.000 (56%) van de huishoudens met een inkomen onder het bestaansminimum maakt hier geen gebruik van. De SVB, de instelling verantwoordelijk voor die AOW, heeft geen toegang tot gegevens over sociale uitkeringen en pensioenen (gekend door het UWV) en kan dus niet nagaan wie er AOW-gerechtigd is. Dit tracht men in Nederland in een piloot op te lossen m.b.v. homomorfe encryptie (zie verder) om te komen tot een SMC protocol. Toch lijkt het op basis van de beschikbare informatie voor uw nederige auteur logischer om in dit geval gebruik te maken van de eerder vermeldde private set intersection (PSI).

Ook in Belgische overheidscontext schuilt er ongetwijfeld heel wat potentieel. Smals Research wil dit samen met u wil ontginnen. Aarzel daarom niet contact met ons op te nemen.

We vermelden ook graag dat de COSIC groep aan de KU Leuven wereldwijd aan de top staat wat betreft SMC onderzoek. Dit onderzoek resulteerde in een uitgebreide, door hen ontwikkelde library die SCALE-MAMBA gedoopt werd. Een ander veelbelovend COSIC project is JANA:

Jana aims to provide practical private data as a service to protect subject privacy while retaining data utility to analysts. 

Relatie tot andere technologieën

SMC laat toe om zonder centrale partij, dus gedistribueerd berekeningen te doen. Wat is dan het verschil met blockchain-technologie? In een klassieke blockchainbenadering, wordt alle input nodig voor de berekeningen op de blockchain geplaatst en dus gedeeld met andere participanten in het blockchain netwerk. Die participanten doen vervolgens allen exact dezelfde berekeningen op die data. Gegeven dit basisprincipe is het niet altijd makkelijk om een blockchain benadering te verzoenen met strenge privacyvereisten. Bij SMC, daarentegen, staan confidentialiteit en privacy centraal. Blockchaintechnologie blinkt wel uit om informatie onweerlegbaar en zonder centrale partij zaken te registreren. Het sleutel(werk)woord bij MPC is berekenen, het sleutelwoord bij blockchain is registreren.

Homomorfe encryptie (HE) is een cryptografische techniek om berekeningen op een veilige manier te outsourcen naar een centrale partij, en is daarmee op functioneel vlak een alternatief voor SMC. HE laat toe dat een centrale partij berekeningen doet op data zonder toegang te krijgen tot die data zelf. De centrale partij doet daarbij berekeningen op de vercijferde gegevens, waarbij het resultaat opnieuw een cijfertekst is. Bijvoorbeeld enc(5) * enc (3) = enc(15). De centrale partij doet in dit geval een vermenigvuldiging, maar het komt noch de waarden 5 en 3 (input) noch de waarde 15 (output) te weten.

Homomorfe encryptie ondersteunt, net zoals SMC, dezelfde berekeningen als een klassieke computer (de Turingmachine). In dat geval speken we van full homomorphic encryption (FHE), waarvoor een eerste concrete schema pas relatief recent – in 2009 – voorgesteld werd. FHE is weliswaar een pak minder efficiënt en daardoor –  veel meer nog dan SMC – een theoretisch gegeven. In het boekA Pragmatic Introduction to Secure Multi-Party Computation” uit 2017 schrijven de auteurs:

Hoewel er recent veel belangstelling is geweest voor het implementeren van FHE-schema’s […] blijft het bouwen van veilige, inzetbare, schaalbare systemen met FHE een ongrijpbaar doel. [..] State-of-the-art FHE-implementaties zijn duizenden keren langzamer dan two-party en multi-party secure computation in typische toepassingen en instellingen die in de literatuur worden overwogen.

Toch mogen we niet vergeten dat beperktere vormen van HE onmisbaar zijn in de cryptografie ter ondersteuning van andere cryptografische bouwblokken zoals…  bepaalde SMC protocollen! 

We geven ten slotte nog mee dat sommige generieke SMC protocollen onder meer gebruik maken van vormen van het reeds aangehaalde oblivious transfer. 

Conclusie

SMC was lange tijd een eerder academisch curiosum, maar ondertussen hebben de eerste concrete toepassingen reeds het licht gezien. We bevinden ons weliswaar nog in een vroeg stadium om SMC in de praktijk te brengen.

Toch lijkt er heel wat potentieel in te zitten de technologie. Het is echter niet steeds eenvoudig om de juiste technologie te selecteren. Er zijn verschillende generieke SMC protocollen, en er zijn talrijke voorstellen voor meer specifieke SMC protocollen. COSIC biedt alvast ondersteuning bij het selecteren van een generiek SMC raamwerk.

We kijken in elk geval al uit naar uw suggesties om samen met u een concrete overheidscase uit te werken.


Dit is een ingezonden bijdrage van Kristof Verslype, cryptograaf bij Smals Research. Het werd geschreven in eigen naam en neemt geen standpunt in namens Smals.