Accurate BGV Parameters Selection: Accounting for Secret and Public Key Dependencies in Average-Case Analysis

In dit artikel wordt een nieuwe gemiddelde-benadering voorgesteld voor het nauwkeurig selecteren van BGV-parameters door de afhankelijkheden tussen fouten in geheime en publieke sleutels te modelleren, wat leidt tot een verbeterde efficiëntie en veiligheid zonder afhankelijkheid van specifieke bibliotheken.

De kern

Hier is een uitleg van het onderzoek in eenvoudig Nederlands, vol met creatieve metaforen om het begrijpelijk te maken voor iedereen.

De Grote Uitdaging: Een Onzichtbare Rots in je Fietsband

Stel je voor dat Fully Homomorphic Encryption (FHE) een magische fiets is. Je kunt erop rijden (rekenen) terwijl je nog steeds in een gesloten koffer zit (de versleutelde data). Je kunt de wielen laten draaien en de pedalen trappen, maar niemand mag zien wat er in de koffer zit.

Het probleem? Elke keer als je trapt (een berekening doet), wordt je fietsband een beetje dunner. Er komt een rotsje in de band te zitten (dit noemen we "ruis" of "noise").

• Als je een keer trapt, is het geen probleem.
• Maar als je langdurig een route rijdt (een complexe berekening), stapelen de rotsjes zich op.
• Op een gegeven moment is de band te dun en plaatst hij. De versleutelde data is dan kapot en je kunt het resultaat niet meer lezen.

Om dit te voorkomen, moet je een extra dikke band kiezen (de "modulus" of $q$). Hoe dikker de band, hoe meer rotsjes hij kan opvangen. Maar een superdikke band is zwaar en traag. Je wilt dus precies de juiste dikte: dik genoeg om niet te lekken, maar licht genoeg om snel te fietsen.

Het Probleem: De Slechte Voorspellers

In het verleden hebben wetenschappers geprobeerd te voorspellen hoeveel rotsjes er in je band komen. Ze gebruikten twee methoden:

1. De "Worst-Case" methode: Ze dachten: "Stel dat elke rots precies op het zwakste punt valt!" Hierdoor kozen ze altijd een enorm dikke band. Dit was veilig, maar veel te zwaar en traag.
2. De "Gemiddelde" methode: Ze dachten: "Gemiddeld vallen rotsjes willekeurig." Dit was sneller, maar ze maakten een grote fout: ze dachten dat elke rots onafhankelijk van de andere viel.

De fout in de oude methode:
In werkelijkheid zijn de rotsjes niet onafhankelijk. Ze zijn allemaal gemaakt uit hetzelfde mengsel (de geheime sleutel en de publieke sleutel). Als er al een rots in de band zit, is de kans groter dat er een tweede rots in de buurt komt die op dezelfde manier is gevormd. Ze "kijken naar elkaar". De oude methoden zagen dit niet en dachten dat de band dikker was dan hij echt was. Dit leidde tot twee problemen:

• Soms lekte de band toch (veiligheidsrisico).
• Soms was de band onnodig dik (inefficiëntie).

De Oplossing: De Nieuwe "Rots-Tracker"

De auteurs van dit paper (Beatrice, Chiara, Nadir en Matilda) hebben een nieuwe manier bedacht om de rotsjes te tellen. Ze noemen het een gemiddelde-benadering, maar dan met een superkracht: ze houden rekening met de afhankelijkheid.

Stel je voor dat je een team van detectives bent die de rotsjes tellen.

• Oude detectives: "Elke rots is een vreemde. Laten we ze apart tellen."
• Nieuwe detectives: "Wacht even! Deze rotsjes komen uit dezelfde fabriek (dezelfde sleutel). Als we er één zien, weten we dat er waarschijnlijk nog een paar in de buurt zitten die op elkaar lijken."

Ze hebben een nieuwe formule bedacht (een "correctiefunctie") die zegt: "Oké, we tellen niet alleen het aantal rotsjes, we tellen ook mee hoezeer ze op elkaar lijken."

Waarom werkt dit? (De Magie van de "Modulus Switch")

Je vraagt je misschien af: "Is het niet gevaarlijk om te vertrouwen op gemiddelden? Wat als de rotsjes toch heel raar gedragen?"

De auteurs bewijzen iets heel belangrijks:
In de BGV-methode (het type fiets dat ze bestuderen) wordt er een trucje gebruikt genaamd "Modulus Switching". Dit is alsof je halverwege je rit de band even verwisselt voor een schone, nieuwe band, maar dan wel zo dat je de route kunt blijven rijden.

Ze tonen aan dat door deze verwisseling, de rotsjes zich perfect gedragen als een normaal verdeling (een Gaussische kromme). Ze worden niet "raar" of "zwaar" (zoals sommige critici dachten). Ze worden gewoon willekeurig en voorspelbaar.

• Zonder deze verwisseling: De rotsjes gedragen zich als een storm met rare windstoten (zware staarten).
• Met deze verwisseling: De rotsjes zijn als een zachte, voorspelde regenbui.

Dit betekent dat hun nieuwe methode veilig is, zolang je die verwissel-truc gebruikt (wat alle moderne software al doet).

Het Resultaat: Lichter en Sneller

Wat betekent dit voor de praktijk?
Omdat ze nu precies weten hoeveel rotsjes er echt in de band komen (en niet hoe erg ze er kunnen komen), kunnen ze de band dunner maken dan voorheen.

• Vroeger: "We maken de band 100% dik voor de zekerheid." -> Traag.
• Nu: "We weten dat de band 10% dikker hoeft dan de rotsjes." -> Veel sneller en efficiënter.

In hun paper laten ze zien dat ze de grootte van de "band" (de modulus) kunnen verkleinen met ongeveer 10 tot 20% vergeleken met de software die nu wordt gebruikt (zoals OpenFHE en HElib). Dat klinkt misschien niet als veel, maar in de wereld van cryptografie betekent dit dat berekeningen veel sneller gaan en minder computerkracht nodig hebben.

Samenvatting in één zin

De auteurs hebben een nieuwe manier bedacht om precies te voorspellen hoeveel "ruis" er ontstaat bij versleutelde berekeningen door rekening te houden met de verborgen banden tussen de data, waardoor we versleutelde systemen kunnen bouwen die veilig, maar veel sneller en lichter zijn dan ooit tevoren.

Technische samenvatting

Hier is een gedetailleerde technische samenvatting van het artikel "Accurate BGV Parameters Selection: Accounting for Secret and Public Key Dependencies in Average-Case Analysis", geschreven in het Nederlands.

Titel: Nauwkeurige selectie van BGV-parameters: Rekening houdend met afhankelijkheden van geheime en publieke sleutels in een gemiddelde-gevalanalyse

Auteurs: Beatrice Biasioli, Chiara Marcolla, Nadir Murru, en Matilda Urani.
Context: Fully Homomorphic Encryption (FHE), specifiek het Brakerski-Gentry-Vaikuntanathan (BGV) schema.

---

1. Het Probleem

Het BGV-schema is een van de meest gebruikte FHE-schema's, gebaseerd op het Learning with Errors (LWE) en Ring-LWE (RLWE) probleem. Een kritieke uitdaging bij het gebruik van FHE is het beheer van ruis (noise). Bij elke homomorfe operatie, en vooral bij vermenigvuldiging, neemt de ruis toe. Als de ruis een bepaalde drempelwaarde overschrijdt (relatief aan de modulus $q$), faalt de decryptie.

Om dit te voorkomen, moeten parameters (zoals de modulus $q$) conservatief worden gekozen. Echter, huidige methoden voor het schatten van ruisgroei hebben twee grote tekortkomingen:

1. Onderschatting van ruis: Veel bestaande "average-case" (gemiddelde-geval) analyses gaan er ten onrechte van uit dat ruiscoëfficiënten onafhankelijk zijn. Ze negeren de afhankelijkheden die ontstaan doordat ciphertexts dezelfde geheime sleutel ($s$) en publieke sleutel-componenten (zoals de foutterm $e$) delen. Dit leidt tot te optimistische schattingen, wat decryptiefouten en beveiligingslekken kan veroorzaken.
2. Worst-case vs. Average-case: Worst-case analyses (gebaseerd op normen) zijn veilig maar leiden tot overmatig grote moduli, wat de efficiëntie sterk verlaagt. Bestaande average-case benaderingen proberen dit op te lossen, maar missen vaak de nauwkeurigheid door de bovengenoemde afhankelijkheden te negeren.

Daarnaast is er discussie over of ruiscoëfficiënten wel een Gaussische verdeling volgen (nodig voor nauwkeurige probabilistische grenzen), met name zonder moduli-switching.

2. Methodologie

De auteurs ontwikkelen een nieuwe average-case analyse voor BGV die specifiek rekening houdt met de structurele afhankelijkheden tussen ruiscoëfficiënten.

• Model van Ruis: In plaats van ruis als volledig onafhankelijke variabelen te behandelen, analyseren de auteurs de kritieke grootheid $\nu$ (de ruis) als een polynoom in de geheime sleutel $s$ en de foutterm $e$. Ze tonen aan dat termen zoals $s^k$ en $e^k$ gemeenschappelijk zijn voor alle ciphertexts gegenereerd met dezelfde sleutels.
• Correctiefunctie $F$: De kern van hun methode is het introduceren van een correctiefunctie $F$ (gebaseerd op Lemma 3 en de stelling van Isserlis voor multivariate normale verdelingen). Deze functie corrigeert het product van varianties bij homomorfe vermenigvuldiging.
  • In tegenstelling tot eerdere werken (zoals voor BFV), moeten ze hier zowel de afhankelijkheden van de geheime sleutel ($s$) als de publieke sleutel-fout ($e$) modelleren.
  • Ze definiëren $F_s(\iota_1, \iota_2)$ en $F_e(K_1, K_2)$ om de extra variantie te compenseren die ontstaat door de vermenigvuldiging van termen met machten van $s$ en $e$.
• Gaussische Aannames en Moduli-Switching: De auteurs bewijzen theoretisch en verifiëren empirisch dat, mits moduli-switching correct wordt toegepast (een standaardtechniek in BGV), de ruiscoëfficiënten inderdaad een Gaussische verdeling volgen. Zonder moduli-switching vertonen de verdelingen zware staarten (heavy-tailed), wat de aannames van average-case analyses ongeldig maakt.
• Variance Tracking: Ze leiden formele formules af voor de variantie van de ruis na encryptie, optelling, constante vermenigvuldiging, moduli-switching en homomorfe vermenigvuldiging.

3. Belangrijkste Bijdragen

1. Nieuwe Average-Case Analyse: Het is de eerste average-case analyse voor BGV die geen onderschattingen geeft door expliciet de afhankelijkheden van de geheime en publieke sleutels te modelleren.
2. Formele Correctiefunctie: In plaats van heuristieken, bieden ze een formeel afgeleide correctiefunctie die de product-termen van varianties aanpast. Dit leidt tot een factor 2 in de variantieschatting voor specifieke circuits (in vergelijking met de veronderstelling van onafhankelijkheid).
3. Validatie van Gaussische Aannames: Ze weerleggen de kritiek dat ruis in BGV niet Gaussisch is, door aan te tonen dat moduli-switching essentieel is om de Gaussische verdeling te behouden. Ze stellen een voorwaarde op voor de grootte van de priemgetallen (moduli) om dit te garanderen.
4. Library-Onafhankelijke Richtlijnen: De methode is generiek en niet gebonden aan specifieke implementaties (zoals HElib of OpenFHE), maar focust op de structurele eigenschappen van het BGV-schema.

4. Resultaten

De auteurs hebben hun methode getest en vergeleken met bestaande benaderingen en bibliotheken:

• Nauwkeurigheid: De geschatte varianties komen zeer nauw overeen met experimentele waarden (berekend via de OpenFHE bibliotheek). In tegenstelling tot eerdere methoden wordt de ruis nooit onderschat.
• Vergelijking met Worst-Case: De nieuwe methode levert veel strakkere (smallere) grenzen op dan worst-case analyses (gebaseerd op de canonieke norm), wat leidt tot kleinere moduli.
• Vergelijking met Bestaande Bibliotheken:
  • OpenFHE: De auteurs tonen aan dat hun methode leidt tot een aanzienlijke reductie in de grootte van de ciphertext-modulus ($q$). Voor een circuit met diepte 3 en ringdimensie $2^{13}$wordt een reductie van ongeveer 26 bits in$\log_2(q)$ bereikt (van ~151.8 naar ~124.5).
  • HElib: Ook in vergelijking met HElib toont de methode aan dat de verhouding tussen opeenvolgende moduli (de priemgetallen $p_\ell$) kleiner kan worden gekozen (tot 6 bits minder) terwijl de veiligheid en correctheid behouden blijven.
• Veiligheid: Door de afhankelijkheden te modelleren, worden decryptiefouten voorkomen en wordt het risico op sleutelherstel-aanvallen (die kunnen ontstaan door te kleine moduli) geminimaliseerd.

5. Betekenis en Conclusie

Dit werk is van groot belang voor de praktische toepassing van Fully Homomorphic Encryption.

• Efficiëntie: Door nauwkeurigere ruismodellen te gebruiken, kunnen cryptografische parameters (vooral de modulus $q$) kleiner worden gekozen. Dit resulteert in snellere berekeningen en minder geheugengebruik, zonder in te leveren op veiligheid.
• Betrouwbaarheid: Het biedt een solide theoretische basis voor het kiezen van parameters die garanderen dat decryptie correct verloopt, zelfs in diepe circuits.
• Toekomst: De resultaten bevestigen dat average-case analyses, mits correct toegepast met aandacht voor afhankelijkheden en moduli-switching, de voorkeur hebben boven conservatieve worst-case benaderingen voor het optimaliseren van FHE-schema's.

Kortom, de auteurs leveren een cruciale verbetering in de parameterselectie voor BGV, waardoor FHE-systemen zowel veiliger als efficiënter worden.