Berekeningen op vercijferde Data: van droom naar realiteit

Cet article est aussi disponible en français.

Kunnen we de verwerking van gevoelige gegevens uitbesteden aan een externe partij, zonder dat deze toegang krijgt tot deze gegevens en zonder vertrouwen te moeten leggen in gecertificeerde hardware? Dit is mogelijk dankzij Fully Homomorphic Encryption (FHE). Het laat toe om willekeurige berekeningen uit te voeren op vercijferde data, waarbij ook het resultaat opnieuw vercijferd is. Het beschermt zo wiskundig de confidentialiteit van data in use. Vandaag is FHE meestal nog te traag voor praktische toepassingen, maar er zijn redenen tot optimisme.

Evolutie

Het idee van FHE werd voor het eerst in 1978 geformuleerd. Dit is niet toevallig kort na de publicatie van RSA in 1977, wat tot op vandaag gebruikt wordt voor onder meer authenticatie en digitale handtekeningen. Encryptie met RSA is namelijk partieel homomorf, zoals geïllustreerd in figuur 1; de vermenigvuldiging van twee RSA-cijferteksten resulteert in de RSA-vercijfering van het product van de twee oorspronkelijke waarden.

Figuur 1. RSA is partieel homomorf

Gedurende ruim 30 jaar was het onduidelijk of FHE mogelijk was. Maar in 2009 kwam dan eindelijk de grote doorbraak. Craig Gentry (Stanfort University) slaagde er als eerste in een schema voor vercijfering te bedenken dat volledig homomorf was; het was mogelijk om zowel optellingen als vermenigvuldigingen op vercijferde data uit te voeren. Het voorstel was echter afschuwelijk traag. Veel te traag om in de praktijk bruikbaar te zijn.

Sindsdien wordt binnen de academische wereld en door een aantal innovatieve bedrijven hard aan de weg getimmerd om FHE efficiënter te maken. Daarbij worden algoritmes en de implementaties van die algoritmes verbeterd. Ook wordt gewerkt aan FHE hardware accelerators, al zijn die nog niet commercieel beschikbaar.

Toepassingen vandaag

Vandaag kent FHE nog een erg beperkt adoptie. Vier concrete toepassingen die van FHE gebruikmaken werden door uw auteur gedetecteerd.

Microsoft gebruikt het voor private information retrieval (PIR): De Microsoft Edge-browser vercijfert een hash van je wachtwoord en stuurt het naar een server die op een homomorfe wijze nagaat of het wachtwoord zich in een lijst van gecompromitteerde wachtwoorden bevindt. Het vercijferde resultaat (true of false) wordt teruggestuurd naar de Edge-browser die het resultaat ontcijfert. Je weet of je wachtwoord gecompromitteerd is, zonder dat wachtwoord aan de server prijs te geven.

Apple past FHE toe in een gelijkaardig scenario, zoals geïllustreerd in figuur 2: je wordt gebeld door een onbekend nummer. Je iPhone vercijfert het nummer en stuurt het naar een server. Die server doet een database lookup op vercijferde data en retourneert de vercijferde informatie over het nummer, zoals naam en eventueel een foto. De server komt nooit te weten wie je probeert te bellen.

Figuur 2. FHE door Apple: opvragen van informatie over onbekend nummer.

Een derde use case, geïllustreerd in figuur 3, komt eveneens van Apple. Een burger neemt met haar iPhone een foto van een Point of Interest (PoI), zoals het Atomium of de Eifeltoren. De iPhone berekent op basis hiervan een vector (een reeks getallen) die het PoI beschrijft, stuurt het vercijferd naar een server die met behulp van FHE de bijbehorende informatie over het PoI opzoekt en terugstuurt. De server komt dus nooit te weten waar je bent. Het verschil met de vorige use cases is dat hier approximatief gewerkt wordt: de op de iPhone berekende vector is niet steeds dezelfde voor eenzelfde PoI.

Figuur 3. FHE door Apple: opvragen informatie Point of Interest

De laatste use case situeert zich in de blockchain-wereld. Transacties op publieke blockchains zijn voor iedereen zichtbaar. Deze transparantie is een obstakel bij on-chain financiële transacties. De missie van het in Parijs gevestigde Zama is om bedragen en saldi vertrouwelijk te houden, terwijl volledige verifieerbaarheid en naleving van regelgeving gewaarborgd blijven. De op FHE gebaseerde oplossing van Zama werd in 2026 toegepast bij de distributie van zowel Zama als KAIO tokens. Tokens zijn hier activa die op een publieke blockchain verhandelbaar zijn.

Prototypes

In de toekomst kan een brede waaier aan toepassingen mogelijk worden. Dat die toekomst niet zo heel veraf meer is blijkt onder meer uit prototypes die reeds gebouwd werden.

  • Reeds in 2021 bouwde EPFL (École Polytechnique Fédérale de Lausanne) een prototype dat verschillende zorgverleners in staat stelt om gezamenlijk statistische analyses uit te voeren en modellen voor machine learning te ontwikkelen, zonder de onderliggende datasets uit te wisselen.
  • In een samenwerking met SWIFT bouwde Belfort Labs, een spin-off van de KU Leuven, een PoC die in real-time nagaat of een vercijferde banktransactie toegelaten is op basis van een sanctielijst.
  • Samen met LG Electronics en de New York University bouwde Belfort een PoC voor een recommendation engine die in ongeveer een halve seconde gepersonaliseerde reclame toont, zonder je persoonsgegevens te moeten prijsgeven.
  • Een van de grote use case is AI op vercijferde data. Belfort Labs lanceerde in juli een demo voor een encrypted image classifier, waarvan een screenshot in figuur 4. Een server ontvangt een vercijferde afbeelding en berekent in ongeveer 0,2 seconden de vercijferde categorie (boot, auto, kat, …). Daarbij wordt onderliggend gebruik gemaakt van een GPU.
Figuur 4. Resultaat van de image classifier demo van Belfort Labs
  • Het Amerikaanse bedrijf Duality slaagde er in een prototype voor een encrypted LLM te bouwen. Een client vercijfert eerst de user prompt of -query met behulp van FHE en stuurt de vercijferde query vervolgens naar een LLM. De LLM verwerkt de query zonder deze te ontcijferen, genereert een vercijferd antwoord en stuurt dit terug naar de client. Voorlopig wordt er enkel met kleinere LLM-modellen gewerkt.

FHE basisflow

De basisflow voor FHE wordt geïllustreerd in figuur 5. Gegevens worden vercijferd met een publieke sleutel. Het uitvoeren van berekeningen op vercijferde data – in ons voorbeeld de optelling – vereist een evaluatiesleutel. Er vindt dus – en dat is de technisch correcte term – een homomorfe evaluatie plaats van de optelling. Decryptie van het resultaat vereist een (geheime) private sleutel.

Elk van de vier grijze rechthoeken kan in principe een aparte entiteit voorstellen, al hoeft dit niet. Verschillende clients kunnen dus geëncrypteerde data aanleveren. Ook encryptie en decryptie kunnen door afzonderlijke clients gebeuren. De decrypterende client genereert voorafgaandelijk de drie sleutels, bezorgt de evaluatiesleutel aan de server, de publieke sleutel aan alle aanleverende clients en beschermt de private sleutel.

Figuur 5. Basisflow voor FHE

Encryptie is niet enkel mogelijk met de publieke sleutel, maar ook met de private sleutel. Dat is efficiënter en nuttig wanneer encryptie en decryptie door dezelfde client gebeuren. De private sleutel en de evaluatiesleutel worden ook wel de client sleutel en de server sleutel genoemd.

Schema’s en implementaties

Net zoals digitale handtekeningen en symmetrische encryptie is FHE een concept dat op verschillende manieren gerealiseerd kan worden. In cryptografie noemt men een dergelijke realisatie een schema, wat een verzameling van algoritmes is. Elk FHE-schema bevat algoritmes voor onder meer sleutelgeneratie, encryptie, homomorfe evaluatie en decryptie.

De voornaamste schema’s vandaag zijn TFHE, CKKS en BFV. Ze hebben uiteenlopende eigenschappen. Afhankelijk van de use case kies je voor het het ene of het andere schema. Over het algemeen is TFHE meer geschikt voor booleaanse logica en logica waarbij met (kleine) integers wordt gewerkt, terwijl CKKS en BFV werken met reële getallen en zich daardoor beter lenen tot data science en machine learning.

Al deze schema’s zijn bovendien gebaseerd op lattices. Dat zijn wiskundige ruimtes waarin problemen gedefinieerd worden die zowel voor klassieke als kwantumcomputers als moeilijk beschouwd worden. Anders gezegd: FHE is kwantumveilig.

Een schema is een formele, wiskundige beschrijving van de stappen die de verschillende algoritmes dienen te doorlopen. Voor uitvoerbare code is een implementatie van het schema nodig.

TFHE is vandaag het schema met de meest volwassen implementaties, zoals TFHE-rs, wat in RUST geschreven is. OpenFHE is een C++ library die implementaties aanbiedt voor verschillende FHE-schema’s, waaronder de drie eerder genoemde. Lattigo biedt dan weer implementaties aan van onder meer CKKS en BFV in Go. Google, Microsoft en Apple hebben met HEIR, SEAL en Swift elk hun eigen open-source FHE-implementatie. Alle vermelde implementaties hebben een erg actieve ontwikkelcommunity.

Beloftevolle schema’s zoals GBFV en FINAL hebben vandaag enkel experimentele implementaties.

Bootstrapping

Bij elke operatie op vercijferde data wordt onbedoeld maar onvermijdelijk extra ruis aan de cijfertekst toegevoegd. Te veel ruis maakt de cijfertekst op den duur onbruikbaar: de waarde die we bekomen na decryptie verliest dan alle nauwkeurigheid en wordt dus waardeloos.

Bootstrapping is een procedure waarbij op basis van de oude cijfertekst met veel ruis een nieuwe cijfertekst met minder ruis gegenereerd wordt. Bootstrapping dient geregeld herhaald te worden. In TFHE wordt dit automatisch na elke homomorfe evaluatie uitgevoerd. In schema’s zoals CKKS wordt bootstrapping dan weer expliciet en enkel wanneer nodig uitgevoerd.

Bootstrapping is de meest computationeel intensieve component in FHE. Het hoeft dan ook niet te verbazen dat heel wat effort gestoken wordt om dit te verbeteren. En met succes! Jaar na jaar wordt bootstrapping efficiënter, en dat aan een tempo dat beduidend hoger ligt dan volgens de wet van Moore.

Performantie

Smals Research deed enkele performantietesten op basis van TFHE op een virtuele machine met 16 vCPU’s (virtuele CPU’s, in ons geval threads op een Intel Xeon 6) en 32GB RAM. De default TFHE-parameters werden gebruikt. De resultaten in seconden zijn te zien in tabel 1. Daarbij kunnen één of beide integer inputwaardes FHE-vercijferd zijn.

OperatieCijfertekst-cijfertekstCijfertekst-klaartekst
Vermenigvuldiging11514
Optelling1413
Xor42
Bit shift294
Minimum2211
Tabel 1. Uitvoeringstijden (sec.) van berekeningen op vercijferde integers. In de eerste kolom zijn beide inputs vercijferd, in de tweede kolom slechts één.

De sleutelgeneratie, integer-encryptie en integer-decryptie duurden 4400ms, 6ms en minder dan 1 ms. Encryptie gebeurde met de private sleutel. De voornaamste flessenhals is dus het uitvoeren van de berekeningen op de vercijferde data. Er zijn weliswaar toepassingsspecifieke optimalisaties mogelijk, bijvoorbeeld voor AES-encryptie, maar dat schaalt niet bijzonder goed.

Gelukkig wordt jaar na jaar vooruitgang geboekt op zowel het niveau van het algoritme, als de implementatie van die algoritmes. Daarbij gaat, zoals reeds vermeld, veel aandacht naar snellere bootstrapping. Toch zijn er limieten.

Vandaar dat bedrijven zoals Duality, Niobium, Belfort Labs, Zama, Hovera en Xiphera bouwen aan hardware accelerators. Het doel van deze bedrijven is om FHE voldoende snel (en praktisch) te maken voor real-time toepassingen. De huidige hardware accelerators maken het uitvoeren van berekeningen op vercijferde data meer dan 10 keer sneller. Afhankelijk van de toepassing kan dit vandaag al een pak meer zijn. Deze hardware accelerators zijn gebaseerd op FPGA’s (programmeerbare hardware) of GPU’s.

Ondertussen worden hardware accelerators ontworpen gebaseerd op ASIC’s. Dat is dus hardware specifiek ontwikkeld voor FHE. Men verwacht versnellingen van meerdere grootteordes. Een prototype van Heracles-chip van Intel leverde recent een versnelling met een factor 5000 op ten opzichte van een uitvoering op een Intel Xeon-processor met 24 cores (=48 threads). Dergelijke ASIC’s zullen binnen enkele jaren, misschien zelfs maanden, commercieel beschikbaar zijn. Niobium staat hier bijvoorbeeld al erg ver mee en mikt op 2027.

Het is redelijk om aan te nemen dat wanneer snelle hardware accelerators commercieel beschikbaar worden aan competitieve prijzen, FHE een bredere adoptie zal kennen.

Uitdagingen

Naast uitvoeringssnelheid zijn er nog een aantal andere uitdagingen:

  • Grootte. FHE-cijferteksten exploderen in grootte en kunnen duizenden malen groter zijn dat de originele klaartekst. Ook evaluatiesleutels zijn – afhankelijk van het schema – al snel honderd MB of zelfs meerdere GB groot. Deze uitdaging wordt besproken in een volgend artikel.
  • Complexiteit. Het ontwikkelen van een toepassing die gebruik maakt van FHE is vandaag complex. Het kan niet de bedoeling zijn dat daarvoor een doctoraat in de cryptografie vereist is. Men werkt gelukkig aan abstractielagen. TFHE-concrete laat toe om bestaande Python-functies uit te voeren op met FHE vercijferde data. Daarbovenop werd Concrete-ML ontwikkeld, voor privay-vriendelijke machine learning. Belfort Labs lanceerde recent eML (encrypted machine learning), waarmee een model in PyTorch – een deep learning library – omgezet kan worden naar het met FHE vercijferde domein.5
  • Integriteit. In klassieke FHE gaan we ervan uit dat de server eerlijk maar nieuwsgierig is (honest but curious): de server doet wat van hem wordt verwacht. We hebben helaas geen garantie dat de server de correcte logica op de met FHE vercijferde data toepast. We hebben evenmin garanties dat daarbij de juiste input gebruikt wordt. Dit tracht men op te lossen met Verifiable Fully Homomorphic Encryption (vFHE). De client krijgt niet enkel het met FHE vercijferde resultaat van de server, maar ook een correctheidsbewijs. vFHE bevindt zich vandaag nog in de onderzoeksfase. Generatie, transfer en verificatie van het bewijs hebben een significante computationele en communicatie-overhead.
  • Samenwerking. FHE leent zich uitstekend tot samenwerking waarbij meerdere partijen met FHE vercijferde data aanleveren en slechts één partij het resultaat van de berekeningen hoeft te decrypteren. Alle aanleverende partijen encrypteren daarbij hun data met de publieke sleutel van de decrypterende partij, de server werkt met de evaluatiesleutel van de decrypterende partij.
    Het wordt uitdagender wanneer verschillende partijen werken met hun eigen sleutels. Stel dat verschillende banken willen samenwerken bij het trainen van een AI-model. Aangezien het om gevoelige gegevens gaat, gebeurt alles in het vercijferde domain, dus met behulp van FHE. Elke bank heeft zijn eigen publieke en private sleutel en bezorgt zijn evaluatiesleutel aan de server. In dit scenario worden meerdere publieke sleutels, private sleutels en evaluatiesleutels gebruikt.
    Dit is een uitdagender scenario dan daarnet en is een voorbeeld van multi-party FHE. Dit is computationeel intensiever dan klassieke FHE. Er wordt volop onderzoek naar verricht, maar ondersteuning is alvast aanwezig in libraries zoals Lattigo.

Confidential computing

Voor de bescherming van de confidentialiteit van data at rest en data in transit hebben we al jaren gestandaardiseerde oplossingen. Het beschermen van de confidentialiteit van data in use bleek lastiger, al is er de laatste jaren stevig aan de weg getimmerd. Momenteel zijn er drie benaderingen:

  • Fully homomorphic Encryption (FHE). Een centrale partij voert berekeningen uit op de aangeleverde vercijferde data.
  • Multi-party computation (MPC). Meerdere partijen voeren samen berekeningen uit, waarbij geen informatie over individuele inputs lekt naar andere partijen. De data blijven bij de bron. Enkel het resultaat van de berekeningen wordt zichtbaar voor één of meerdere partijen. Een voorbeeld uit 1982 – MPC is inderdaad al zo oud – illustreert dit. Een groep miljonairs gaan op restaurant en spreken af dat de rijkste de rekening betaalt. Niemand wil echter zijn exacte rijkdom prijsgeven. De miljonairs doen daarom beroep op MPC.
  • Trusted execution environments (TEE‘s‘). Vercijferde data wordt bezorgd aan een centrale partij en wordt er enkel gedecrypteerd in een veilige hardware-module, waartoe in principe zelfs de beheerder van de machine geen toegang heeft.

TEE is de meest praktische van de drie. TEE’s worden breed ondersteund en bestaande code kan in TEE’s uitgevoerd worden. Weliswaar wordt het als de minder veilige benadering beschouwd, aangezien de data zich wel degelijk onvercijferd in de TEE bevinden en onderzoekers geregeld aanvallen vinden waardoor alsnog informatie kan lekken. Niettemin blijft het absoluut een zeer waardevolle extra beschermingslaag in cloudinfrastructuren.

MPC is gedistribueerd, vereist geen speciale hardware, maar gaat gepaard met significante communicatie overhead. Het opzetten en uitvoeren van MPC-protocollen kan bovendien vrij complex worden.

FHE is door de gecentraliseerde aanpak eenvoudiger op te zetten dan MPC, maar heeft als nadeel dat het computationeel erg zwaar is, zoals eerder in dit artikel reeds besproken. Zowel TEE als FHE doen een beroep op hardware, maar anders dan bij TEE is er geen vertrouwen nodig in die hardware. FHE staat momenteel dichter bij standaardisatie (door NIST en ISO) dan MPC, wat adoptie stimuleert.

Conclusies

FHE is een van de drie benaderingen voor confidential computing. De technologie is in volle ontwikkeling, en kent toenemende belangstelling bij wetenschappers, standaardisatie-instanties, investeerders en de commerciële sector. Bovendien wordt FHE als kwantumveilig beschouwd. Binnenkort verwachten we dan ook een uptake van de technologie, ondersteund door hardware accelerators.

Smals Research investeert in deze technologie, door middel van experimenten, proof-of concepts en een permanente opvolging van de evoluties. Meer algemeen bouwt Smals Research expertise uit in elk van de drie benaderingen voor confidential computing (FHE, TEE en MPC). Dit stelt ons in staat onderbouwd advies te geven aan onze leden en om de juiste keuzes te maken.

Smals Research biedt de leden van Smals ondersteuning bij innovatie. Aarzel niet contact met ons op te nemen bij interesse.


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.

Featured image by Tom Magliery, published under Creative Commons

_________________________

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


More posts