💻 computer science

Low-Latency Bootstrapping for CKKS using Roots of Unity

Dit artikel introduceert Sparse Roots of Unity (SPRU), een nieuw bootstrapping-algoritme voor het CKKS homomorfe encryptieschema dat modulaire rekenkunde in complexe eenheidswortels inbedt om de multiplicatieve diepte aanzienlijk te verminderen en een tot 5x verbetering in latentie te bereiken vergeleken met traditionele methoden.

Oorspronkelijke auteurs: Jean-Sebastien Coron, Robin Koestler

Gepubliceerd 2026-07-31

📖 8 min leestijd🧠 Diepgaand

CC BY 4.0

Oorspronkelijke auteurs: Jean-Sebastien Coron, Robin Koestler

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 geheim bericht naar een vriend wilt sturen, maar je kunt de post niet vertrouwen. Je vergrendelt je brief in een doos, maar de post moet de brief sorteren, stapelen en misschien zelfs openen om het adres te controleren zonder ooit te zien wat erin zit. Dit is de magie van Fully Homomorphic Encryption (FHE). Het stelt computers in staat om berekeningen uit te voeren op data die nog steeds in hun versleutelde vorm zit. Denk aan een magische keuken waar je een taart kunt bakken met ingrediënten die nog steeds in hun verzegelde, ongeopende verpakkingen zitten; de oven doet het werk, en wanneer je de doos aan het einde eindelijk opent, heb je een verse taart, maar de oven wist nooit wat de ingrediënten waren.

Er is echter een addertje onder het gras. Elke keer dat de computer een wiskundige operatie uitvoert op deze vergrendelde data, wordt er een klein beetje "ruis" of statische elektriciteit aan de doos toegevoegd, zoals stof dat op een lens neerdaalt. Als je te veel berekeningen uitvoert, wordt de ruis zo luid dat de boodschap onleesbaar en verstoord raakt. Om dit op te lossen, gebruiken wetenschappers een proces genaamd bootstrapping. Het is als een magische resetknop: de computer neemt de ruizige, vergrendelde doos, voert een complexe truc uit om het stof eruit te poetsen, en plaatst de boodschap terug in een frisse, schone doos zodat de berekeningen kunnen doorgaan. Het probleem is dat deze schoonmaaktruc ongelooflijk traag en zwaar is, alsof je een auto probeert te wassen met een tandenborstel. Het kost zoveel rekenkracht dat het alles vertraagt, waardoor praktische toepassingen traag aanvoelen.

Hier komt een nieuw artikel van Jean-Sébastien Coron en Robin Köstler om de hoek kijken. Zij introduceren een slimme nieuwe manier om dit "schoonmaakproces" uit te voeren, genaamd Sparse Roots of Unity (SPRU) bootstrapping. In plaats van de oude, zware methode die probeert een complexe curve (zoals een sinusgolf) te benaderen, hebben zij een manier gevonden om de data direct te mappen op een cirkel van getallen die "roots of unity" worden genoemd. Stel je voor dat je in plaats van het poetsen van de auto met een tandenborstel, de auto gewoon op een enorme, draaiende carrousel schuift die het stof er vanzelf afveegt terwijl hij draait. Hun methode is veel sneller en lichter, vooral wanneer je met een klein aantal gegevensitems tegelijk werkt. Door deze nieuwe aanpak te gebruiken, hebben ze aangetoond dat de tijd die nodig is om de versleuteling te resetten, met wel 5 keer kan worden verminderd vergeleken met de standaardmethode, waardoor de magie van geheime berekeningen meer aanvoelt als een tastbare realiteit dan als een verre droom.

De Oude Manier: De Zware Werker

Om te begrijpen waarom deze nieuwe truc zo speciaal is, moeten we kijken naar hoe de oude methode werkte. In het standaard CKKS-encryptieschema (het meest populaire schema voor het doen van wiskunde met decimalen), was het bootstrapping-proces als het proberen te raden van de vorm van een berg door er een vloeiende lijn overheen te tekenen. De computer moest een ingewikkelde polynoom (een fancy wiskundige formule) evalueren die een "modulaire reductie" benaderde. Denk aan modulaire reductie als een manier om een lange getallenlijn in een cirkel te vouwen zodat deze weer in een kleine doos past. De oude methode probeerde een sinusgolf (een golvende lijn) te gebruiken om dit inkapselingsproces na te bootsen.

Hoewel dit werkte, was het een zware opgave. Het vereiste een diepe stapel wiskundige operaties, wat betekende dat de computer een zeer grote "ringdimensie" (een maat voor de grootte van de wiskundige speeltuin) moest gebruiken. Dit was als proberen een marathon te lopen terwijl je een zware rugzak draagt; het vertraagde alles en beperkte hoeveel nuttig werk er na de reset kon worden gedaan. De auteurs wijzen erop dat deze hoge "multiplicatieve diepte" (het aantal lagen van de wiskunde waar je doorheen moet gaan) de belangrijkste flessenhals was, wat het proces te traag maakte voor praktisch gebruik, vooral wanneer je slechts een paar getallen tegelijk wilt verwerken.

De Nieuwe Manier: De Carrousel van Roots

Het nieuwe idee van de auteurs, SPRU bootstrapping, verandert de regels door de zware benadering volledig over te slaan. In plaats van te proberen een golvende lijn te tekenen om de inkapseling na te bootsen, realiseerden zij zich dat ze de data direct op de "roots of unity" konden inbedden.

Hier is een eenvoudige analogie: stel je voor dat de oude methode leek op het proberen te vertalen van een geheime code door voor elke letter een lange, ingewikkelde woordenboekvermelding te schrijven. Dat duurde eeuwen. De nieuwe methode is het besef dat de geheime code eigenlijk gewoon een reeks sleutels is die perfect in een specifiek slot passen. In plaats van te vertalen, draai je gewoon de sleutel om.

In technische termen mappen ze de additieve groep (de manier waarop getallen optellen) direct naar de complexe roots of unity (punten op een cirkel in het complexe getallensysteem). Omdat het CKKS-encryptieschema van nature deze complexe getallen begrijpt, kan de computer de "schoonmaakoperatie" direct uitvoeren, zonder een sinusgolf te hoeven benaderen. Het is alsof je overstapt van het bouwen van een brug met individuele stenen naar het gebruiken van een prefab boog die er perfect in past.

Het Geheime Ingrediënt: Sparsity en Packing

Het artikel stopt niet bij de nieuwe kaart; ze hebben ook twee slimme optimalisaties geïntroduceerd om het nog sneller te maken, vooral bij het werken met een klein aantal datastellen (zoals een lijst met enkele getallen).

De Bits Verpakken: In de oude dagen, als je een geheime sleutel van 1.000 bits had, moest de computer elke bit één voor één afhandelen. De auteurs realiseerden zich dat ze deze bits konden "verpakken" in de slots van de encryptie, zoals het proppen van 1.000 brieven in een enkele, super-efficiënte brievenbus. Dit verminderde het aantal zware berekeningen van een enorme hoeveelheid naar een logaritmische hoeveelheid (denk eraan om een lange lijst in te korten tot een korte samenvatting).
De Sparse Block Trick: Ze gingen er ook van uit dat de geheime sleutel een speciale structuur had: in plaats van willekeurige bits, was de sleutel verdeeld in blokken waarbij slechts één bit in elk blok een "1" was en de rest "0". Dit is als het hebben van een rij lichtschakelaars waarbij er in elke groep van tien slechts één aan staat. Door deze "sparse" structuur te gebruiken, konden ze veel moeilijke vermenigvuldigingsstappen vervangen door eenvoudige optelstappen. Dit is het verschil tussen het vermenigvuldigen van een lange lijst getallen en het simpelweg optellen van een paar van hen. Dit verminderde de "diepte" van de berekening nog verder, van een hoge toren naar een kleine trap.

De Resultaten: Het Versnellen van de Magie

De auteurs hebben hun nieuwe methode getest met de OpenFHE bibliotheek, een populaire tool voor het bouwen van encryptiesoftware. Ze vergeleken hun SPRU bootstrapping met de originele, zware methode.

De resultaten waren opvallend voor specifieke scenario's. Wanneer ze ciphertexts met een klein aantal slots verwerkten (wat gebruikelijk is in veel echte toepassingen), was hun nieuwe methode tot wel 5 keer sneller (een 5x reductie in latentie). Dit is een enorme zaak, want het betekent dat de "resetknop" niet zo lang hoeft te wachten, waardoor de computer veel sneller weer nuttig werk kan doen.

De paper merkt echter voorzichtig op dat dit geen wondermiddel is voor elke situatie. Als je een enorm aantal slots probeert te verwerken (een enorme lijst met data), kan de oorspronkelijke methode nog steeds efficiënter zijn. Maar voor de vele gevallen waarin we met kleinere batches data werken, biedt deze nieuwe aanpak een aanzienlijke versnelling.

Waarom het Ertoe Doet

De schoonheid van dit werk is dat het niet alleen de cijfers bijstuurt; het verandert fundamenteel hoe we over het bootstrapping-proces denken. Door af te stappen van de zware polynoom-benaderingen en de natuurlijke mogelijkheden van het encryptieschema te omarmen, hebben de auteurs aangetoond dat we de volledig homomorfe encryptie veel praktischer kunnen maken.

Ze bewezen dat door deze "roots of unity" en slimme verpakkings-technieken te gebruiken, we de tijd en rekenkracht die nodig is om versleutelde data bruikbaar te houden, aanzienlijk kunnen verminderen. Hoewel het artikel zich richt op de technische details en de wiskunde achter de schermen, is de boodक duidelijk: de droom om complexe berekeningen op geheime data uit te voeren zonder vertraging, komt dichter bij de realiteit. De auteurs hebben een nieuwe, lichtere en snellere manier geboden om de magie levend te houden, waardoor het mogelijk wordt om een toekomst voor te stellen waarin jouw private data kan worden verwerkt in de cloud zonder ooit gezien te worden, en zonder dat je eeuwig op het resultaat hoeft te wachten.

Technische Samenvatting: Laag-Latentie Bootstrapping voor CKKS met behulp van Roots of Unity

Probleemstelling

Het CKKS homomorfe encryptieschema ondersteunt benaderende rekenkunde op versleutelde complexe getallen, wat het geschikt maakt voor veilige machine learning en cloud computing. Echter, een kritieke bottleneck in CKKS is de bootstrapping procedure, die vereist is om cipherteksten te verversen en onbeperkte computationele diepte mogelijk te maken.

De oorspronkelijke CKKS bootstrapping-methode [CHK+18a] vertrouwt op de homomorfe evaluatie van een polynoombenadering van de modulaire reductiefunctie (specifiek, een geschaalde sinusfunctie). Deze aanpak lijdt onder twee belangrijke nadelen:

Hoge Multiplicatieve Diepte: De polynoombenadering vereist een diep circuit, wat een grote ciphertext-modulus noodzakelijk maakt.
Inefficiëntie voor Kleine Aantal Slots: De complexiteit van de oorspronkelijke methode schaalt met het aantal slots ( $n$ ) en de ringdimensie ( $N$ ), waarbij vaak $O(\log n + \log N)$ operaties nodig zijn. Deze hoge diepte dwingt tot het gebruik van grotere ringdimensies om veiligheid te garanderen, wat leidt tot verhoogde latentie.

De auteurs identificeren de behoefte aan een bootstrapping-algoritme dat de multiplicatieve diepte vermindert, waardoor kleinere ringdimensies en aanzienlijk lagere latentie mogelijk worden, met name voor cipherteksten met een klein aantal slots.

Methodologie: Sparse Roots of Unity (SPRU)

Het paper introduceert Sparse Roots of Unity (SPRU) bootstrapping, een nieuw algoritme dat fundamenteel verandert hoe modulaire reductie wordt uitgevoerd in CKKS.

Kernconcept: Natieve Embedding

In plaats van modulaire reductie te benaderen via een sinusfunctie, implementeert SPRU bootstrapping direct de additieve groep $\mathbb{Z}_q$ in de multiplicatieve groep van complexe roots of unity. De auteurs maken gebruik van de homomorfisme:
$f: \mathbb{Z}_q \to \mathbb{C}, \quad x \mapsto \exp(2i\pi \cdot x/q)$

Voor een LWE-stijl decryptievergelijking $m = \langle s, c \rangle \pmod q$ , observeren de auteurs dat:
$\exp(2i\pi \cdot m/q) = \prod_{k=0}^{N-1} \exp(2i\pi \cdot c_k s_k / q)$
Aangezien de bits van de geheime sleutel $s_k \in \{0, 1\}$ fungeren als selectors, kan dit product herschreven worden als:
$\exp(2i\pi \cdot m/q) = \prod_{k=0}^{N-1} (1 + (\exp(2i\pi \cdot c_k/q) - 1) \cdot s_k)$
Door het imaginaire deel te isoleren en een lineaire schalingfactor toe te passen, kan de oorspronkelijke boodschap $m$ worden hersteld. Deze vergelijking kan homomorf binnen het CKKS-schema worden geëvalueerd zonder de polynoombenadering van de sinusfunctie.

Belangrijke Optimalisaties

Om deze aanpak praktisch te maken, introduceren de auteurs twee cruciale optimalisaties:

Packing van Secret-Key Bits:
In plaats van elke bit van de geheime sleutel afzonderlijk te versleutelen, worden de $N$ bits verpakt in de $N/2$ slots van twee CKKS cipherteksten. De termen $(\exp(2i\pi \cdot c_k/q) - 1)$ worden op soortgelijke wijze verpakt. Het product van deze termen wordt berekend met de Product Operator ( $Pr_{N/2 \to 1}$ ), die het aantal homomorfe multiplicaties reduceert van $O(N)$ naar $O(\log N)$ .
Sparse Block Secret Key:
De auteurs gaan uit van een gestructureerde geheime sleutel $s$ verdeeld in $h$ blokken van grootte $B = N/h$ , waarbij elk blok precies één niet-nul bit bevat (een '1'). Deze structuur maakt het mogelijk om het product binnen elk blok te vervangen door een som.
- De som binnen de blokken wordt berekend met de Trace Operator ( $Tr_{N/2 \to h}$ ), die alleen optellingen en automorfismen omvat (geen multiplicatieve diepte).
- Het uiteindelijke product wordt genomen over de $h$ blokresultaten.
- Resultaat: De multiplicatieve diepte wordt gereduceerd van $\log_2 N + 2$ naar $\log_2 h + 1$ . Omdat $h \ll N$ , wordt de vereiste modulusgrootte hiermee aanzienlijk verlaagd.

Uitbreiding naar Meerdere Slots

De methode wordt gegeneraliseerd om $n$ slots te verwerken (waarbij $n \le N/2$ ). De decryptiematrix wordt geëxtraheerd en de bootstrapping-vergelijking wordt parallel toegepast op elk van de $n$ boodschapcomponenten. De complexiteit is $O(n + \log N)$ , wat asymptotisch hoger is dan de oorspronkelijke CKKS bootstrapping ( $O(\log n + \log N)$ ) voor grote $n$ . Echter, voor kleine $n$ levert de verminderde multiplicatieve diepte superieure praktische prestaties op.

Belangrijkste Bijdragen

SPRU Bootstrapping Algoritme: Een nieuwe bootstrapping-techniek voor CKKS die de sinusfunctie-benadering vervangt door de natieve evaluatie van roots of unity.
Verminderde Multiplicatieve Diepte: Door gebruik te maken van sparse block secret keys en de trace operator, bereikt het algoritme een multiplicatieve diepte van $O(\log h)$ , wat aanzienlijk lager is dan de $O(\log N)$ van de oorspronkelijke methode.
Geoptimaliseerde Implementatie: De auteurs bieden een open-source implementatie aan met de OpenFHE C++ bibliotheek, waarmee compatibiliteit met Residue Number System (RNS) aritmetica en bestaande lineaire transformatie-optimalisaties (SlotToCoeff) wordt aangetoond.
Veiligheidsanalyse: Een formele analyse van de block binary secret key distributie, die aantoont dat dit de veiligheid van het RLWE-probleem tegen bekende aanvallen (hybride dual en meet-in-the-middle aanvallen) niet verzwakt, mits de parameters correct worden aangepast.

Resultaten

De auteurs hebben de SPRU bootstrapping gebenchmarkt tegen de oorspronkelijke CKKS bootstrapping met behulp van de OpenFHE-bibliotheek met 128-bit veiligheidsparameters.

Latentie-reductie: Voor cipherteksten met een klein aantal slots bereikt SPRU bootstrapping een reductie in latentie van tot wel 5x.
Efficiëntie: De reductie in multiplicatieve diepte maakt het gebruik van kleinere ringdimensies mogelijk, wat verder bijdraagt aan de versnelling.
Parallellisme: De methode is zeer paralleliseerbaar; met $n$ processoren kan een $O(\log N)$ complexiteit worden bereikt die vergelijkbaar is met de oorspronkelijke methode.

Betekenis en Claims

Het paper claimt dat SPRU bootstrapping een praktisch alternatief biedt voor de oorspronkelijke CKKS bootstrapping, specifiek gericht op scenario's waarin lage latentie cruciaal is en het aantal slots klein is. Door dure polynoombenaderingen te vermijden en de multiplicatieve diepte te verlagen, maakt de methode efficiëntere het verversen van cipherteksten mogelijk.

De auteurs positioneren hun werk als een belangrijke stap naar het levensvatbaar maken van volledig homomorfe encryptie voor real-world toepassingen die frequente bootstrapping vereisen. Zij merken op dat hoewel hun methode is geoptimaliseerd voor kleine slot-aantallen, het complementair is aan bestaand werk (zoals het onafhankelijke werk van Cheon et al. [CHKS25] dat zich richt op volledige $N/2$ -slot bootstrapping) door een andere afweging te bieden die de voorkeur geeft aan latentie boven massaal parallellisme voor kleine datasets.

Het paper concludeert dat de verminderde multiplicatieve diepte de primaire drijfveer is voor efficiëntie, waardoor er meer computationele niveaus vrijkomen voor nuttige operaties na de bootstrapping en het gebruik van kleinere, snellere ringdimensies mogelijk wordt.