💻 computer science

Vectorized SQIsign Implementation Using AVX-512

This paper presents the first comprehensive AVX-512 vectorized implementation of the SQIsign digital signature scheme, achieving significant performance speedups over reference implementations while demonstrating the long-term viability of these optimizations through Intel's upcoming AVX10 instruction set architecture.

Original authors: Weize Wang, Chutong Wang, Yu Wu, Qifan Xue, Jieyu Zheng, Yunlei Zhao

Published 2026-08-17

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Weize Wang, Chutong Wang, Yu Wu, Qifan Xue, Jieyu Zheng, Yunlei Zhao

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you are trying to send a secret message to a friend, but you know a super-smart robot from the future might be listening. To stay safe, you need a lock that even that robot can't pick. This is the world of "post-quantum cryptography," a field of science dedicated to building digital locks that can survive the arrival of powerful quantum computers. One of the most promising new locks is called SQIsign. It's like a magical puzzle based on twisting and turning shapes (mathematically known as elliptic curves) in a way that is incredibly compact but also very hard to solve. The problem is, while the puzzle is small enough to fit in your pocket, solving it takes a long time, like trying to untangle a giant ball of yarn with a tiny pair of scissors.

To make these digital locks practical for everyday use, we need to solve the puzzle much faster. This is where the paper comes in. The researchers are essentially asking: "How can we make the scissors cut through the yarn faster?" They found a way to use a special set of tools inside modern computer chips called AVX-512. Think of a normal computer processor as a chef who chops one vegetable at a time. The AVX-512 tools are like a magical knife that can chop eight vegetables simultaneously with a single swipe. The paper shows how to reorganize the entire SQIsign puzzle so that this "eight-at-a-time" knife can be used for almost every step of the process, turning a slow, tedious job into a lightning-fast one.

The Magic of the "Eight-at-a-Time" Knife

The core of this paper is a massive speed-up for the SQIsign digital signature scheme. The authors, a team from Fudan University, have built the first version of SQIsign that fully utilizes the AVX-512 instruction set, specifically a powerful feature called IFMA (Integer Fused Multiply-Add).

To understand why this matters, imagine you are a baker making thousands of cookies. The old way of doing things (the "reference implementation") was to mix the dough, roll it, cut it, and bake it one cookie at a time. Even if you were fast, the process was slow. The SQIsign algorithm is like a very complex recipe that requires a lot of mixing and rolling. The researchers realized that instead of making one cookie at a time, they could restructure their kitchen to make eight cookies at once using a single motion.

They achieved this by redesigning the "math kitchen" of the algorithm. They took the basic building blocks—like adding and multiplying huge numbers (which are the ingredients of the cryptographic puzzle)—and rewrote them to fit perfectly into the AVX-512 "eight-at-a-time" lanes. They didn't just stop at the basic math; they applied this speed-up to the entire chain of operations, including:

Elliptic Curve Operations: The twisting and turning of the shapes.
Pairing Computations: A special type of math used to verify the shapes match.
Isogeny Evaluations: The actual process of transforming one shape into another.

The Results: Speeding Up the Puzzle

When they put their new "eight-at-a-time" kitchen to the test, the results were impressive. They measured the speed against the standard version of SQIsign at NIST security level I (which is the baseline security level for protecting data).

Signing: When creating a digital signature (locking the message), their new method was 2.69 times faster.
Verification: When checking if a signature is valid (unlocking the message), it was 3.18 times faster.

They also combined their work with another technique called Qlapoti, which is like a different way of organizing the ingredients, to get these results. The paper notes that verification got a bigger boost than signing because the signing process still has to do some heavy lifting with a different type of math (quaternion algebra) that they didn't vectorize yet. However, the verification part, which relies entirely on the math they optimized, saw the maximum possible speed-up.

Debunking the "Obsolete" Myth

One interesting side note in the paper is a correction to a common misunderstanding. Some people thought the AVX-512 technology was becoming obsolete or was only for specific, expensive server computers. The authors argue strongly against this. They point out that Intel has announced a new standard called AVX10 (specifically revision 10.2), which is scheduled for widespread deployment in late 2026. This new standard will bring these powerful "eight-at-a-time" capabilities to both high-performance cores and efficiency cores in future processors. This means the speed-up techniques they developed aren't just a temporary fix for today's supercomputers; they are a long-term solution that will work on the computers of the future, ensuring that these cryptographic locks remain fast and practical for years to come.

Why This Matters

The paper doesn't just show a faster way to do math; it provides a blueprint for how to make isogeny-based cryptography (a very promising type of post-quantum security) actually usable in the real world. By showing that SIMD vectorization (the "eight-at-a-time" approach) is a critical, yet previously underused, way to speed things up, they have opened the door for other researchers to apply similar tricks to different cryptographic puzzles.

The authors are careful to note that their work is independent of other recent algorithmic improvements. This means that if someone else invents a better recipe for the cookie dough (a new algorithm), the "eight-at-a-time" knife they invented can still be used to cut the cookies faster. It's a multiplicative win: you can get the benefits of better algorithms and their faster hardware usage at the same time.

In short, this paper takes a promising but slow digital lock and polishes it until it shines, proving that with the right tools and a little bit of creative reorganization, we can make our future digital world both secure and speedy.

Technical Summary: Vectorized SQIsign Implementation Using AVX-512

Problem Statement

SQIsign is the only isogeny-based digital signature scheme submitted to the NIST Post-Quantum Cryptography standardization process. While it offers compact key and signature sizes based on the hardness of the endomorphism ring problem for supersingular elliptic curves, its practical deployment is currently hindered by computationally intensive signing procedures. The performance bottleneck resides primarily in the "curve-side" computations, which include extensive arithmetic over large prime fields ( $\mathbb{F}_p$ ) and their quadratic extensions ( $\mathbb{F}_{p^2}$ ), elliptic curve operations (point doubling and scalar multiplication), and higher-dimensional isogeny evaluations over principally polarized abelian surfaces (PPAS). Existing reference implementations rely heavily on scalar arithmetic, often utilizing the GNU Multiple Precision Arithmetic Library (GMP) for quaternion algebra components, which limits throughput.

Methodology

This paper presents the first comprehensive vectorized implementation of the "curve-side" components of SQIsign utilizing the AVX-512 Integer Fused Multiply-Add (IFMA) instruction set architecture. The authors systematically redesigned the computational stack to exploit SIMD (Single Instruction, Multiple Data) parallelism across all major algorithmic layers, while explicitly noting that the quaternion algebra components (IdealToIsogeny) remain scalar and unoptimized in this work.

Core Technical Strategies

Finite Field Arithmetic ( $\mathbb{F}_p$ and $\mathbb{F}_{p^2}$ ):
- Representation: The implementation adopts a radix- $2^{51}$ representation for field elements, decomposing them into five 51-bit limbs. This size is chosen to fit within the lower 52 bits of 64-bit lanes, preventing overflow during IFMA operations while reserving headroom for deferred reduction.
- Parallelization: An $(8 \times 1)$ -way parallelization strategy is employed at the $\mathbb{F}_p$ layer, processing eight independent field elements simultaneously within a single 512-bit ZMM register.
- Extensions: For $\mathbb{F}_{p^2}$ , the authors implement three distinct parallelization patterns— $(8 \times 1 \times 1)$ , $(4 \times 2 \times 1)$ , and $(2 \times 4 \times 1)$ —to balance throughput and register pressure depending on the specific algorithmic requirements (e.g., batch operations vs. internal component parallelism).
- Instructions: The design leverages vpmadd52luq and vpmadd52huq instructions to execute eight parallel $52 \times 52$ -bit multiplications with fused multiply-add capabilities, significantly reducing instruction counts for Montgomery multiplication and carry propagation.
Elliptic Curve Operations:
- Point Doubling: The authors optimized point doubling for both $x$ -only coordinates (Montgomery curves) and full projective coordinates (Jacobian and Modified Jacobian). For $x$ -only coordinates, they consistently omit normalization steps in vectorized contexts to maintain data flow, whereas normalization is applied only when doubling multiple points simultaneously to maximize parallelism.
- Scalar Multiplication: The implementation vectorizes the Montgomery ladder, the three-point ladder, and the two-dimensional ladder (LadderBiscalar). A key contribution is a redesigned four-way vectorization strategy for the xDBLADD function that accommodates the general $(A_{24}:C_{24})$ parameter format used in isogeny-based cryptography, avoiding the special-form dependencies of previous vectorization attempts.
- Pairings: The paper addresses the Tate-Lichtenbaum pairing computations used for basis generation. By fusing one point doubling with two differential additions, the authors created a cubicalDBLADDADD algorithm that generates required pairings using three four-way parallel multiplications and one four-way parallel squaring.
Isogeny Evaluations:
- Dimension 1 & 2: The authors applied batching strategies to isogeny evaluations. Instead of processing points sequentially, they interleave coordinates from multiple points across AVX-512 lanes to saturate SIMD multipliers. This approach is applied to both 4-isogenies on elliptic curves and $(2,2)$ -isogenies on abelian surfaces (PPAS), utilizing theta-coordinate arithmetic.
Architecture Context:
- The paper addresses misconceptions regarding AVX-512 obsolescence, noting that Intel's upcoming AVX10 architecture (revision 10.2, scheduled for late 2026) will standardize these capabilities across both performance and efficiency cores, ensuring long-term viability.

Key Contributions

Comprehensive Vectorization of SQIsign Curve-Side Operations: The work provides the first full vectorization of the "curve-side" components of SQIsign using AVX-512IFMA, covering prime-field arithmetic, quadratic extensions, elliptic curve operations (including scalar multiplication and pairings), and isogeny evaluations in both one and two dimensions. The quaternion algebra components remain scalar.
Extended Vectorization Analysis on x86-64: Unlike prior ARM-based vectorization efforts (e.g., De Feo et al. using NEON), this work explores a significantly broader range of functions on the x86-64 platform, including complex scalar multiplication strategies and theta-coordinate operations. The algorithmic designs are noted as architecture-agnostic, offering a foundation for migration to other SIMD platforms like ARM SVE or RISC-V.
Generalizable Optimizations: The techniques developed for point doubling, batched scalar multiplication, and vectorized theta-point arithmetic are presented as methodological foundations applicable to other isogeny-based cryptosystems utilizing higher-dimensional abelian varieties, independent of specific SQIsign variants.

Experimental Results

The implementation was benchmarked on an Intel Core i7-11700F CPU (2.50GHz) running Ubuntu 24.04. The results are compared against the official reference implementation (optimized for Broadwell with 64-bit limbs).

Performance Gains:
- Key Generation: Speedups ranging from $1.03\times$ to $1.28\times$ .
- Signing: Speedups ranging from $1.08\times$ to $1.26\times$ .
- Verification: Speedups ranging from $1.46\times$ to $1.84\times$ .
Combined with Qlapoti: When combined with the Qlapoti technology, the implementation achieves a $2.69\times$ speedup for signing and a $3.18\times$ improvement for verification at NIST security level I.
Verification Disparity: The paper notes that verification benefits more significantly than signing because verification relies exclusively on the vectorized curve-side operations, whereas signing still involves quaternion algebra operations currently executed via scalar GMP (a component not optimized in this work).

Significance and Claims

The authors claim that this work demonstrates that SIMD vectorization represents a critical yet underexplored optimization dimension for post-quantum isogeny-based schemes.

Independence from Algorithmic Advances: The optimizations are orthogonal to recent high-level algorithmic refinements (such as Qlapoti or Superglue). This implies that the performance gains achieved through vectorization are multiplicative; future protocol-level innovations can be applied on top of this vectorized foundation to compound performance improvements.
Long-Term Viability: By emphasizing the standardization of AVX-512 capabilities in future Intel architectures (AVX10), the paper argues that these optimization techniques are not a temporary fix but a sustainable path for efficient isogeny-based cryptography.
Universality: The methodology is claimed to be applicable across various isogeny-based constructions (e.g., SQIsignHD, SQIsign2D-East, SQIPrime) because they all rely on the same underlying primitives ( $\mathbb{F}_{p^2}$ arithmetic, theta coordinates, and elliptic curve operations) that are the targets of this optimization.

The paper concludes that while the "quaternion side" of SQIsign remains a scalar bottleneck, the vectorization of the "curve side" significantly bridges the gap between theoretical compactness and practical deployment efficiency.