Modification to Fully Homomorphic Modified Rivest Scheme

Dit document beschrijft de Fully Homomorphic Modified Rivest Scheme (FHMRS), identificeert een beveiligingsprobleem daarin, en presenteert een aangepaste versie (mFHMRS) om dit probleem te ondervangen.

De kern

Hier is een uitleg van het paper over de FHMRS en de verbeterde mFHMRS, vertaald naar eenvoudig Nederlands met behulp van creatieve analogieën.

🏰 Het Grote Geheim: Rekenen in de Verborgenheid

Stel je voor dat je een heel waardevol geheim (je data) hebt, maar je wilt dat een vreemde (een cloudserver) erop rekent zonder dat die vreemde ooit weet wat het geheim is. Dat is wat Fully Homomorphic Encryption (FHE) doet. Het is alsof je een slotje op je data zet, de vreemde mag erop tikken en duwen (rekenen), en als je het slotje weer opent, is het resultaat van die berekening correct, terwijl de vreemde nooit wist wat erin zat.

Dit paper beschrijft een nieuw soort slotje, gebaseerd op een oude idee van Rivest, maar dan verbeterd.

---

1. Het Oude Slotje: FHMRS (De "Twee Deuren" Methode)

Het originele systeem (FHMRS) werkt als een slimme twee-deurs kluiskamer.

• Hoe het werkt: Je neemt je geheim (bijvoorbeeld een getal) en stopt het in een envelop. Je voegt een willekeurig aantal "versteuringsmoleculen" (een willekeurig getal vermenigvuldigd met een geheim getal $u$) toe.
• De twee deuren: Je maakt twee kopieën van deze envelop.
  • De ene kopie wordt door een deur genaamd $p$ gekeken.
  • De andere door een deur genaamd $q$.
  • De deuren zijn zo groot dat ze de envelop precies passen, maar niet groter.
• Rekenen: Als iemand in de kamer (de server) twee enveloppen bij elkaar moet optellen of vermenigvuldigen, doet hij dat gewoon met de kopieën. Omdat de deuren ($p$ en $q$) groot genoeg zijn, "breken" ze niet onder het gewicht van de berekening.
• Openen: Om het resultaat te zien, gebruik je de sleutels ($p$, $q$ en $u$) om de twee kopieën weer samen te voegen (een wiskundige truc genaamd Chinese Remainder Theorem). De "versteuringsmoleculen" vallen er dan uit en je houdt je originele antwoord over.

Het probleem:
Het paper laat zien dat dit oude slotje een zwakke plek had. Als een hacker wist wat er in de envelop zat (bijvoorbeeld omdat je een berichtje stuurde met de tekst "Hallo" en zag wat het resultaat was), kon hij twee enveloppen vergelijken. Door de verschillen te bekijken, kon hij de sleutel $u$ achterhalen. Het was alsof je twee identieke dozen zag en door de kieren te meten, de sleutel van het slot kon raden.

---

2. De Nieuwe Uitvinding: mFHMRS (De "Meer Deuren" Methode)

Om dit probleem op te lossen, hebben de auteurs het systeem mFHMRS (Modified FHMRS) bedacht. Ze hebben het oude systeem flink aangepakt.

De Analogie: Van Twee naar Veel Deuren

In plaats van slechts twee deuren ($p$ en $q$), gebruiken ze nu veel deuren ($p_1, p_2, ..., p_{N+S}$).

• Meer veiligheid: Stel je voor dat je je geheim niet in twee kopieën stopt, maar in 10 of 20 verschillende kopieën, elk door een andere deur gekeken.
• De "Versteuringsmoleculen" (Randomness): Ze maken de willekeurige getallen ($g$) die aan het geheim worden toegevoegd, veel groter en onvoorspelbaarder.
• Het resultaat: Als een hacker nu probeert de oude truc te doen (twee enveloppen vergelijken om de sleutel te vinden), werkt het niet meer. De extra deuren en de grotere willekeurige getallen zorgen ervoor dat de "kieren" te klein zijn om de sleutel door te meten. Zelfs als de hacker weet wat er in de envelop zat, kan hij de sleutels niet afleiden.

---

3. Waarom is dit veilig? (De "Labyrint" Analogie)

Het paper bespreekt verschillende manieren waarop hackers proberen te kraken, en waarom mFHMRS ze stopt:

1. Gokken (Brute Force):

   • Analogie: Een hacker probeert elke mogelijke sleutel uit een enorme kast.
   • Waarom het faalt: De kast is zo enorm groot (de getallen zijn gigantisch, met honderden cijfers) dat het duizenden jaren duurt om ze allemaal te proberen. Het is als zoeken naar één specifiek zandkorreltje in alle stranden van de wereld.

2. Lattice-aanvallen (Het "Gordijn" probleem):

   • Analogie: Hacker probeert een patroon te zien in een gordijn van draden (wiskundige roosters) om de vorm van de sleutel te raden.
   • Waarom het faalt: De auteurs hebben de draden zo geplaatst dat het gordijn eruitziet als een wirwar van ruis. Er is geen duidelijk patroon te zien, zelfs niet met de krachtigste wiskundige brillen. De "ruis" (de willekeurige getallen) is groter dan de "patronen" die de hacker zoekt.

3. Lineaire vergelijkingen (Het "Puzzel" probleem):

   • Analogie: Hacker probeert een vergelijking op te lossen: "Als ik dit weet en dat weet, dan is de sleutel X".
   • Waarom het faalt: Omdat de willekeurige getallen ($g$) zo groot en onvoorspelbaar zijn, zijn er te veel mogelijke oplossingen voor de vergelijking. Het is alsof je een vergelijking probeert op te lossen met 100 onbekende variabelen; je raakt de sleutel nooit.

---

4. Samenvatting in Eenvoudige Woorden

• Het doel: Mensen kunnen data in de cloud laten verwerken zonder dat de cloudprovider weet wat de data is.
• Het oude probleem: Het oude systeem was kwetsbaar als de hacker wist wat de ingang was (Known Plaintext Attack). Hij kon dan de sleutel achterhalen.
• De oplossing: Het nieuwe systeem (mFHMRS) gebruikt meer deuren (meer priemgetallen) en grotere willekeurige getallen.
• Het resultaat: Zelfs als de hacker weet wat er in de envelop zit, kan hij de sleutel niet achterhalen. Het is alsof je een raadsel oplost, maar de antwoorden zijn zo verward met ruis dat het raadsel onoplosbaar wordt voor de hacker.

Kortom: De auteurs hebben een oude, kwetsbare sleutel vervangen door een super-sterke, meervoudige sleutel die zelfs slimme hackers niet kan kraken, terwijl het voor de gebruiker nog steeds werkt als een gewone rekenmachine.

Technische samenvatting

Hier is een gedetailleerde technische samenvatting van het paper "Modification to Fully Homomorphic Modified Rivest Scheme" in het Nederlands.

Titel: Aanpassing van het Volledig Homomorf Gewijzigd Rivest-schema (FHMRS)

Auteurs: Sona Alex en Bian Yang (NTNU, Noorwegen)

---

1. Het Probleem

Het paper adresseert een fundamentele beveiligingskwetsbaarheid in het bestaande Fully Homomorphic Modified Rivest Scheme (FHMRS). FHMRS is een symmetrisch sleutel-cryptosysteem dat homomorfische bewerkingen (optellen en vermenigvuldigen) op versleutelde data toestaat.

De kern van het probleem is een Known Plaintext Attack (KPA) die mogelijk is wanneer het schema homomorfische vermenigvuldiging ondersteunt:

• In het originele FHMRS wordt een bericht $m_i$ versleuteld als $c_i = m_i + (g_i \cdot u) \pmod p$ en $\pmod q$, waarbij $p$ en $q$ geheime priemgetallen zijn en $u$ een geheim getal is.
• Als een aanvaller twee koppelparen van (plaintext, ciphertext) bezit ($m_1, c_1$ en $m_2, c_2$), kan hij de termen $c_1 - m_1 = g_1 \cdot u$ en $c_2 - m_2 = g_2 \cdot u$ berekenen.
• Door de Grootste Gemene Deler (GCD) van deze twee waarden te nemen, kan de aanvaller het geheime getal $u$ direct afleiden.
• Zodra $u$ bekend is, is het gehele systeem gebroken, omdat $u$ essentieel is voor de decryptie en de structuur van de versleuteling.

2. Methodologie: mFHMRS

Om deze kwetsbaarheid te mitigeren, stellen de auteurs een gewijzigd schema voor, genaamd Modified FHMRS (mFHMRS). De belangrijkste methodologische wijzigingen zijn:

• Uitbreiding van de Moduli: In plaats van twee geheime priemgetallen ($p, q$), gebruikt mFHMRS een reeks van $N+S$ geheime priemgetallen ($p_1, p_2, ..., p_{N+S}$). Hierbij is $N$ het aantal ondersteunde opeenvolgende vermenigvuldigingen en $S$ een extra parameter voor veiligheid.
• Chinese Reststelling (CRT) Share: Het ciphertext bestaat nu uit $N+S$ delen (shares), waarbij elk deel berekend wordt modulo een verschillend priemgetal $p_i$.
  • $c_i = ([m_i + (g_i \cdot u)]_{p_1}, ..., [m_i + (g_i \cdot u)]_{p_{N+S}})$.
• Grootte van Parameters: De auteurs definiëren strikte voorwaarden voor de bit-lengte van de parameters ($l_p$ voor priemgetallen, $l_u$ voor $u$, $l_g$ voor het willekeurige getal $g$) om zowel correctheid als veiligheid te garanderen.
  • De priemgetallen $p_i$ moeten groot genoeg zijn om lattice-aanvallen te weerstaan, maar klein genoeg om de decryptie correct te laten verlopen.
  • Er geldt: $l_p \geq \lambda$ (waarbij $\lambda$ de veiligheidsparameter is) en $l_u > l_p$.
• Homomorfische Operaties: Het schema behoudt de eigenschappen van volledig homomorfische encryptie:
  • Optellen: Componenten van ciphertexts worden componentsgewijs opgeteld.
  • Vermenigvuldigen: Componenten worden componentsgewijs vermenigvuldigd.
  • Decryptie: Gebruikt de Chinese Reststelling om het bericht te reconstrueren uit de $N+S$ delen, gevolgd door een modulo $u$ operatie om het oorspronkelijke bericht te verkrijgen.

3. Belangrijkste Bijdragen

1. Identificatie van de KPA: Het paper demonstreert expliciet hoe het originele FHMRS kwetsbaar is voor een aanval op basis van bekende plaintexts door het vinden van de GCD van de "noise"-termen.
2. Ontwerp van mFHMRS: Het introduceren van een multi-moduli structuur ($N+S$ priemgetallen) die de relatie tussen ciphertext en plaintext verstoort voor een aanvaller. Omdat de ciphertext nu verspreid is over meerdere moduli, kan een aanvaller niet direct $g_i \cdot u$ isoleren zonder de geheime $p_i$ te kennen.
3. Formele Veiligheidsanalyse: Een uitgebreide analyse van de weerstand tegen verschillende soorten aanvallen:
   • Brute-force: De complexiteit is exponentieel afhankelijk van het aantal priemgetallen en hun bit-lengte.
   • Lattice-based Attacks (LLL): Het paper toont aan dat de constructie van het rooster (lattice) en de gekozen parameters ervoor zorgen dat de kortste vector in het rooster niet de geheime sleutels onthult. De fouttermen zijn te groot voor succesvolle reductie.
   • Lineaire vergelijkingen: Zelfs met bekende plaintext-ciphertext paren, leiden de systemen van lineaire vergelijkingen (zoals $c_{ij} - m_i = g_i \cdot u - k_{ij} \cdot p_j$) tot een onoplosbaar probleem voor de aanvaller vanwege de onvoorspelbaarheid van de willekeurige getallen $g$ en de grootte van de parameters.
4. Correctheidsbewijs: Het paper levert wiskundige voorwaarden op voor de bit-lengtes van de parameters om te garanderen dat decryptie na $N$ vermenigvuldigingen en $A$ optellingen correct blijft werken (d.w.z. dat er geen overloop is die de modulo $n$ operatie verstoort).

4. Resultaten

• Veiligheid: De analyse toont aan dat mFHMRS resistent is tegen de eerder beschreven KPA. De GCD-aanval faalt omdat de aanvaller niet direct toegang heeft tot de term $(m + g \cdot u)$ in zijn pure vorm; deze is gefragmenteerd over meerdere moduli.
• Complexiteit: Voor een veiligheidsniveau van $\lambda = 128$ bit, worden parameters voorgesteld zoals $l_u = 130$ bit en $l_p = 128$ bit (voor $N=1, S=2$). De berekeningscomplexiteit voor een brute-force aanval wordt geschat op ongeveer $2^{490}$ operaties, wat praktisch onmogelijk is.
• Schaalbaarheid: Het schema schaalbaar naar grotere dieptes van vermenigvuldiging ($N$) door het aantal priemgetallen ($S$) en hun grootte aan te passen, zonder de fundamentele beveiliging te compromitteren.

5. Betekenis

Dit paper is significant voor het veld van Fully Homomorphic Encryption (FHE) omdat:

• Het een specifieke, kritieke kwetsbaarheid in een bestaand symmetrisch FHE-schema (Rivest-variant) oplost.
• Het aantoont dat het gebruik van meerdere moduli (in plaats van slechts twee) een effectieve verdediging kan zijn tegen algebraïsche aanvallen zoals GCD-berekeningen, terwijl de homomorfische eigenschappen behouden blijven.
• Het biedt een gedetailleerd raamwerk voor het kiezen van parameters (bit-lengtes) om een balans te vinden tussen veiligheid (weerstand tegen lattice-aanvallen) en correctheid (vermijden van overloop bij decryptie).
• Het draagt bij aan de ontwikkeling van lichtgewicht, symmetrische FHE-schema's die mogelijk efficiënter zijn dan traditionele asymmetrische FHE-schema's (zoals BGV of BFV), mits de juiste beveiligingsmaatregelen worden genomen.

Kortom, de auteurs hebben een robuustere versie van het Modified Rivest-schema ontworpen die de fundamentele zwaktes van de oorspronkelijke implementatie wegneemt, waardoor het een veilige kandidaat wordt voor toepassingen die privacy-bewuste berekeningen vereisen.