💻 computer science

Efficient Mod Approximation and Its Applications to CKKS Ciphertexts

Dit paper introduceert een nauwkeurige polynomaal benadering van de mod-functie voor CKKS-versleutelde data, wat leidt tot efficiëntere verpakkingsmethoden en nieuwe toepassingen zoals homomorfe afronding en conversie van geheime delen naar ciphertexts.

Oorspronkelijke auteurs: Yufei Zhou

Gepubliceerd 2026-04-08

📖 4 min leestijd☕ Koffiepauze-leesvoer

CC BY 4.0

Oorspronkelijke auteurs: Yufei Zhou

Oorspronkelijk artikel gelicentieerd onder CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ Dit is een AI-gegenereerde uitleg van het onderstaande artikel. Het is niet geschreven of goedgekeurd door de auteurs. Raadpleeg het oorspronkelijke artikel voor technische nauwkeurigheid. Lees de volledige disclaimer

Stel je voor dat je een zeer geheimzinnige brief wilt versturen naar een vriend. Je wilt dat deze vriend de brief kan lezen, erop kan rekenen, en er tekens aan kan toevoegen, maar zonder dat hij ooit de echte inhoud van de brief ziet. Dat is wat Homomorfische Versleuteling (HE) doet: het stelt computers in staat om te rekenen met versleutelde data.

Deze paper introduceert een nieuwe manier om een specifiek, lastig type rekenwerk te doen binnen deze versleutelde wereld: het modulus-berekenen (kortweg "mod").

Hier is een uitleg in simpele taal, met wat creatieve vergelijkingen:

1. Het Probleem: De Gebroken Trap

Stel je voor dat de versleutelde computer (in dit geval het CKKS-systeem) een meester is in het optellen en vermenigvuldigen van getallen. Het kan een heel complex recept berekenen terwijl de ingrediënten nog in de verpakking zitten.

Maar er is één ding waar deze computer slecht in is: de "mod" functie.
In het dagelijks leven is "mod" als het kijken naar de tijd op een klok. Als het 13:00 is, is het op een 12-uursklok 1:00. Je telt niet tot 13, je "springt" terug naar 1. Dit is een sprong in de tijd.
Voor de versleutelde computer zijn deze sprongen (discontinuïteiten) een nachtmerrie. Ze kunnen niet goed met deze sprongen omgaan. Bestaande methodes proberen dit op te lossen door een "gladde" lijn te tekenen die er een beetje op lijkt, maar die lijn werkt alleen op een klein stukje van de klok. Als je naar een ander uur kijkt, is de lijn helemaal verkeerd.

2. De Oplossing: De Perfecte Landkaart

De auteurs van dit paper hebben een nieuwe manier bedacht om deze "sprong" na te bootsen met een polynoom (een complexe wiskundige formule).
In plaats van een ruwe schets te maken, tekenen ze een ultra-accurate landkaart die de hele klok (van 0 tot het eind) perfect nabootst. Ze gebruiken een wiskundige techniek genaamd "Chebyshev-reeksen".

De Analogie: Stel je voor dat je een trampoline moet bouwen die precies de vorm van een steile klif nabootst. De oude methodes bouwden een trampoline die alleen op de top werkte. De nieuwe methode bouwt een trampoline die over de hele klif perfect werkt, zelfs op de steilste plekken.
Het Resultaat: De computer kan nu precies weten wat de rest is van een deling (bijvoorbeeld: 100 gedeeld door 7 is 14 met rest 2), zelfs als de getallen versleuteld zijn.

3. De Toepassing: De "Tetris"-Stapels (BitStack & CRTStack)

Nu de computer deze "mod"-rekenmachine heeft, kunnen ze een nieuw trucje uithalen: Data Packing (datapakking).

Stel je voor dat je een vrachtwagen (de versleutelde boodschap) hebt die 1000 vakjes groot is.

Huidige situatie: Mensen vullen vaak maar één vakje met een klein getal en laten de rest leeg. Dat is zonde van de ruimte en kost veel tijd om te versturen.
De nieuwe methode: De auteurs gebruiken hun "mod"-rekenmachine om kleine getallen (zoals cijfers van 0 tot 9) op een slimme manier in elkaar te steken, alsof je Tetris-blokjes in één grote stapel zet.
- BitStack: Dit is alsof je kleine blokjes in een lange rij zet, precies naast elkaar, zonder ruimte te verspillen.
- CRTStack: Dit is alsof je verschillende kleuren blokjes in één doos stopt, en later met een speciale sleutel (de mod-functie) weer precies de juiste kleur eruit haalt.

Waarom is dit cool?
Het verkleint de grootte van de versleutelde boodschap enorm. Het is alsof je van 100 losse postzegels naar één grote envelop gaat. Dit maakt het veel sneller en goedkoper om data naar de server te sturen, vooral voor apparaten met weinig kracht (zoals een slimme thermostaat of een telefoon).

4. Andere Toepassingen: Afronden en Geheimen Deelen

Deze nieuwe "mod"-machine heeft nog meer nut:

Afronden: Het helpt om versleutelde getallen netjes af te ronden (bijv. van 3.14159 naar 3.14), wat normaal heel lastig is in versleutelde vorm.
Geheimen Deelen: Stel je voor dat een geheim in stukjes wordt verdeeld onder 10 mensen. Normaal moeten die mensen samenkomen om het geheim te reconstrueren. Met deze methode kan de server de versleutelde stukjes van de 10 mensen direct samenvoegen tot één versleutelde boodschap, zonder dat de mensen elkaar hoeven te spreken.

Samenvatting

Deze paper zegt eigenlijk: "We hebben een manier gevonden om de versleutelde computer te leren hoe hij moet 'springen' (mod-rekenen) zonder dat hij de boodschap ontsleutelt. Hierdoor kunnen we veel meer data in één versleutelde envelop proppen, wat het systeem veel sneller en praktischer maakt voor de echte wereld."

Het is een grote stap om privacy-bewuste technologie (zoals in de zorg of slimme huizen) echt bruikbaar te maken, omdat het de vertraging en kosten van het versturen van versleutelde data drastisch verlaagt.

Titel: Efficiënte Mod-benadering en Toepassingen op CKKS Cifertexten

Auteur: Yufei Zhou (Sun Yat-sen Universiteit)

1. Het Probleem

Homomorfische Versleuteling (HE), en specifiek het CKKS-schema, maakt het mogelijk om berekeningen uit te voeren op versleutelde data zonder deze te ontsleutelen. Dit is cruciaal voor privacybehoudende toepassingen. Er zijn echter twee fundamentele beperkingen:

Gebrek aan niet-lineaire operaties: CKKS ondersteunt native alleen optelling en vermenigvuldiging. De mod-functie (modulo-reductie) is echter essentieel voor veel cryptografische protocollen en data-verwerkingstaken, maar is vanwege zijn discontinuïteit en periodiciteit extreem moeilijk nauwkeurig te benaderen met polynomen binnen HE. Bestaande methoden leveren vaak alleen nauwkeurige resultaten binnen beperkte subintervallen van het invoerbereik, niet over het volledige domein.
Inefficiëntie bij data-packing: In resource-beperkte omgevingen (zoals IoT of smart homes) is de communicatiekosten voor het uploaden van grote cifertexten een grote bottleneck. Bestaande data-packing technieken gebruiken de beschikbare "slots" (plaatsen voor plaintext-waarden) in een CKKS-cifertext niet optimaal, vooral voor kleine gehele getallen.

2. Methodologie

A. Nauwkeurige Benadering van de Mod-functie

De auteurs stellen een nieuwe methode voor om de mod-functie nauwkeurig te benaderen over het gehele invoerbereik $[0, B]$ voor kleine gehele getallen.

Techniek: In plaats van trigonometrische benaderingen (zoals sin/cos series) die vaak onnauwkeurig zijn bij sprongdiscontinuïteiten, gebruiken ze polynoominterpolatie gecombineerd met een Chebyshev-reeks.
Aanpak:
- De mod-functie wordt behandeld als een verzameling discrete steunpunten $(x, x \mod p)$ .
- Een Chebyshev-reeks wordt gebruikt om deze punten te benaderen. Chebyshev-polynomen verminderen het Runge-fenomeen en zorgen voor snelle verval van coëfficiënten, wat numerieke stabiliteit garandeert.
- Om de coëfficiënten te vinden, wordt een stelsel vergelijkingen opgelost met de kleinste-kwadratenmethode (least squares).
- Schaalfactor ( $\delta$ ): Om te voorkomen dat grote coëfficiënten de ruis in CKKS te sterk versterken, worden de coëfficiënten geschaald met een factor $\delta$ zodat ze allemaal kleiner dan 1 blijven. Dit wordt gedaan door de polynoom-evaluatie in plaintext te testen voordat deze op cifertexten wordt toegepast.
- Evaluatie: Voor de efficiënte evaluatie van de hoge graad-polynomen wordt de Paterson-Stockmeyer-methode gebruikt.

B. Data Packing Schemes: BitStack en CRTStack

Op basis van de homomorfe mod-functie worden twee nieuwe packing-methoden ontwikkeld voor kleine gehele getallen:

BitStack:
- Principe: Data wordt in binaire vorm gestapeld. Verschillende lagen van data worden samengevoegd tot één groot geheel getal ( $x = a_1 + a_2 \cdot 2^{l_1} + \dots$ ).
- Ontpakken: Gebruikt de mod-functie om lagen sequentieel af te halen (bijv. $a_1 = x \mod 2^{l_1}$ ).
- Voordeel: Zeer compacte structuur.
- Nadeel: Vereist sequentieel ontpakken, wat meer vermenigvuldigingsdiepte (multiplicative depth) kost en fouten kan accumuleren.
CRTStack (Chinese Remainder Theorem):
- Principe: Gebruikt het Chinese Reststelling-principe. Data wordt gecodeerd als resten modulo een stel onderling ondeelbare getallen ( $P_1, P_2, \dots$ ).
- Ontpakken: Elke laag kan parallel worden ontrokken door de mod-functie toe te passen met de respectieve modulus ( $a_i = x \mod P_i$ ).
- Voordeel: Parallelle verwerking en geen foutaccumulatie tussen lagen.
- Nadeel: Vereist een groter invoerbereik voor de mod-benadering.

C. Aanvullende Technieken

VecConcat & ImgConcat: Methoden om vectoren te combineren en de imaginaire delen van CKKS (die vaak onbenut blijven bij reële data) te gebruiken voor extra packing.

3. Belangrijkste Bijdragen

Nieuwe Mod-benadering: Een polynoom-benadering die de mod-functie nauwkeurig over het volledige invoerbereik voor kleine gehele getallen benadert, in tegenstelling tot bestaande methoden die beperkt zijn tot subintervallen.
Efficiënte Packing Schemes: Introductie van BitStack en CRTStack, die de gebruikte plaintext-ruimte in CKKS maximaliseren en de communicatiekosten voor het uploaden van data drastisch verlagen.
Homomorf Ronden: Implementatie van een nauwkeurige rounding-functie (Floor, Ceil, Round) voor kleine gehele getallen binnen CKKS, met een foutmarge tot $10^{-10}$ .
Secret Share naar CKKS Conversie: De eerste complete methode om additieve geheime delen (secret shares) direct om te zetten naar CKKS-cifertexten zonder de onderliggende secret sharing-scheme aan te passen. Dit overbrugt de kloof tussen secret sharing en HE.

4. Resultaten

De experimenten zijn uitgevoerd op een Intel Xeon Gold CPU met de OpenFHE bibliotheek.

Nauwkeurigheid: De voorgestelde mod-benadering bereikt een gemiddelde absolute fout van ongeveer $10^{-8}$ (bij polynoomgraad > 45), wat significant beter is dan bestaande methoden (zoals Lee et al. [LLL+21] en OpenFHE's standaard benadering) die fouten van rond de 2 hebben.
Packing Performance:
- De packing-methoden verminderen de upload-traffic met bijna twee ordes van grootte vergeleken met standaard CKKS.
- BitStack vs. CRTStack: CRTStack is sneller in ontpakken door parallelisme (11.47s vs 12.84s voor BitStack in een test), maar BitStack is compacter.
Vergelijking met Transcipher:
- In vergelijking met het Transcipher-framework (Rubato), is de auteurs' methode 1.6x sneller in het ontpakken (156s vs 407s) en heeft het een orde van grootte lagere fout ( $4.00 \times 10^{-6}$ vs $7.54 \times 10^{-5}$ ).
- De encryptietijd aan de client-kant is lager dan bij Transcipher.
Secret Share Conversie: De conversie van secret shares naar CKKS-cifertexten is succesvol uitgevoerd met fouten in de orde van $10^{-8}$ , zelfs bij een toenemend aantal partijen.

5. Betekenis en Conclusie

Dit werk lost een langdurig probleem op in het domein van Homomorfische Versleuteling: het uitvoeren van nauwkeurige modulo-berekeningen op versleutelde data.

Praktische Impact: De methoden maken het mogelijk om privacybehoudende toepassingen voor kleine gehele getallen (zoals genomische data, sensoren, of image processing) veel efficiënter uit te voeren door de communicatiekosten te verlagen en de rekenkracht van de server beter te benutten.
Innovatie: Het biedt een brug tussen secret sharing en HE, wat nieuwe mogelijkheden opent voor hybride privacy-preserving systemen.
Beperking: De methode is momenteel beperkt tot kleine invoerbereiken (enkele tientallen tot honderden), waardoor het niet direct toepasbaar is voor bootstrapping met grote moduli, maar ideaal voor specifieke toepassingen met kleine data-elementen.

Samenvattend biedt dit paper een robuuste oplossing voor de beperkingen van CKKS bij niet-lineaire operaties en introduceert het efficiënte strategieën voor data-dichtheid, wat de schaalbaarheid van HE in real-world scenario's aanzienlijk verbetert.