Explicit cost analysis of Toom-4 multiplication for incomplete NTT in lattice-based cryptography

Technische Samenvatting: Expliciete Kosteanalyse van Toom-4 Vermenigvuldiging voor Onvolledige NTT in Roostergebaseerde Cryptografie

Probleemstelling
Polynoomvermenigvuldiging is een fundamentele bewerking in roostergebaseerde cryptosystemen zoals Kyber (ML-KEM) en Dilithium (ML-DSA), doorgaans uitgevoerd over restklasseringen $R_q = \mathbb{F}_q[x]/\langle x^n + 1 \rangle$. Hoewel de Getaltheoretische Transformatie (NTT) een vermenigvuldigingssnelheid van $O(n \log n)$ biedt, vereist deze strikt de voorwaarde $2n \mid (q-1)$. Deze beperking limitert de parameterkeuze en kan de beveiligings- of efficiëntiedoelstellingen in gevaar brengen.

Om dit aan te pakken, introduceerden Hafiz et al. (2025) de "onvolledige NTT", die de modulusbeperking versoepelt door een afgeknotte NTT met diepte $\ell$ (waarbij $2^{\ell+1} \mid (q-1)$) uit te voeren en deze te combineren met conventionele polynoomvermenigvuldiging voor de overige subproblemen. Waar Karatsuba-vermenigvuldiging binnen dit kader goed begrepen is, is de precieze kostprijs van Toom-4-vermenigvuldiging – specifiek de constante factoren met betrekking tot optellingen en vermenigvuldigingen – niet uitgedrukt in een vorm die compatibel is met het kostmodel voor onvolledige NTT. Bestaande analyses van Toom-Cook (bijvoorbeeld Bodrato en Zanoni) richten zich op algemene optimalisatie, maar zijn niet direct geïntegreerd in het specifieke hybride kader dat vereist is voor onvolledige NTT.

Methodologie
De auteurs presenteren een concrete implementatie van Toom-4-vermenigvuldiging, afgestemd op het kader voor onvolledige NTT, en leiden een expliciet model voor het aantal bewerkingen af.

1. Implementatiestrategie: De auteurs hanteren gehele evaluatiepunten $\{0, \pm 1, \pm 2, 3, \infty\}$ om breukgetallen constanten te vermijden. Alle delingen worden uitgesteld tot een laatste schalingsstap.
2. Optimalisatie van Optelketens: Een kritiek onderdeel van de methodologie is het gebruik van optelketens om de benodigde scalaire veelvouden te berekenen tijdens de interpolatiefase. In plaats van afzonderlijke scalaire vermenigvuldigingen uit te voeren, construeren de auteurs minimale optelketens voor de doelcoëfficiënten die vereist zijn door de inverse Vandermonde-matrix. Dit maakt een systematische bepaling mogelijk van het exacte aantal benodigde optellingen en aftrekkingen.
3. Kostafleiding: De auteurs splitsen de aantallen bewerkingen op in optellingen/aftrekkingen ($A$) en vermenigvuldigingen ($M$) over het coëfficiëntenveld $\mathbb{F}_q$. Zij leiden recursieve formules af voor de Toom-4-stappen (splitsen, evalueren, recursieve vermenigvuldiging, interpoleren en her-samenstellen) en integreren deze in het gewogen kostmodel voor onvolledige NTT zoals vastgesteld door Hafiz et al.
4. Hybride Analyse: De studie analyseert hybride strategieën die Toom-4, Karatsuba en onvolledige NTT combineren. Door de gewogen kostfunctie $C_w(n; \ell, L)$ te minimaliseren (waarbij $w$ de relatieve kost van optelling ten opzichte van vermenigvuldiging is), bepalen de auteurs de optimale recursiediepte $L$ voor diverse subproblemgroottes.

Belangrijkste Bijdragen

• Expliciet Toom-4 Kostmodel: Het artikel biedt het eerste expliciete Toom-4 kostmodel dat compatibel is met het kader voor onvolledige NTT. Het detailleert de exacte aantallen optellingen en vermenigvuldigingen, inclusief constante factoren afgeleid van geoptimaliseerde optelketens.
• Verificatie van Optelketens: De auteurs leveren verificatiescripts (beschikbaar in hun repository) die de optimaliteit bevestigen van de optelketens die worden gebruikt voor de interpolatiescalar, zodat de afgeleide aantallen minimaal zijn voor de gekozen evaluatiepunten.
• Optimalisatie van Hybride Strategieën: De studie identificeert specifieke parameterbereiken waar een Toom-4/Karatsuba-hybride beter presteert dan pure Karatsuba of pure Toom-4 binnen de context van onvolledige NTT.
• Experimentele Validatie: De auteurs hebben de voorgestelde hybride methode geïmplementeerd in Python en hebben de theoretische voorspellingen gevalideerd tegen experimentele looptijden met behulp van priemmoduli die onvriendelijk zijn voor NTT (vergelijkbaar in grootte met de modulus van Dilithium, maar met beperkte 2-adische valuaties).

Resultaten
De analyse toont aan dat de effectiviteit van Toom-4 in deze context sterk afhankelijk is van de toelaatbare NTT-diepte ($\ell$) en de resulterende subproblemgrootte ($d = n/2^\ell$):

• Beperkte Diepte Regime: Wanneer de toelaatbare NTT-diepte klein is (bijvoorbeeld $\ell=0$ of $\ell=1$), zijn de subproblemen groot genoeg zodat Toom-4 aanzienlijke winsten oplevert. Bijvoorbeeld, met $n=256$ en $\ell=0$, verlaagde de hybride methode de gewogen kost met ongeveer 5% in vergelijking met pure Karatsuba en presteerde deze aanzienlijk beter dan pure Toom-4.
• Optimale Recursie: De optimale recursiediepte $L$ varieert met $d$. Voor $d \le 128$ is de optimale strategie $L=0$ (pure Karatsuba). Voor $d=256$ is $L=1$ optimaal, en voor $d \ge 512$ is $L=2$ optimaal.
• Experimentele Bevestiging: Experimenten met priemgetallen met beperkte 2-adische valuaties bevestigden het theoretische model. Wanneer de maximaal toelaatbare diepte minimaal was ($\ell_{max}=0$), presteerde de hybride methode aanzienlijk beter dan Karatsuba (bijvoorbeeld 14,182 ms versus 16,722 ms voor $n=256$). Naarmate de toelaatbare diepte toenam, nam het prestatievoordeel van de hybride methode af, om uiteindelijk te convergeren met Karatsuba wanneer de subproblemen te klein werden.

Betekenis en Claims
De auteurs claimen bescheiden dat hun primaire bijdrage geen nieuw vermenigvuldiging-algoritme is, maar een precieze analyse op constanteniveau van Toom-4, afgestemd op het kader voor onvolledige NTT. Zij stellen dat dit expliciete kostmodel een gat in de literatuur dicht, waardoor een systematische evaluatie van hybride strategieën mogelijk wordt in scenario's waar een volledige NTT niet beschikbaar is.

Het artikel concludeert dat Toom-4 het meest voordelig is in het "beperkte-diepte regime" van onvolledige NTT, specifiek wanneer de 2-adische waarde van $q-1$ de transformatiediepte beperkt. In dergelijke gevallen biedt de voorgestelde hybride strategie een meetbare prestatieverbetering ten opzichte van standaard Karatsuba-gebaseerde benaderingen. De auteurs merken op dat hun huidige implementatie in Python is geschreven en dat toekomstig werk gericht is op het optimaliseren van low-level implementaties (bijvoorbeeld in C/C++) en verdere evaluatie in concrete roostergebaseerde schema's.