💻 computer science

PIP-NTT: Towards a Scalable Memory-Parallelized Accelerator for Iterative NTT in PQC

Het artikel stelt PIP-NTT voor, een schaalbare en geheugen-geparalleliseerde hardwareversneller voor iteratieve Number Theoretic Transforms in post-kwantumcryptografie die gebruikmaakt van vier kleinere geheugenblokken en een vermenigvuldigingsvrije rescaling-architectuur om een aanzienlijk hogere oppervlakte-tijd-efficiëntie te bereiken vergeleken met bestaande ontwerpen.

Oorspronkelijke auteurs: Malik Imran, Ayesha Khalid, Ciara Rafferty, Safiullah Khan, Muhammad Rashid, Maire O'Neill

Gepubliceerd 2026-07-22

📖 3 min leestijd☕ Koffiepauze-leesvoer

CC BY 4.0

Oorspronkelijke auteurs: Malik Imran, Ayesha Khalid, Ciara Rafferty, Safiullah Khan, Muhammad Rashid, Maire O'Neill

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 een wereld voor waarin de sloten die je bankrekening, je privéberichten en zelfs staatsgeheimen beschermen, van papier zijn gemaakt. Decennialang hebben we vertrouwd op wiskundige puzzels, zoals het ontbinden van enorme getallen in factoren, om deze sloten veilig te houden. Maar wetenschappers hebben ontdekt dat toekomstige "quantumcomputers", die werken volgens de vreemde regels van de kwantumfysica, deze papieren sloten binnen seconden uit elkaar kunnen scheuren met een truc genaamd het algoritme van Shor. Om dit te stoppen, bouwen cryptografen nieuwe, supersterke sloten gebaseerd op "roosters" (lattices) — complexe, meerdimensionale rasters van getallen. Deze nieuwe sloten zijn de helden van de "Post-Quantum Cryptography" (PQC). Er is echter een addertje onder het gras: deze nieuwe sloten zijn ontzettend zwaar en traag in gebruik omdat ze enorme hoeveelheden rekenwerk vereisen. Om ze praktisch te maken voor je telefoon of een slimme thermostaat, moeten we speciale, razendsnelle hardware-engines bouwen die deze berekeningen efficiënt kunnen uitvoeren zonder de batterij leeg te trekken of te veel ruimte in beslag te nemen. Dit is de uitdaging waar een team onderzoekers zich mee bezighoudt, die deze nieuwe digitale sloten snel genoeg willen maken voor de echte wereld.

Het artikel dat je nu gaat lezen, introduceert een nieuwe hardware-engine genaamd PIP-NTT, ontworpen om een specifieke, cruciale wiskundige operatie te versnellen genaamd de Number Theoretic Transform (NTT). Beschouw de NTT als een magische lopende band die een stapel getallen herschikt, zodat ze direct met elkaar vermenigvuldigd kunnen worden. In de wereld van roostergebaseerde cryptografie (zoals het onlangs door NIST gestandaardiseerde ML-KEM-schema) is deze operatie de hartslag van het systeem. Als de NTT traag is, komt het hele beveiligingssysteem tot stilstand. De onderzoekers merkten op dat bestaande engines voor deze taak vaak vastzaten aan een "pingpong"-geheugensysteem, waarbij gegevens heen en weer moesten springen tussen twee grote opslagbakken, wat een verkeersopstopping veroorzaakte die alles vertraagde. Ze merkten ook op dat de laatste stap van het proces een zware, energieverslindende methode gebruikte om de getallen op te schonen.

Om dit op te lossen, hebben de auteurs een slimmere, gestroomlijndere engine gebouwd. In plaats van twee gigantische opslagbakken gebruikten ze vier kleinere, snellere bakken die parallel werken, waardoor gegevens door het systeem kunnen stromen zonder in de rij te hoeven staan. Ze vervingen ook de zware schoonmaakstap door een slimme, multiplicatievrije truc die gebruikmaakt van eenvoudige optellingen en verdubbelingen, wat enorm veel ruimte en stroom bespaart. Door deze geheugentrucs te combineren met een hoog geoptimaliseerde "butterfly"-unit (de kleine rekenmachine die de eigenlijke wiskunde doet), creëerden ze een ontwerp dat zowel ongelooflijk snel als verrassend klein is. Toen ze hun creatie testten op een field-programmable gate array (FPGA) — een type chip die kan worden hergeprogrammeerd om als aangepaste hardware te fungeren — ontdekten ze dat het aanzienlijk efficiënter was dan alles wat momenteel in de literatuur te vinden is. Specifiek bereikte hun ontwerp een "Area-Time Product" (een maatstaf voor hoeveel ruimte en tijd de chip nodig heeft om een taak uit te voeren) die 2,67 keer beter was dan de meest ruimtebesparende ontwerpen en 1,48 keer beter dan de snelste high-speed ontwerpen. Het resultaat is een veelzijdige, schaalbare engine die kan helpen onze digitale toekomst te beveiligen tegen de kwantumdreiging, zonder dat dit ten koste gaat van de portemonnee of de batterij.

Technische Samenvatting: PIP-NTT: Naar een Schaalbare Geheugen-Parallelle Versneller voor Iteratieve NTT in PQC

Probleemstelling
Lattice-gebaseerde Post-Quantum Cryptografie (PQC), specifiek schema's zoals ML-KEM (Kyber) en ML-DSA (Dilithium) die door NIST zijn gestandaardiseerd, vertrouwt zwaar op de Number Theoretic Transform (NTT) voor efficiënte polynoomvermenigvuldiging. Bestaande hardwareversnellers voor iteratieve NTT staan voor een afweging tussen doorvoer en resource-utilisatie. High-throughput ontwerpen maken vaak gebruik van diepe pipelining en grote geheugenarrays of meerdere butterfly-units, wat aanzienlijke oppervlakteoverhead veroorzaakt die ongeschikt is voor resource-beperkte platforms. Daarentegen zijn area-geoptimaliseerde ontwerpen vaak afhankelijk van "ping-pong" geheugenschema's en enkele butterfly-units. Ho'ewel deze de hardwarevoetafdruk verminderen, beperken ze inherent de schaalbaarheid, parallellisme en frequentie-optimalisatie, wat leidt tot prestatiebottlenecks. Bovendien kan de herschalingstap die vereist is na de Inverse NTT (INTT) vaak kostbare modulaire vermenigvuldiging of deling omvatten, wat de kritieke padvertraging verhoogt.

Methodologie
De auteurs stellen "PIP-NTT" voor, een unieke, gepipelde en geheugen-parallelle NTT-versneller die is ontworpen om een balans te vinden tussen oppervlakte-efficiëntie en computationele doorvoer. De methodologie is gebaseerd op drie kerninnovaties:

Unified Pipelined Butterfly Unit (DSE): De auteurs voerden een uitgebreide Design Space Exploration (DSE) uit van Cooley–Tukey (CT) en Gentleman–Sande (GS) butterfly-units. Ze evalueerden acht architecturale varianten, variërend van een niet-gepipelde baseline tot ontwerpen die gebruikmaken van zowel coarse-grained als fine-grained pipelining. Het optimale ontwerp, een 8-stage gepipelde butterfly-unit (8SP-BU), integreert modulaire reductie (met behulp van de Barrett-methode) en rekenkundige operaties met registers die strategisch binnen het datapad zijn geplaatst om de werkfrequentie te maximalen terwijl de oppervlakteoverhead wordt geminimaliseerd.
Multiplicatie-vrije Rescaling: Voor de INTT-rescaling stap ( $a \cdot n^{-1} \mod q$ ), maken de auteurs gebruik van de specifieke congruentie van de Kyber-modulus ( $q=3329$ ), waarbij $n^{-1} \equiv -13 \pmod{3329}$ . In plaats van een complexe shift-add circuit of deling, implementeren zij een lichtgewicht architectuur die gebruikmaakt van modulaire verdubbelingen en optellingen om $13a$ te berekenen, gevolgd door een conditionele negatie. Dit elimineert de noodzaak van een general-purpose multiplier in deze stap.
Geheugen-Parallelisatie Strategie: Om de beperkingen van traditionele ping-pong geheugenschema's te overwinnen zonder de totale geheugengrootte te vergroten, introduceren de auteurs een techniek met vier kleinere geheugenblokken (elk van grootte $n/4$ ) in plaats van twee grotere blokken. Coëfficiënten worden in aangrenzende paren opgeslagen. Een multiplexer-gebaseerd swap-netwerk herordent de outputs op basis van de offset ( $\delta$ ) van de huidige fase. Dit maakt het mogelijk dat twee butterfly-units gelijktijdig opereren. Wanneer de offset groot is ( $\delta \ge n/4$ ), worden alle vier de geheugenblokken en beide butterfly-units gebruikt; wanneer de offset klein is ( $\delta < n/4$ ), bereikt het systeem partiële parallelliteit met twee actieve blokken. Deze strategie halveert het aantal klokcycli vergeleken met single-unit iteratieve ontwerpen terwijl dezelfde totale geheugencapaciteit behouden blijft.

Belangrijkste Bijdragen

Geoptimaliseerde Butterfly Architectuur: Een unieke CT/GS butterfly-unit die een frequentieverhoging bereikt van 46 MHz (baseline) naar 298 MHz door middel van fine-grained pipelining, met slechts een 1,32× oppervlakteoverhead.
Efficiënte Rescaling: Een multiplicatie-vrije rescaling architectuur voor de INTT die het gebruik van Slices en LUT's respectievelijk met 1,67× en 1,84× vermindert vergeleken met een standaard 7-term shift-add implementatie.
Schaalbare Geheugen Parallellisme: Een innovale geheugenorganisatie met vier $n/4$ -grote blokken en een swap-netwerk om partiële parallelliteit in iteratieve NTT mogelijk te maken, waardoor het aantal klokcycli met 50% wordt verminderd zonder de totale geheugenkosten te verhogen.
Geïntegreerde Versneller (PIP-NTT): Een volledige FPGA-implementatie die twee geoptimaliseerde butterfly-units en het geheugen-parallelisatie schema integreert, ondersteunend voor zowel Forward (FNTT) als Inverse (INTT) transformaties voor Kyber-parameters ( $n=256, q=3329$ ).

Experimentele Resultaten
Het PIP-NTT ontwerp werd geïmplementeerd op Xilinx Virtex-7 en Artix-7 FPGA platforms.

Prestaties: De versneller werkt op 200 MHz en berekent een enkele FNTT of INT in 2,60 µs (520 klokcycli).
Efficiëntie: In termen van de Area-Time Product (ATP), bereikt PIP-NTT:
- 2,67× hogere efficiëntie vergeleken met de meest oppervlakte-geoptimaliseerde NTT-versnellers in de literatuur.
- 1,48× hogere efficiëntie vergeleken met de meest high-speed NTT-versnellers.
Resource Gebruik: Het ontwerp gebruikt 156 slices, 426 LUT's en 379 Flip-Flops op de Virtex-7, wat een zeer compacte voetafdruk demonstreert in verhouding tot de doorvoer.

Betekenis en Claims
Het artikel claimt dat PIP-NTT een veelzijdige oplossing biedt voor toekomstige cryptografische hardware door effectief de schaalbaarheid en efficiëntie-afwegingen aan te pakken die inherent zijn aan iteratieve NTT-ontwerpen. Door parallellisme te ontkoppelen van de totale geheugenkosten via de voorgestelde geheugen-parallelisatie strategie, maakt het ontwerp hoge doorvoer mogelijk onder strikte oppervlaktebeperkingen. De auteurs benadrukken dat de architectuur niet beperkt is tot Kyber; de radix- en schema-agnostische aard van de geheugenstrategie en het modulaire ontwerp van de butterfly-unit maken aanpassing aan andere PQC-schema's (zoals Dilithium) en variërende ringgroottes mogelijk met minimale wijzigingen. Het werk positioneert PIP-NTT als een gebalanceerde, resource-efficiënte benadering die geschikt is voor diverse implementatiescenario's, van embedded systemen tot datacenters.

Meer zoals dit