💻 computer science

Multi-Input Ciphertext Multiplication for Homomorphic Encryption

Dit artikel stelt een geoptimaliseerde methode voor vermenigvuldiging van meervoudige invoerciferteksten voor homomorfische encryptie voor die verder gaat dan twee invoeren door hervormde berekeningen, extra evaluatiesleutels en een meerlagige herschaling, wat resulteert in hardware-architecturen die de logische oppervlakte en latentie aanzienlijk verminderen in vergelijking met eerdere ontwerpen.

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 meesterkok bent die een taart probeert te bakken, maar er zit een addertje onder het gras: je moet alle meng- en bakwerk doen terwijl je dikke, zware ovenwanten draagt die je beletten de ingrediënten te voelen of de kom te zien. Dit is Homomorf Versleuteling (HE). Het stelt computers in staat om wiskunde te verrichten op "versleutelde" data (het taartbeslag in de wanten) zonder het ooit te ontsleutelen (de wanten af te doen). Dit houdt geheimen veilig, of het nu gaat om je medische dossiers of je banksaldo.

Het uitvoeren van wiskunde met deze "wanten" is echter ontzettend traag en rommelig. De grootste bottleneck is vermenigvuldiging. Bij standaard versleuteling kun je maar twee ingrediënten tegelijk vermenigvuldigen. Maar veel moderne taken, zoals het trainen van een AI om een ziekte te herkennen of het analyseren van complexe financiële trends, vereisen dat vele ingrediënten (ciphertexts) tegelijk met elkaar worden vermenigvuldigd.

Dit artikel introduceert een nieuwe, super-efficiënte manier om deze versleutelde ingrediënten te vermenigvuldigen, specifiek voor een populaire versleutelmethode genaamd CKKS. Hier is de uiteenzetting van hun doorbraak met behulp van eenvoudige analogieën:

1. Het Probleem: De "Rommelige Keuken"

Wanneer je versleutelde getallen vermenigvuldigt, wordt het "ruis" (de rommeligheid die door de ovenwanten wordt veroorzaakt) steeds luider. Als je te veel getallen tegelijk vermenigvuldigt zonder op te ruimen, verdringt de ruis de daadwerkelijke data en wordt het resultaat onbruikbaar.

Om dit op te lossen, moet het versleutelingssysteem na elke vermenigvuldiging een "opruim"-stap uitvoeren die Rescaling (herschaal) wordt genoemd. Denk hierbij aan het stoppen om het aanrecht af te vegen en de ingrediënten weer op orde te brengen.

De Oude Manier: Als je 10 ingrediënten moest vermenigvuldigen, was de oude methode als een lopende band waarbij je twee vermenigvuldigde, stopte om op te ruimen, nog twee vermenigvuldigde, weer stopte om op te ruimen, en zo verder. Het was traag en vereiste veel schoonmaakmiddelen (hardware-resources).
De Eerdere "Drie-Ingrediënten"-Poging: Het eerdere werk van de auteurs toonde aan dat je drie ingrediënten tegelijk kon vermenigvuldigen, wat sneller was. Maar het had nog steeds veel onnodige opruimstappen.

2. De Oplossing: De "Slimme Assemblagelijn"

De auteurs stellen twee grote upgrades voor om dit proces sneller en kleiner te maken:

A. De "Een-Staps-Opruiming" (Verbeterde 3-Invoer Vermenigvuldiging)

In hun nieuwe ontwerp voor het vermenigvuldigen van drie ingrediënten, realiseerden ze zich dat ze het opruimen (Rescaling) en het opnieuw ordenen (Relinearization) op een onhandige, omweg-methode deden.

De Analogie: Stel je voor dat je drie kommen beslag hebt. De oude methode was om ze te mengen, het mengsel in een nieuwe kom te gieten, de oude kommen schoon te maken, het mengsel opnieuw te gieten en weer schoon te maken.
De Oplossing: Ze hebben het proces zo herontworpen dat je kunt mengen en opruimen in één vloeiende beweging. Ze hebben uitgevonden hoe ze de opruimstappen kunnen combineren, zodat je niet zo vaak hoeft te stoppen om het aanrecht af te vegen.
Het Resultaat: Hun nieuwe "drie-kom mixer" is 50% sneller (latentie) en neemt 15% minder ruimte in beslag op de chip (oppervlakte) in vergelijking met hun vorige beste ontwerp.

B. De "Groepsopruiming" (Multi-Invoer Vermenigvuldiging)

Wat als je vier, vijf of zelfs twaalf ingrediënten tegelijk moet vermenigvuldigen?

De Oude Manier: Je zou een lange lijn van "twee-kom mixers" bouwen. Je mengt twee, maakt schoon, mengt twee meer, maakt schoon, mengt vervolgens de resultaten en maakt weer schoon. Dit creëert een zeer lange lijn (hoge "vermenigvuldigingsdiepte"), wat betekent dat de ruis te snel opbouwt.
De Nieuwe Strategie: De auteurs realiseerden zich dat als je je ingrediënten anders groepeert, je een "Groepsopruiming" kunt doen.
- In plaats van na elke enkele stap schoon te maken, hebben ze een wiskundige truc ontwikkeld (genaamd Multi-Rescaling) die het mogelijk maakt om te wachten en meerdere lagen rommel tegelijk op te ruimen.
- De Analogie: Stel je voor dat je borden wast. In plaats van een bord te wassen, het te drogen en weg te zetten, en dan een kopje te wassen, te drogen en weg te zetten, was je een hele stapel borden, droog je de hele stapel en zet je ze allemaal weg. Je doet het "drogen" (het dure, trage deel) slechts één keer voor de hele groep.
Het Resultaat: Door te herschikken hoe ze de ingrediënten groeperen (de "partitionering"), kunnen ze deze opruimstappen combineren. Voor het vermenigvuldigen van 4 tot 12 ingrediënten bespaart hun nieuwe methode 32% van de ruimte en halveert de tijd (45% sneller) in vergelijking met de oude "twee-voor-twee"-lijn.

3. Waarom Dit Belangrijk Is (Volgens Het Artikel)

Het artikel richt zich strikt op de hardware-architectuur — het fysieke ontwerp van de computerchip die deze wiskunde uitvoert.

Ze bewezen dat door te veranderen hoe de wiskunde is georganiseerd (het algoritme) en hoe de chip is gebouwd (de architectuur), je complexe versleutelde wiskunde veel sneller kunt uitvoeren.
Ze noemen specifiek dat dit helpt bij toepassingen zoals machine learning, medische diagnose en financiële analyse, omdat deze velden vaak vereisen dat veel versleutelde datapunten met elkaar worden vermenigvuldigd.

Samenvatting

Beschouw dit artikel als het uitvinden van een nieuwe, super-efficiënte keuken voor een kok die zijn ovenwanten niet kan uittrekken.

Ze bedachten hoe ze drie ingrediënten tegelijk konden mengen zonder rommel te maken.
Ze bedachten een manier om meerdere lagen rommel tegelijk op te ruimen, in plaats van één voor één.
Het resultaat is een keuken die kleiner, sneller en minder energie vereist om geheimen veilig te houden tijdens het uitvoeren van complexe wiskunde.

De auteurs hebben dit in dit artikel niet getest op echte patiënten of echte bankrekeningen; ze bewezen alleen dat de machine die is ontworpen om dit werk te doen, aanzienlijk beter is dan de machines die we eerder hadden.

Technische Samenvatting: Vermenigvuldiging van Ciferteksten met Meerdere Invoeren voor Homomorf Versleutelen

Probleemstelling
Homomorf versleutelen (HE), met name het RNS-CKKS-schema, stelt rekenkundige bewerkingen op versleutelde gegevens mogelijk, wat cruciaal is voor privacybehoudende toepassingen zoals machine learning en medische diagnose. Standaard HE-schema's definiëren echter ciphertext-vermenigvuldiging uitsluitend voor twee invoeren. Veel praktische toepassingen, zoals benaderingen van hogere orde polynomen voor activatiefuncties in neurale netwerken (bijv. ReLU), beslissingsbomen en genoomsequencing, vereisen de vermenigvuldiging van meerdere ciphertexts ( $n > 2$ ).

Bestaande benaderingen om vermenigvuldiging met meerdere invoeren te verwerken, koppelen doorgaans meerdere vermenigvuldigers voor twee invoeren in een binaire boomstructuur. Deze methode lijdt aan twee primaire inefficiënties:

Hoge Latentie en Oppervlakte: Het sequentieel vermenigvuldigen van $n$ ciphertexts met behulp van eenheden voor twee invoeren resulteert in aanzienlijke hardware- overhead en latentie.
Ruisgroei en Overhead voor Opnieuw Schalen: Elke vermenigvuldiging verhoogt het ruisniveau, wat een opnieuw schalen (rescaling) vereist om de berichtschaal te herstellen. In een standaard binaire boom moet opnieuw schalen plaatsvinden na elke vermenigvuldigingsstap om exponentiële ruisgroei te voorkomen. Dit resulteert in een groot aantal eenheden voor opnieuw schalen, die elk dure operaties voor het Getaltheoretische Transformatie (NTT) en de Inverse NTT (INTT) vereisen, wat de computationele complexiteit en het gebruik van hardwarebronnen aanzienlijk verhoogt.

Methodologie
Het artikel stelt een raamwerk voor directe vermenigvuldiging van ciphertexts met $n$ invoeren voor die de vermenigvuldigingsdiepte en de hardwarecomplexiteit minimaliseert. De methodologie is verdeeld in twee hoofdcontributies:

Verbeterde Vermenigvuldiger voor Drie Invoeren:
De auteurs herformuleren eerst het proces voor vermenigvuldiging met drie invoeren. In het voorlopige werk [26] werden relinearisatie en opnieuw schalen afzonderlijk uitgevoerd, wat meerdere ModUp/ModDown-operaties en talrijke (I)NTT-blokken vereiste. Het nieuwe ontwerp:
- Herformuleert Relinearisatie: Door de $P^{-1}$ -schaalfactor naar de basisconversie (BConv) en de vermenigvuldiging met de evaluatiesleutel te verplaatsen, elimineert het ontwerp afzonderlijke schaalstappen.
- Optimaliseert Opnieuw Schalen: De auteurs herschikken het datapad om opnieuw schalen uit te voeren in het oorspronkelijke domein voordat de definitieve NTT plaatsvindt, in plaats van in het NTT-domein. Dit maakt het elimineren van overbodige (I)NTT-operaties mogelijk.
- Resultaat: Deze wijzigingen verminderen het aantal (I)NTT-blokken in het datapad van acht naar vier, waardoor de lengte van het datapad effectief wordt gehalveerd.
Extensie voor Meerdere Invoeren met Gecombineerd Opnieuw Schalen:
Om vermenigvuldiging uit te breiden naar $n > 3$ invoeren zonder de vermenigvuldigingsdiepte te verhogen, introduceert het artikel:
- Gegenereerde Evaluatiesleutels: Er worden nieuwe evaluatiesleutels ( $ek_t$ ) geïntroduceerd om de hogere graad polynoomtermen ( $d_t s^t$ ) die worden gegenereerd door het vermenigvuldigen van $n$ ciphertexts te relineariseren, waardoor het resultaat terug wordt gebracht naar een formaat met twee polynomen.
- Multi-Rescaling (Multi-RS) Algoritme: Een theoretische analyse identificeert voorwaarden waaronder meerdere schaaloperaties kunnen worden uitgesteld en gecombineerd. De auteurs stellen een algoritme voor dat $\mu$ aaneengesloten schaaloperaties uitvoert met hetzelfde aantal (I)NTT-operaties als een enkele schaaloperatie. Dit wordt bereikt door de invoer te transformeren naar het INTT-domein, iteratief opnieuw te schalen in het coëfficiëntdomein en terug te transformeren, waarbij voorgecomputeerde constanten worden gebruikt om de operaties samen te voegen.
- Richtlijnen voor Invoerpartitie: Het artikel biedt richtlijnen voor het partitioneren van $n$ invoeren in groepen (bijv. $(n_1, n_2, \dots, n_m)$ ) om het aantal gecombineerde schaaloperaties te maximaliseren terwijl de optimale vermenigvuldigingsdiepte van $\lceil \log_2 n \rceil$ wordt behouden. Dit houdt het creëren van onbalansboomstructuren in waar mogelijk, om meer invoeren te groeperen voordat een schaalstap plaatsvindt.

Belangrijkste Contributies

Algoritmische Herformulering: Een nieuwe formulering voor vermenigvuldiging met drie invoeren die tussenberekeningen combineert, het aantal (I)NTT-operaties vermindert en het datapad verkort.
Raamwerk voor Meerdere Invoeren: Een uitbreiding van ciphertext-vermenigvuldiging naar willekeurige $n$ invoeren met behulp van gegeneraliseerde evaluatiesleutels en een boomgestructureerde vermenigvuldiger.
Gecombineerd Opnieuw Schalen: Een nieuw multi-rescaling-algoritme dat de complexiteit van het uitvoeren van meerdere schaaloperaties reduceert tot die van een enkele schaaloperatie, ongeacht het aantal gecombineerde stappen ( $\mu$ ).
Hardware Architectuur: Ontwerp van volledig gepipelined hardware-architecturen voor de voorgestelde vermenigvuldigers, inclusief geoptimaliseerde ModUp-, ModDown- en schaleenheden.

Resultaten
De voorgestelde ontwerpen zijn gesynthetiseerd met het GlobalFoundries 22FDX-proces met parameters $N=2^{16}$ , $L=K=24$ en $w=64$ .

Vermenigvuldiger voor Drie Invoeren: In vergelijking met het eerdere werk [26] bereikt de verbeterde vermenigvuldiger voor drie invoeren een reductie van 15% in logisch oppervlak en een reductie van 50% in latentie. Het vermindert ook de geheugeneisen met ongeveer 20% vanwege minder (I)NTT-eenheden.
Vermenigvuldigers voor Meerdere Invoeren ( $n=4$ tot $12$): In vergelijking met een basisimplementatie die een binaire boom van vermenigvuldigers voor twee invoeren gebruikt, bereikt de voorgestelde methode een gemiddelde reductie van 32% in totaal oppervlak en een reductie van 45% in latentie.
Efficiëntie van Opnieuw Schalen: Voor invoeren die geen machten van twee zijn (bijv. $n=17$ ), reduceert de geoptimaliseerde partitie in combinatie met multi-rescaling het totale aantal schaleenheden (en bijbehorende (I)NTT-operaties) met ongeveer 47% in vergelijking met de standaard binaire boombenadering.

Betekenis
Het artikel beweert dat deze verbeteringen de bottleneck van vermenigvuldiging met meerdere invoeren in HE aanpakken, wat essentieel is voor complexe privacybehoudende toepassingen. Door de hardwarecomplexiteit en latentie van ciphertext-vermenigvuldiging te verminderen, maakt de voorgestelde architectuur de implementatie van HE in omgevingen met beperkte middelen of hoge doorvoer haalbaarder. Het werk toont aan dat door algoritmische herformulering en zorgvuldige invoerpartitie de overhead van ruisbeheer (opnieuw schalen) aanzienlijk kan worden geminimaliseerd zonder de beveiliging of correctheid van het versleutelingschema te compromitteren. De auteurs merken op dat toekomstig werk zal focussen op verdere vereenvoudiging van vermenigvuldigers voor nog grotere aantallen invoeren.