💻 computer science

Triple-Hoisted Baby-Step Giant-Step Linear Transformation over CKKS Homomorphic Encryption and Hardware Accelerator

Dit artikel presenteert een drievoudig gehesste baby-step giant-step-algoritme en een bijbehorende geheugen-geoptimaliseerde FPGA-hardwareversneller die de rotaties van ciphertexts, de toegang tot extern geheugen en de computatietijd voor lineaire transformaties in CKKS-homomorfische encryptie aanzienlijk verminderen.

Oorspronkelijke auteurs: Sajjad Akherati, Xinmiao Zhang

Gepubliceerd 2026-05-19

📖 5 min leestijd🧠 Diepgaand

CC BY 4.0

Oorspronkelijke auteurs: Sajjad Akherati, Xinmiao Zhang

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 geheime agent bent die probeert een complex raadsel op te lossen, maar je mag alleen met de puzzelstukken werken terwijl ze vergrendeld zitten in een zware, onbreekbare kluis. Je kunt de kluis niet openen om de stukken te zien, toch moet je ze herschikken om het raadsel op te lossen. Dit is de uitdaging van Homomorf Versleuteling (HE): berekeningen uitvoeren op gegevens die de hele tijd versleuteld blijven.

Dit artikel presenteert een nieuwe, super-efficiënte manier om een specifiek type raadsel op te lossen, genaamd een Lineaire Transformatie (een wiskundige bewerking die veel wordt gebruikt in Kunstmatige Intelligentie en neurale netwerken), terwijl de gegevens nog steeds vergrendeld zitten in de kluis.

Hier is de uiteenzetting van hun oplossing met eenvoudige analogieën:

1. Het Probleem: Het "Zware Tillen" van het Verplaatsen van Gegevens

In de wereld van versleutelde gegevens is het verplaatsen van een stukje informatie van de ene plek naar de andere binnen de kluis ongelooflijk duur. Het is alsof je probeert een vleugelpiano een trap op te slepen; het kost veel tijd, energie en speciale apparatuur (genaamd "rotatie-sleutels").

De Oude Manier: Om het raadsel op te lossen, moesten eerdere methoden de piano duizenden keren de trap op slepen. Dit veroorzaakte een enorme file, vertraagde alles en vereiste een enorm magazijn (geheugen) om alle sleutels en tussenstappen op te slaan.
De Bottleneck: De grootste vertraging was niet het uitvoeren van de wiskunde; het was het constant heen en weer rennen naar het "magazijn" (geheugen buiten de chip) om sleutels en gegevens te halen. Dit is alsof een kok elke keer naar de supermarkt rent voor een snufje zout.

2. De Oplossing: Het "Drie-Voudig Hijs" Liftsysteem

De auteurs stellen een nieuw algoritme voor genaamd Triple-Hoisted Baby-Step Giant-Step (TH-BSGS).

Het Concept "Baby-Step Giant-Step": Stel je voor dat je 100 mijl moet lopen. In plaats van 100 kleine stapjes te nemen, neem je 10 "gigantische" stappen, en voor elke gigantische stap neem je 10 "baby"-stapjes. Dit vermindert het totale aantal keren dat je moet stoppen om je kaart te controleren.
De Innovatie "Triple-Hoisting": Eerdere versies van deze methode hadden twee lagen van deze stappen. De auteurs beseften dat ze de "baby-stapjes" nog verder konden opsplitsen in een derde laag.
- De Analogie: Denk aan "hijsen" als het gebruik van een kraan om zware dozen te tillen. Bij de oude methode moest je stoppen en de dozen opnieuw rangschikken elke keer als je een laag tilde. De nieuwe "Triple-Hoisted" methode stelt een systeem op waarbij je drie lagen dozen tegelijk kunt tillen zonder te stoppen om ze opnieuw te rangschikken. Je doet het zware tillen één keer, en de wiskunde stroomt soepel.
- Het Resultaat: Dit vermindert drastisch het aantal keren dat je de piano moet verplaatsen (versleutelde tekst-rotaties uitvoeren).

3. De Hardware: Een Aangepaste "Assemblagelijn"

Zelfs met een beter algoritme moet de hardware worden gebouwd om hierop aan te sluiten. De auteurs ontwierpen een aangepaste FPGA-accelerator (een gespecialiseerde computerchip).

De "Permutatiekring" Truc: Een groot deel van het proces houdt in dat gegevens worden geschud (zoals het herschikken van kaarten in een deck). Normaal gesproken vereist dit veel tijdelijke opslagruimte (scratchpads) en kost het veel tijd.
- De Innovatie: De auteurs ontdekten een specifiek patroon in hoe de gegevens worden geschud. In plaats van een rommelige, algemene schudmachine te gebruiken, bouwden ze een speciaal transportband dat precies dit patroon volgt.
- Het Voordeel: Deze aangepaste band is twee keer zo snel en vereist de helft van de ruimte van eerdere ontwerpen, omdat het niet hoeft te stoppen om gegevens in tijdelijke buffers op te slaan.

4. De Geheugenoptimalisatie: De "Just-in-Time" Keuken

Het artikel herschreef ook het gegevenspad om trips naar de "supermarkt" (geheugen buiten de chip) te minimaliseren.

De Strategie: Ze splitsten de berekening op in zes distincte fasen. In elke fase laden ze precies wat nodig is, voeren ze al het werk uit met die gegevens terwijl het op het aanrecht ligt (geheugen op de chip), en pas daarna gaan ze naar de volgende fase.
Het Resultaat: Dit voorkomt dat het systeem constant gegevens ophaalt. In vergelijking met de beste eerdere ontwerpen verlaagde deze aanpak de hoeveelheid opgehaalde gegevens uit het externe magazijn met 2,9 tot 4,2 keer.

De Conclusie

De auteurs testten hun nieuwe systeem op een high-end chip (Xilinx Virtex UltraScale+). In vergelijking met de beste bestaande hardware-accelerators voor deze taak:

Snelheid: Ze maakten de berekening 5,8 keer sneller (in termen van pure rekentijd).
Efficiëntie: Ze verlaagden de behoefte om gegevens op te halen uit extern geheugen met 2,9 keer.
Kosten: Ze bereikten dit zonder aanzienlijk meer hardwarebronnen (chips en geheugen) nodig te hebben dan de vorige beste ontwerpen.

Kortom, ze vonden een slimmere manier om het werk te organiseren en bouwden een gespecialiseerd gereedschap om het te doen, waardoor een langzaam, file-geplagend proces werd omgezet in een gestroomlijnde, hoogwaardige operatie.

Technische Samenvatting: Triple-Hoisted Baby-Step Giant-Step Lineaire Transformatie over CKKS Homomorf Versleuteling en Hardware-versneller

Probleemstelling
Homomorf Versleuteling (HE), met name het CKKS-schema, maakt privacybehoudende berekeningen op versleutelde data mogelijk, wat cruciaal is voor toepassingen zoals medische diagnose, financiële analyse en genoomsequencing. Een fundamentele bewerking in op HE gebaseerde neurale netwerken en transformers is de Lineaire Transformatie (HE-LT). Hoewel de diagonale methode HE-LT mogelijk maakt door matrixdiagonalen te packen in polynomen, vereist deze methode een verbodsbare hoeveelheid ciphertext-rotaties voor hoogdimensionale matrices. Deze rotaties omvatten complexe automorfisme- en key-switching-bewerkingen, wat leidt tot aanzienlijke rekenkundige overhead en massale toegang tot off-chip geheugen. Bestaande hardware-versnellers, zelfs die welke gebruikmaken van Baby-Step Giant-Step (BSGS)-decompositie en double-hoisting-technieken, lijden nog steeds onder aanzienlijke latentie en bandbreedte-bottlenecks in het geheugen, waarbij vaak honderden gigabytes aan off-chip datatransfer nodig zijn voor typische parametersets.

Methodologie
Het artikel stelt een uitgebreide oplossing voor die zowel de algoritmische complexiteit als de hardware-datastroom aanpakt:

Triple-Hoisted BSGS (TH-BSGS) Algoritme:
De auteurs breiden het bestaande double-hoisted BSGS-algoritme uit door de "baby step" verder te decomponeren in twee lagen, waardoor een drie-laags structuur ontstaat ( $n = n'_1 n'_2 n'_3$ ).
- Triple Hoisting: De techniek wordt toegepast over alle drie de lagen van rotaties. Door berekeningen te herschikken en inverse automorfismen toe te passen op switching keys, zorgt het algoritme ervoor dat de Decompose-bewerking (een kostbare key-switching-stap) slechts één keer wordt uitgevoerd voor alle binnenrotaties in een laag.
- Vertraagde ModDown: Net als bij eerdere hoisting-methoden worden de ModDown-bewerkingen vertraagd en gecombineerd. In het voorgestelde ontwerp wordt ModDown alleen toegepast op geaccumuleerde sommen in plaats van op tussentijdse producten, wat het aantal vereiste modulaire bewerkingen aanzienlijk vermindert.
- Flexibiliteit in Afwegingen: Door de decompositiefactoren $n'_1, n'_2, n'_3$ af te stemmen, staat het algoritme flexibele afwegingen toe tussen het aantal vereiste switching keys (geheugen) en de rekenkundige complexiteit.
Geheugen-geoptimaliseerd Data-pad:
Om de latentie veroorzaakt door toegang tot off-chip geheugen aan te pakken, wordt het TH-BSGS-algoritme opgedeeld in zes distincte fasen.
- Fase-indeling: Het algoritme wordt herstructureerd zodat data uit off-chip geheugen wordt gelezen, wordt verwerkt met tussentijdse resultaten die on-chip worden opgeslagen en hergebruikt, en pas aan het einde van elke fase wordt teruggeschreven.
- Data-hergebruik: Het ontwerp maximaliseert on-chip geheugengebruik door het laden van switching keys en polynoom-leden zorgvuldig te plannen. Bijvoorbeeld, in de middelste lagen worden switching keys in on-chip geheugen geladen en hergebruikt over meerdere iteraties om het verkeer te minimaliseren.
- Afstemming van Parallelisme: Zes parallelismeparameters ( $m_1$ tot en met $m_6$ ) worden geïntroduceerd om de verwerking van switching keys, polynoom-leden en ciphertexts in evenwicht te brengen, zodat het ontwerp binnen de beperkingen van FPGA on-chip geheugen past (bijvoorbeeld 43 MB op Xilinx U280).
Hardware-versneller Architectuur:
Er is een efficiënte FPGA-gebaseerde versneller ontworpen om het voorgestelde algoritme te implementeren.
- Geoptimaliseerde Permutatiecircuit: Er wordt een nieuw permutatiecircuit geïntroduceerd om de automorfisme $\phi_r$ te implementeren. Door gebruik te maken van de specifieke eigenschappen van de automorfisme in het NTT-domein en de bit-omgekeerde opslagvolgorde van coëfficiënten, reduceert het ontwerp het aantal multiplexers met de helft ten opzichte van eerdere werken en elimineert het de behoefte aan scratchpad-geheugenbuffers. Dit halveert de latentie van de permutatiebewerking.
- Modulaire Componenten: De architectuur omvat een Processing Element (PE)-array die NTT, INTT en coëfficiëntgewijze bewerkingen ondersteunt; een Tree Adder (TA)-array voor sommaties; en een Permutation Circuit (PC)-array.

Belangrijkste Bijdragen

Algoritmische Innovatie: Het voorstellen van het Triple-Hoisted BSGS-algoritme, dat de baby step verder decomponeert om het aantal ciphertext-rotaties en Decompose-bewerkingen te verminderen in vergelijking met de double-hoisted aanpak.
Optimalisatie van Data-pad: Een op fasen gebaseerde geheugenoptimalisatiestrategie die het verkeer naar off-chip geheugen drastisch reduceert door on-chip datahergebruik te maximaliseren, specifiek toegespitst op de herschikte berekeningen van het TH-BSGS-algoritme.
Hardware-efficiëntie: De ontwikkeling van een hardware-versneller met een vereenvoudigd permutatiecircuit dat de latentie van automorfisme met 50% reduceert en extra geheugenbuffering elimineert.

Experimentele Resultaten
Het ontwerp is gesynthetiseerd op Xilinx Virtex UltraScale+ (U280) apparaten en geëvalueerd tegen state-of-the-art hardware-versnellers (waaronder FAME, CHAM en ontwerpen uit [25]) onder drie verschillende HE-parametersets (Set-A, Set-B, Set-C) die 128-bit beveiliging ondersteunen.

Toegang tot Off-chip Geheugen: Het voorgestelde ontwerp reduceert de toegang tot off-chip geheugen met 2,9× tot 4,2× in vergelijking met het beste eerdere ontwerp (FAME) onder dezelfde parameterinstellingen. In vergelijking met de diagonale methode bereiken de verbeteringen tot 10,6× in reductie van geheugentoegang.
Rekenkundige Latentie: De voorgestelde versneller bereikt een reductie in rekenkundige latentie van 2,9× tot 10,6× in vergelijking met eerdere hardware-versnellers.
Resourcegebruik: Het ontwerp behoudt hardware-resourcevereisten (LUTs, FFs, DSPs, BRAMs) die vergelijkbaar zijn met of licht beter zijn dan bestaande oplossingen, ondanks de aanzienlijke prestatiewinst.
Algoritmische Vergelijking: Hoewel het TH-BSGS-algoritme de geheugenvereiste voor switching keys met ongeveer 3,65× reduceert in vergelijking met het double-hoisted BSGS (DH-BSGS) algoritme, blijft de totale rekenkundige complexiteit vergelijkbaar met DH-BSGS en BSGS, omdat polynoomvermenigvuldigingen de totale complexiteit domineren.

Betekenis
Het artikel stelt dat het voorgestelde TH-BSGS-algoritme en de bijbehorende hardware-versneller een aanzienlijke vooruitgang vertegenwoordigen in de efficiëntie van HE-LT. Door tegelijkertijd de algoritmische overhead van key switching en de hardware-bottleneck van toegang tot off-chip geheugen aan te pakken, maakt het ontwerp snellere en meer schaalbare privacybehoudende lineaire transformaties mogelijk. De reductie in off-chip geheugentrafiek is bijzonder kritiek, aangezien datatransfers het grootste deel van de latentie in HE-LT-bewerkingen uitmaken. Het werk toont aan dat verdere decompositie van de baby step, gecombineerd met rigoureuze data-pad-optimalisatie en gespecialiseerde hardware, aanzienlijke prestatieverbeteringen kan opleveren zonder de hardware-resourcekosten te verhogen. Toekomstig werk wordt opgemerkt om zich te richten op verdere optimalisatie van lineaire transformaties voor specifieke toepassingen.

1. Het Probleem: Het "Zware Tillen" van het Verplaatsen van Gegevens

2. De Oplossing: Het "Drie-Voudig Hijs" Liftsysteem

3. De Hardware: Een Aangepaste "Assemblagelijn"

4. De Geheugenoptimalisatie: De "Just-in-Time" Keuken

De Conclusie

Meer zoals dit