Technisches Resümee: Vektorisierte SQIsign-Implementierung unter Verwendung von AVX-512

Problemstellung

SQIsign ist das einzige isogeniebasierte Digital-Signaturverfahren, das im Rahmen des NIST-Post-Quantum-Kryptographie-Standardisierungsprozesses eingereicht wurde. Obwohl es kompakte Schlüssel- und Signaturgrößen bietet, die auf der Schwierigkeit des Endomorphismenring-Problems für supersinguläre elliptische Kurven basieren, wird sein praktischer Einsatz derzeit durch rechenintensive Signaturverfahren behindert. Der Leistungsengpass liegt primlich in den „kurvenseitigen“ Berechnungen, welche umfangreiche Arithmetik über großen Primkörpern ($\mathbb{F}_p$) und deren quadratischen Erweiterungen ($\mathbb{F}_{p^2}$), Operationen auf elliptischen Kurven (Punktverdopplung und Skalarmultiplikation) sowie höherdimensionalen Isogenie-Evaluierungen über primär polarisierter abelscher Flächen (PPAS) umfassen. Bestehende Referenzimplementierungen verlassen sich stark auf skalare Arithmetik und nutzen oft die GNU Multiple Precision Arithmetic Library (GMP) für Quaternionenalgebra-Komponenten, was den Durchsatz begrenzt.

Methodik

Diese Arbeit präsentiert die erste umfassende vektorisierte Implementierung der „kurvenseitigen“ Komponenten von SQIsign unter Nutzung der AVX-512 Integer Fused Multiply-Add (IFMA) Befehlssatzarchitektur. Die Autoren haben den Stack der Berechnungen systematisch neu gestaltet, um die SIMD-Parallelität (Single Instruction, Multiple Data) über alle wesentlichen algorithmischen Schichten hinweg auszunutzen, wobei sie explizit darauf hinweisen, dass die Quaternionenalgebra-Komponenten (IdealToIsogeny) in dieser Arbeit skalar bleiben und nicht optimiert wurden.

Kerntechnische Strategien

1. Endliche Körperarithmetik ($\mathbb{F}_p$ und $\mathbb{F}_{p^2}$):

   • Repräsentation: Die Implementierung verwendet eine Radix-$2^{51}$-Repräsentation für Feldelemente, die diese in fünf 51-Bit-Limb (Teilstücke) zerlegt. Diese Größe wurde gewählt, um in die unteren 52 Bit der 64-Bit-Lanes zu passen, was Überläufe während der IFMA-Operationen verhindert und Spielraum für eine verzögerte Reduktion lässt.
   • Parallelisierung: Es wird eine $(8 \times 1)$-weg Parallelisierungsstrategie auf der $\mathbb{F}_p$-Ebene angewandt, die acht unabhängige Feldelemente gleichzeitig innerhalb eines einzelnen 512-Bit ZMM-Registers verarbeitet.
   • Erweiterungen: Für $\mathbb{F}_{p^2}$ implementieren die Autoren drei verschiedene Parallelisierungsmuster – $(8 \times 1 \times 1)$, $(4 \times 2 \times 1)$ und $(2 \times 4 \times 1)$ – um den Durchsatz und den Registerdruck je nach spezifischen algorithmischen Anforderungen (z. B. Batch-Operationen vs. interne Komponentenparallelität) auszubalancieren.
   • Instruktionen: Das Design nutzt vpmadd52luq und vpmadd52huq Instruktionen, um acht parallele $52 \times 52$-Bit-Multiplikationen mit Fused-Multiply-Add-Fähigkeiten auszuführen, was die Instruktionsanzahl für die Montgomery-Multiplikation und die Carry-Propagation signifikant reduziert.

2. Operationen auf elliptischen Kurven:

   • Punktverdopplung: Die Autoren haben die Punktverdopplung sowohl für $x$-nur-Koordinaten (Montgomery-Kurven) als auch für volle projektive Koordinaten (Jacobian und Modified Jacobian) optimiert. Für $x$-nur-Koordinaten lassen sie Normalisierungsschritte in vektorisierten Kontexten konsistent weg, um den Datenfluss aufrechtzuerhalten, während die Normalisierung nur angewendet wird, wenn mehrere Punkte gleichzeitig verdoppelt werden, um die Parallelität zu maximieren.
   • Skalarmultiplikation: Die Implementierung vektorisiert die Montgomery-Leiter, die Drei-Punkte-Leiter und die Zwei-dimensionale Leiter (LadderBiscalar). Ein wesentlicher Beitrag ist eine neu gestaltete vierwege Vektorisierungsstrategie für die xDBLADD-Funktion, die das allgemeine $(A_{24}:C_{24})$ Parameterformat berücksichtigt, welches in der isogeniebasierten Kryptographie verwendet wird, und so die Abhängigkeiten von Spezialformen früherer Vektorisierungsversuche vermeidet.
   • Pairings: Die Arbeit adressiert die Tate-Lichtenbaum-Pairing-Berechnungen, die zur Basiserzeugung verwendet werden. Durch die Fusion einer Punktverdopplung mit zwei Differenzial-Additionen haben die Autoren einen cubicalDBLADDADD-Algorithmus geschaffen, der die erforderlichen Pairings unter Verwendung von drei vierfachen parallelen Multiplikationen und einer vierfachen parallelen Quadrierung erzeugt.

3. Isogenie-Evaluierungen:

   • Dimension 1 & 2: Die Autoren haben Batching-Strategien für Isogenie-Evaluierungen angewandt. Anstatt Punkte sequenziell zu verarbeiten, werden die Koordinaten mehrerer Punkte über die AVX-512-Lanes verschachtelt, um die SIMD-Multiplizierer zu sättigen. Dieser Ansatz wird sowohl für 4-Isogenien auf elliptischen Kurven als auch für $(2,2)$-Isogenien auf abelschen Flächen (PPAS) unter Verwendung von Theta-Koordinaten-Arithmetik angewendet.

4. Architekturkontext:

   • Die Arbeit geht auf Missverständnisse bezüglich der Obsoleszenz von AVX-512 ein und stellt fest, dass Intels kommende AVX10-Architektur (Revision 10.2, geplant für Ende 2026) diese Fähigkeiten standardisieren wird, wodurch sie sowohl für Performance- als auch für Efficiency-Cores verfügbar sind, was die langfristige Lebensfähigkeit sicherstellt.

Wesentliche Beiträge

1. Umfassende Vektorisierung der SQIsign-Kurvenseitigen Operationen: Die Arbeit liefert die erste vollständige Vektorisierung der „kurvenseitigen“ Komponenten von SQIsign mittels AVX-512IFMA, die Primkörperarithmetik, quadratische Erweiterungen, Operationen auf elliptischen Kurven (einschließlich Skalarmultiplikation und Pairings) sowie Isogenie-Evaluierungen in einer und zwei Dimensionen abdeckt. Die Quaternionenalgebra-Komponenten bleiben skalar.
2. Erweiterte Vektorisierungsanalyse auf x86-64: Im Gegensatz zu früheren ARM-basierten Vektorisierungsbemühungen (z. B. De Feo et al. mit NEON) untersucht diese Arbeit ein deutlich breiteres Spektrum an Funktionen auf der x86-64 Plattform, einschließlich komplexer Skalarmultiplikationsstrategien und Theta-Koordinaten-Operationen. Die algorithmischen Designs werden als architekturagnostisch bezeichnet, was eine Grundlage für die Migration auf andere SIMD-Plattformen wie ARM SVE oder RISC-V bietet.
3. Generalisierbare Optimierungen: Die entwickelten Techniken für Punktverdopplung, gebatchte Skalarmultiplikation und vektorisierte Theta-Punkt-Arithmetik werden als methodische Grundlagen präsentiert, die für andere isogeniebasierte Kryptosysteme anwendbar sind, die höhere dimensionale abelsche Varietäten nutzen, unabhängig von spezifischen SQIsign-Varianten.

Experimentelle Ergebnisse

Die Implementierung wurde auf einem Intel Core i7-11700F CPU (2,50 GHz) unter Ubuntu 24.04 getestet. Die Ergebnisse werden mit der offiziellen Referenzimplementierung (optimiert für Broadwell mit 64-Bit-Limb) verglichen.

• Leistungsgewinne:
  • Schlüsselerzeugung: Beschleunigungen zwischen $1,03\times$ und $1,28\times$.
  • Signierung: Beschleunigungen zwischen $1,08\times$ und $1,26\times$.
  • Verifizierung: Beschleunigungen zwischen $1,46\times$ und $1,84\times$.
• In Kombination mit Qlapoti: Wenn die Implementierung mit der Qlapoti-Technologie kombiniert wird, erreicht sie eine $2,69\times$ Beschleunigung bei der Signierung und eine $3,18\times$ Verbesserung bei der Verifizierung auf NIST-Sicherheitsniveau I.
• Disparität bei der Verifizierung: Die Arbeit stellt fest, dass die Verifizierung stärker profitiert als die Signierung, da die Verifizierung ausschließlich auf den vektorisierten kurvenseitigen Operationen beruht, während die Signierung immer noch Quaternionenalgebra-Operationen beinhaltet, die derzeit über die skalare GMP ausgeführt werden (eine Komponente, die in dieser Arbeit nicht optimiert wurde).

Bedeutung und Ansprüche

Die Autoren behaupten, dass diese Arbeit zeigt, dass die SIMD-Vektorisierung eine kritische, jedoch unterexplorierte Optimierungsdimension für Post-Quanten-Isogenie-Schemata darstellt.

• Unabhängigkeit von algorithmischen Fortschritten: Die Optimierungen sind orthogonal zu jüngsten High-Level-algorithmischen Verfeinerungen (wie Qlapoti oder Superglue). Dies impliziert, dass die durch Vektorisierung erzielten Leistungsgewinne multiplikativ sind; zukünftige Protokoll-Innovationen können auf dieser vektorisierten Basis angewendet werden, um die Leistungsverbesserungen zu kumulieren.
• Langfristige Lebensfähigkeit: Durch die Betonung der Standardisierung von AVX-512-Fähigkeiten in zukünftigen Intel-Architekturen (AVX10) argumentiert das Paper, dass diese Optimierungstechniken keine temporäre Lösung, sondern ein nachhaltiger Weg für eine effiziente isogeniebasierte Kryptographie sind.
• Universalität: Die Methodik wird als anwendbar auf verschiedene isogeniebasierte Konstruktionen (z. B. SQIsignHD, SQIsign2D-East, SQIPrime) beansprucht, da diese alle auf denselben zugrunde liegenden Primitiven ($\mathbb{F}_{p^2}$-Arithmetik, Theta-Koordinaten und Operationen auf elliptischen Kurven) basieren, die Ziel dieser Optimierung sind.

Das Paper schließt mit der Feststellung, dass obwohl die „Quaternionenseite“ von SQIsign ein skalares Nadelöhr bleibt, die Vektorisierung der „Kurvenseite“ die Lücke zwischen theoretischer Kompaktheit und praktischer Einsatzeffizienz signifikant schließt.