Menu
Voor zover men weet, bestaat het idee dat homomorfe encryptie gebruikt kan worden voor het beschermen van data al decennia3. Het probleem van het vormen van een volledig homomorfe encryptie, werd voor het eerste voorgesteld in 19784. Er werden speciale encryptie functies genaamd “privacy homomorphisms” voorgesteld. De auteurs bespreken het gebruiken van hardware om data veilig te verwerken. De data zouden dan alleen ontcijferd worden op een fysiek veilige processor. Op deze manier wordt de data altijd versleuteld wanneer het de processor verlaat (bv. wanneer het naar het geheugen wordt verplaatst). Het probleem met deze soort chips, is dat het op maat gemaakte hardware is, duur om te implementeren en altijd nog een decoderingssleutel nodig heeft. Voor meer dan 30 jaar was het onduidelijk of er een oplossing bestond voor dit probleem. In die periode zijn er een aantal gedeeltelijke oplossingen verschenen1:
Craig Gentry beschreef de eerste plausibele constructie voor een volledig homomorfe encryptie met behulp van op roosters gebaseerd cryptografie* 1,5. Gentry’s constructie ondersteunt zowel optel- als vermenigvuldigingsbewerkingen op versleutelde teksten, van waaruit het mogelijk is om schakelingen te maken voor het uitvoeren van willekeurige berekeningen. De constructie volgt een aantal stappen waarin eerst ruis** wordt geïntroduceerd en vervolgens wordt gereduceerd. Hierdoor is het mogelijk om een willekeurig aantal optellingen en vermenigvuldigen te berekenen zonder de ruis te veel te verhogen. De Gentry-Halevi implementatie van Gentry’s originele cryptosysteem rapporteerde een timing van ongeveer 30 minuten per simpele bit operatie6. Uitgebreide ontwerp- en implementatiewerkzaamheden in de daaropvolgende jaren, hebben de runtime-prestaties van deze vroege implementaties met vele ordes van grootte verbeterd.
In 2010 presenteerde Marten van Dijk, Craig Gentry, Shai Halevi en Vinod Vaikuntanathan7 een tweede volledig homomorf encryptieschema, wat veel van de tools van Gentry’s constructie gebruikt.
* Zie voor een goede uitleg van op roosters gebaseerde cryptografie de Wikipediapagina ‘Lattice-based cryptography’.
** Door de cryptografische bewerkingen bevat elke cijfertekst een hoeveelheid ruis1. Deze ruis groeit wanneer cijferteksten bij elkaar opgeteld of met elkaar vermenigvuldigd worden, totdat de ruis de cijfertekst uiteindelijk niet meer ontcijferbaar maakt.
De homomorfe cryptosystemen die momenteel worden gebruikt, zijn afgeleid van technieken die vanaf 2011-2012 zijn ontwikkeld door Zvika Brakerski, Craig Gentry, Vinod Vaikuntanathan en anderen1. Deze innovaties leidden tot de ontwikkeling van veel efficiëntere enigszins en volledig homomorfe cryptosystemen. Deze omvatten:
De beveiliging van de meeste van deze schema’s, is gebaseerd op de hardheid van het (Ring) Leren Met Fouten (Engels: Ring Learning With Errors of RLWE) probleem. Behalve de LTV- en BLLN-schema’s, want die vertrouwen op een overbelaste14 variant van het NTRU-rekenprobleem*** 15. Deze NTRU-variant bleek vervolgens kwetsbaar te zijn voor sub-veldroosteraanvallen, en daarom worden deze twee schema’s in de praktijk niet meer gebruikt.
Alle cryptosystemen van de tweede generatie volgen nog steeds de basisblauwdruk van de oorspronkelijke constructie van Gentry. Ze construeren namelijk eerst een ietwat homomorf cryptosysteem en converteren het vervolgens naar een volledig homomorf cryptosysteem met behulp van ‘bootstrapping’.
Een onderscheidend kenmerk van de tweede generatie cryptosystemen is dat ze allemaal een veel langzamere groei van de ruis vertonen tijdens de homomorfe edit-berekeningen. Een ander kenmerk is dat ze efficiënt genoeg zijn voor veel toepassingen, zelfs zonder ‘bootstrapping’ aan te roepen, in plaats daarvan opereren ze in de ‘leveled’ FHE-modus.
*** NTRU is een open source public-key cryptosysteem wat op roosters gebaseerde cryptografie gebruikt om gegevens te coderen en decoderen16.
In 2013 stelden Craig Gentry, Amit Sahai en Brent Waters (GSW) een nieuwe techniek voor, voor het bouwen van FHE-schema’s die een dure stap van ‘relinearisering’ bij homomorfe vermenigvuldigingen vermijden17. Zvika Brakerski en Vinod Vaikuntanathan merkten op dat het GSW-cryptosysteem, voor bepaalde typen schakelingen, een nog langzamere groeisnelheid van ruis vertoont18. Dit geeft dus een betere efficiëntie en sterkere beveiliging. Jacob Alperin-Sheriff en Chris Peikert beschreven vervolgens een zeer efficiënte ‘bootstrapping’-techniek op basis van deze observatie19.
Deze technieken werden verder verbeterd om efficiënte ringvarianten van het GSW-cryptosysteem te ontwikkelen. Hier kwamen het FHEW-20 en TFHE-schema21 uit voort. Het FHEW-schema was het eerste wat aantoonde dat door de versleutelde teksten na elke bewerking te vernieuwen, het mogelijk is om de ‘bootstrapping’-tijd terug te brengen tot een fractie van een seconde. FHEW introduceerde een nieuwe methode om Booleaanse poorten op versleutelde gegevens te berekenen. Hiermee werd ‘bootstrapping’ aanzienlijk vereenvoudigt en werd een variant van de ‘bootstrapping’-methode geïmplementeerd19. De efficiëntie van FHEW werd verder verbeterd door het TFHE-schema, wat een ringvariant van de ‘bootstrapping’-procedure22 implementeert met behulp van een methode die vergelijkbaar is met die in FHEW.
Het CKKS-schema23 ondersteunt efficiënte afrondings-bewerkingen in versleutelde toestand1. De afrondings-bewerking regelt de toename van de ruis bij gecodeerde vermenigvuldiging, waardoor het aantal ‘bootstrapping’ in een schakeling wordt verminderd. In Crypto2018 is op CKKS gefocust als een oplossing voor versleutelde machine learning. Dit komt door een kenmerk van het CKKS-schema dat geschatte waarden codeert in plaats van exacte waarden. Wanneer computers gegevens met een reële waarde opslaan, onthouden ze waarden bij benadering met lange significante bits, niet exact met werkelijke waarden. Het CKKS-schema is ontworpen om efficiënt om te gaan met de fouten die voortvloeien uit de benaderingen. Het schema is bekend bij machine learning, wat inherent ruis in zijn structuur heeft. Ieder schema heeft zo zijn sterke en zwakke punten.
Doordat CKKS met afgeronde waarden werkt, in plaats van exacte is het mogelijk dat hierdoor kwetsbaarheden ontstaan. Een artikel uit 2021 van Baiyu Li en Daniele Micciancio bespreekt passieve aanvallen tegen CKKS24. De auteurs passen de aanval toe op vier moderne homomorfe encryptie libraries (HEAAN, SEAL, HElib en PALISADE) en melden dat het mogelijk is om de geheime sleutel te herstellen in verschillende parameter-configuraties. Volgens het artikel zou een mogelijke beperking, het bijwerken van het encryptiealgoritme van CKKS vereisen om te voorkomen dat de encryptieruis van een versleutelde tekst wordt achterhaald.
