Technische Samenvatting: Gevectoriseerde SQIsign Implementatie Gebruikmakend van AVX-512

Probleemstelling

SQIsign is het enige isogene digitale handtekeningschema dat is ingediend voor het NIST Post-Quantum Cryptography standaardisatieproces. Hoewel het compacte sleutel- en handtekeningsgroottes biedt op basis van de hardheid van het endomorfisme-ringprobleem voor supersinguliere elliptische curves, wordt de praktische implementatie momenteel gehinderd door computationeel intensieve ondertekeningsprocedures. De prestatie-bottleneck bevindt zich voornamelijk in de "curve-zijde" berekeningen, die uitgebreide rekenkunde over grote priemvelden ($\mathbb{F}_p$) en hun kwadratische uitbreidingen ($\mathbb{F}_{p^2}$), elliptische curve operaties (puntverdubbeling en scalaire vermenigvuldiging), en hogere-dimensie isogene evaluaties over principaal gepolariseerde abeliaanse oppervlakken (PPAS) omvatten. Bestaande referentie-implementaties vertrouwen zwaar op scalaire rekenkunde, waarbij vaak gebruik wordt gemaakt van de GNU Multiple Precision Arithmetic Library (GMP) voor quaternion-algebra componenten, wat de doorvoer beperkt.

Methodologie

Dit artikel presenteert de eerste uitgebreide gevectoriseerde implementatie van de "curve-zijde" componenten van SQIsign met behulp van de AVX-512 Integer Fused Multiply-Add (IFMA) instructie-architectuur. De auteurs hebben de computationele stack systematisch herontworpen om SIMD (Single Instruction, Multiple Data) parallellisme te exploiteren over alle belangrijke algoritmische lagen, waarbij zij expliciet vermelden dat de quaternion-algebra componenten (IdealToIsogeny) scalair blijven en niet geoptimaliseerd zijn in dit werk.

Kernstrategieën voor Techniek

1. Eindige Veldrekenkunde ($\mathbb{F}_p$ en $\mathbb{F}_{p^2}$):

   • Representatie: De implementatie hanteert een radix-$2^{51}$ representatie voor veldelementen, waarbij ze worden ontleed in vijf 51-bit limbs. Deze grootte is gekozen om binnen de onderste 52 bits van 64-bit lanes te passen, wat overflow tijdens IFMA-operaties voorkomt terwijl er ruimte overblijft voor uitgestelde reductie.
   • Parallellisering: Een $(8 \times 1)$-wijze parallelliseringsstrategie wordt toegepast op de $\mathbb{F}_p$ laag, waarbij acht onafhankelijke veldelementen simultaan worden verwerkt binnen een enkele 512-bit ZMM-register.
   • Uitbreidingen: Voor $\mathbb{F}_{p^2}$ implementeren de auteurs drie verschillende parallelliseringspatronen—$(8 \times 1 \times 1)$, $(4 \times 2 \times 1)$, en $(2 \times 4 \times 1)$—om de doorvoer en de registerdruk te balanceren afhankelijk van de specifieke algoritmische vereisten (bijv. batch-operaties versus interne component-parallellisme).
   • Instructies: Het ontwerp maakt gebruik van vpmadd52luq en vpmadd52huq instructies om acht parallelle $52 \times 52$-bit vermenigvuldigingen met fused multiply-add capaciteiten uit te voeren, wat het aantal instructies voor Montgomery-reductie en carry-propagatie aanzienlijk vermindert.

2. Elliptische Curve Operaties:

   • Puntverdubbeling: De auteurs hebben puntverdubbeling geoptimaliseerd voor zowel $x$-alleen coördinaten (Montgomery curves) als volledige projectieve coördinaten (Jacobian en Modified Jacobian). Voor $x$-alleen coördinaten laten zij consistent normalisatiestappen weg in gevectoriseerde contexten om de datastroom te behouden, terwijl normalisatie alleen wordt toegepast wanneer meerdere punten simultaan worden verdubbeld om parallellisme te maximaleren.
   • Scalaire Vermenigvuldiging: De implementatie vectoriseert de Montgomery ladder, de drie-punts ladder, en de twee-dimensionale ladder (LadderBiscalar). Een sleutelbijdrage is een herontworpen vier-wijze vectorisatie strategie voor de xDBLADD functie die rekening houdt met het algemene $(A_{24}:C_{24})$ parameterformaat dat gebruikt wordt in isogene cryptografie, waardoor afhankelijkheden van speciale vormen uit eerdere vectorisatiepogingen worden vermeden.
   • Pairings: Het artikel behandelt de Tate-Lichtenbaum pairing berekeningen die worden gebruikt voor basisgeneratie. Door één puntverdubbeling te fuseren met twee differentiële addities, hebben de auteurs een cubielDBLADDADD algoritme gecreëerd dat vereiste pairings genereert met behulp van drie vier-wijze parallelle vermenigvuldigingen en één vier-wijze parallelle kwadratische operatie.

3. Isogene Evaluaties:

   • Dimensie 1 & 2: De auteurs hebben batching-strategieën toegepast op isogene evaluaties. In plaats van punten sequentieel te verwerken, worden coördinaten van meerdere punten geïnterleavederd over AVX-512 lanes om de SIMD-multipliers te verzadigen. Deze aanpak wordt toegepast op zowel 4-isogenen op elliptische curves als (2,2)-isogenen op abeliaanse oppervlakken (PPAS), gebruikmakend van theta-coördinaat rekenkunde.

4. Architectuurcontext:

   • Het artikel adresseert misvattingen over de veroudering van AVX-512, waarbij wordt opgemerkt dat de aankomende Intel AVX10 architectuur (revisie 10.2, gepland voor eind 2026) deze capaciteiten zal standaardiseren over zowel performance als efficiency cores, wat de langetermijnlevensvatbaarheid garandeert.

Belangrijkste Bijdragen

1. Uitgebreide Vectorisatie van SQIsign Curve-Zijde Operaties: Het werk biedt de eerste volledige vectorisatie van de "curve-zijde" componenten van SQIsign met behruik van AVX-512IFMA, dekkend van priemveld-rekenkunde, kwadratische uitbreidingen, elliptische curve operaties (inclusclusief scalaire vermenigvuldiging en pairings), en isogene evaluaties in zowel één als twee dimensies. De quaternion-algebra componenten blijven scalair.
2. Uitgebreide Vectorisatie Analyse op x86-64: In tegen tegenstelling tot eerdere ARM-gebaseerde vectorisatie-inspanningen (bijv. De Feo et al. met NEON), verkent dit werk een aanzienlijk breder scala aan functies op het x86-64 platform, inclusief complexe scalaire vermenigvuldigingsstrategieën en theta-coördinaat operaties. De algoritmische ontwerpen worden als architectuur-agnostisch beschouwd, wat een fundament biedt voor migratie naar andere SIMD-platformen zoals ARM SVE of RISC-V.
3. Generaliseerbare Optimalisaties: De technieken ontwikkeld voor puntverdubbeling, gebatchte scalaire vermenigvuldiging en gevectoriseerde theta-punt rekenkunde worden gepresenteerd als methodologische fundamenten die toepasbaar zijn op andere isogene cryptosystemen die hogere-dimensie abeliaanse variëteiten gebruiken, onafhankelijk van specifieke SQIsign varianten.

Experimentele Resultaten

De implementatie is gebenchmarkt op een Intel Core i7-11700F CPU (2.50GHz) draaiend op Ubuntu 24.04. De resultaten worden vergeleken met de officiële referentie-implementatie (geoptimaliseerd voor Broadwell met 64-bit limbs).

• Prestatiewinst:
  • Sleutelgeneratie: Versnellingen variërend van $1.03\times$ tot $1.28\times$.
  • Ondertekening (Signing): Versnellingen variërend van $1.08\times$ tot $1.26\times$.
  • Verificatie: Versnellingen variërend van $1.46\times$ tot $1.84\times$.
• Gecombineerd met Qlapoti: Wanneer gecombineerd met de Qlapoti technologie, bereikt de implementatie een $2.69\times$ versnelling voor ondertekening en een $3.18\times$ verbetering voor verificatie bij NIST beveiligingsniveau I.
• Verificatie Dispariteit: Het artikel merkt op dat verificatie meer profiteert dan ondertekening, omdat verificatie uitsluitend steunt op de gevectoriseerde curve-zijde operaties, terwijl ondertekening nog steeds quaternion-algebra operaties bevat die momenteel via scalaire GMP worden uitgevoerd (een component die niet geoptimaliseerd is in dit werk).

Betekenis en Claims

De auteurs claimen dat dit werk aantoont dat SIMD vectorisatie een kritieke maar onderbelichte optimalisatiedimensie is voor post-kwantum isogene schema's.

• Onafhankelijkheid van Algoritmische Vooruitgang: De optimalisaties zijn orthogonaal aan recente hoog-niveau algoritmische verfijningen (zoals Qlapoti of Superglue). Dit impliceert dat de prestatiewinst behaald door vectorisatie multiplicatief is; toekomstige protocol-niveau innovaties kunnen worden toegepast op dit gevectoriseerde fundament om prestatieverbeteringen te stapelen.
• Langetermijnlevensvatbaarheid: Door de nadruk te leggen op de standaardisatie van AVX-512 capaciteiten in toekomstige Intel-architecturen (AVX10), betogen de auteurs dat deze optimalisatietechnieken geen tijdelijke oplossing zijn, maar een duurzaam pad voor efficiënte isogene cryptografie.
• Universaliteit: De methodologie wordt geclaimd toepasbaar te zijn op diverse isogene constructies (bijv. SQIsignHD, SQIsign2D-East, SQIPrime), omdat ze allemaal steunen op dezelfde onderliggende primitieven ($\mathbb{F}_{p^2}$ rekenkunde, theta coördinaten, en elliptische curve operaties) die de doelwitten van deze optimalisatie zijn.

Het artikel concludeert dat hoewel de "quaternion-zijde" van SQIsign een scalaire bottleneck blijft, de vectorisatie van de "curve-zijde" de kloof tussen theoretische compactheid en praktische implementatie-efficiëntie aanzienlijk verkleint.