Exposing SIMD Parallelism in SQIsign: An AVX-512 Implementation

• URL: http://arxiv.org/abs/2608.13948v2
• Date: Mon, 17 Aug 2026 12:09:56 GMT
• Title: Exposing SIMD Parallelism in SQIsign: An AVX-512 Implementation
• Abstract summary: Modern isogeny-based cryptosystems spend much of their running time in finite-field, elliptic-curve, and higher-dimensional isogeny arithmetic.<n>We show that substantial SIMD parallelism can be recovered by reorganizing the arithmetic dependency graphs of higher-level primitives.
• Score: 8.28115240166203
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Modern isogeny-based cryptosystems spend much of their running time in finite-field, elliptic-curve, and higher-dimensional isogeny arithmetic. Exploiting SIMD parallelism is nontrivial: routines such as Montgomery ladders contain loop-carried dependencies, while point, pairing, and theta-coordinate formulas expose only irregular fine-grained parallelism. We show that substantial SIMD parallelism can be recovered by reorganizing the arithmetic dependency graphs of higher-level primitives rather than vectorizing field multiplication in isolation. We develop an end-to-end AVX-512IFMA implementation of SQIsign in which data remain in a radix-$2^{51}$ vector representation across most of the curve-side computation. Our redesign includes projective xDBLADD schedules, batched point doubling in several coordinate systems, a vectorized biscalar ladder, fused cubical-arithmetic pairing steps, and batched one- and two-dimensional isogeny evaluation. Relative to the reference C implementation, we achieve end-to-end speedups of $1.76\times$, $1.71\times$, and $3.18\times$ for key generation, signing, and verification at NIST level~I; combined with Qlapoti, key-generation and signing speedups rise to $2.90\times$ and $2.69\times$. We further apply the same backend and methodology to CORAL, a recent isogeny group action for post-quantum non-interactive key exchange based on two-dimensional $2$-isogenies. Across five parameter sets, this yields $1.28$--$1.40\times$ speedups for key generation and $1.92$--$2.46\times$ for shared-key computation. These results provide cross-scheme evidence that algorithm-level SIMD scheduling is a reusable optimization dimension for higher-dimensional isogeny cryptography.

Related papers

• ELiTeFormer: An Efficient Transformer for FPGAs [3.884894816711594]
  Transformer blocks are prevalent in large language model (LLM) but present deployment challenges.<n>We present ELiTeFormer, the first Transformer model architecture that unifies hybrid linear attention with ultra-low-precision (ternary) linear projections.
  arXiv  Detail & Related papers  (2026-07-04T00:52:06Z)
• Low-rank Updates in Slowly Time-varying Graphs for Spatial-Temporal Signal Interpolation [36.25340747048208]
  A crucial assumption in graph signal processing (GSP) is the existence of an underlying graph that captures the pairwise similarities between nodes.<n>For spatial-temporal data in which node-to-node similarities evolve over time, a static spatial graph is insufficient.<n>We model the graph changes in two consecutive adjacency matrices $P = W(2) - W(1)$ across time as a low-rank matrix.
  arXiv  Detail & Related papers  (2026-06-22T23:33:33Z)
• Demystifying Pipeline Parallelism: First Theory for PipeDream [53.657104889705856]
  In this paper we introduce Randomized PipeDream (PD) as a stale block-SGD abstraction that yields clean non convergence for a PD-style method.<n>We prove that the delay induced by steady-state PD grows as $S2 - S/2 + O(1)$ for $S$ stages, so the stale-read contribution scales as $(2 S4)$, equivalently $(S4/K)$ in the tuned-rate form.
  arXiv  Detail & Related papers  (2026-06-02T11:14:57Z)
• OScaR: The Occam's Razor for Extreme KV Cache Quantization in LLMs and Beyond [50.440302567029654]
  Multi-modal intelligence has made the Key-Value cache a dominant memory bottleneck for efficient deployment.<n>In this work, we revisit the inherent limitations of the per-channel quantization paradigm.<n>We propose OScaR, an accurate and lightweight KV cache compression framework for X-LLMs.
  arXiv  Detail & Related papers  (2026-05-19T10:53:03Z)
• From Continual Learning to SGD and Back: Better Rates for Continual Linear Models [50.11453013647086]
  We analyze the forgetting, i.e., loss on previously seen tasks, after $k$ iterations.<n>We develop novel last-iterate upper bounds in the realizable least squares setup.<n>We prove for the first time that randomization alone, with no task repetition, can prevent catastrophic in sufficiently long task sequences.
  arXiv  Detail & Related papers  (2025-04-06T18:39:45Z)
• Communication-Efficient, 2D Parallel Stochastic Gradient Descent for Distributed-Memory Optimization [2.2596489829928452]
  This work generalizes work on 1D $s$-step SGD and 1D Federated SGD with Averaging (FedAvg) to yield a 2D parallel SGD method (HybridSGD)<n>We implement all algorithms in C++ and MPI and evaluate their performance on a Cray EX supercomputing system.
  arXiv  Detail & Related papers  (2025-01-13T17:56:39Z)
• EPS-MoE: Expert Pipeline Scheduler for Cost-Efficient MoE Inference [49.94169109038806]
  This paper introduces EPS-MoE, a novel expert pipeline scheduler for MoE that surpasses the existing parallelism schemes.<n>Our results demonstrate at most 52.4% improvement in prefill throughput compared to existing parallel inference methods.
  arXiv  Detail & Related papers  (2024-10-16T05:17:49Z)
• Block encoding bosons by signal processing [0.0]
  We demonstrate that QSP-based techniques, such as Quantum Singular Value Transformation (QSVT) and Quantum Eigenvalue Transformation for Unitary Matrices (QETU) can themselves be efficiently utilized for BE implementation.<n>We present several examples of using QSVT and QETU algorithms, along with their combinations, to block encode Hamiltonians for lattice bosons.<n>We find that, while using QSVT for BE results in the best gate count scaling with the number of qubits per site, LOVE-LCU outperforms all other methods for operators acting on up to $lesssim11$ qubits.
  arXiv  Detail & Related papers  (2024-08-29T18:00:02Z)
• Fast computation of 2-isogenies in dimension 4 and cryptographic applications [0.0]
  We present algorithms to compute chains of $2$-isogenies between abelian varieties of dimension $ggeq 1$ with theta-coordinates of level $n=2$.<n>We are able to run a complete key recovery attack on SIDH when the endomorphism ring of the starting curve is unknown within a few seconds on a laptop.
  arXiv  Detail & Related papers  (2024-07-22T09:19:20Z)
• AdaLog: Post-Training Quantization for Vision Transformers with Adaptive Logarithm Quantizer [54.713778961605115]
  Vision Transformer (ViT) has become one of the most prevailing fundamental backbone networks in the computer vision community. We propose a novel non-uniform quantizer, dubbed the Adaptive Logarithm AdaLog (AdaLog) quantizer.
  arXiv  Detail & Related papers  (2024-07-17T18:38:48Z)
• An Efficient Algorithm for Modulus Operation and Its Hardware Implementation in Prime Number Calculation [0.0]
  The proposed algorithm use only addition, subtraction, logical, and bit shift operations.<n>It addresses scalability challenges in cryptographic applications.<n>The application of this algorithm in prime number calculation up to 500,000 shows its practical utility and performance advantages.
  arXiv  Detail & Related papers  (2024-07-17T13:24:52Z)
• Projection by Convolution: Optimal Sample Complexity for Reinforcement Learning in Continuous-Space MDPs [56.237917407785545]
  We consider the problem of learning an $varepsilon$-optimal policy in a general class of continuous-space Markov decision processes (MDPs) having smooth Bellman operators. Key to our solution is a novel projection technique based on ideas from harmonic analysis. Our result bridges the gap between two popular but conflicting perspectives on continuous-space MDPs.
  arXiv  Detail & Related papers  (2024-05-10T09:58:47Z)
• Multi-level projection with exponential parallel speedup; Application to sparse auto-encoders neural networks [2.264332709661011]
  We show that the time complexity for the $ell_1,infty$ norm is only $mathcalObig(n m big)$ for a matrix in $mathbbRntimes m$. Experiments show that our projection is $2$ times faster than the actual fastest Euclidean algorithms.
  arXiv  Detail & Related papers  (2024-05-03T13:21:49Z)
• Transformers as Support Vector Machines [54.642793677472724]
  We establish a formal equivalence between the optimization geometry of self-attention and a hard-margin SVM problem. We characterize the implicit bias of 1-layer transformers optimized with gradient descent. We believe these findings inspire the interpretation of transformers as a hierarchy of SVMs that separates and selects optimal tokens.
  arXiv  Detail & Related papers  (2023-08-31T17:57:50Z)
• GloptiNets: Scalable Non-Convex Optimization with Certificates [61.50835040805378]
  We present a novel approach to non-cube optimization with certificates, which handles smooth functions on the hypercube or on the torus. By exploiting the regularity of the target function intrinsic in the decay of its spectrum, we allow at the same time to obtain precise certificates and leverage the advanced and powerful neural networks.
  arXiv  Detail & Related papers  (2023-06-26T09:42:59Z)
• Projection-free Graph-based Classifier Learning using Gershgorin Disc Perfect Alignment [59.87663954467815]
  In graph-based binary learning, a subset of known labels $hatx_i$ are used to infer unknown labels. When restricting labels $x_i$ to binary values, the problem is NP-hard. We propose a fast projection-free method by solving a sequence of linear programs (LP) instead.
  arXiv  Detail & Related papers  (2021-06-03T07:22:48Z)
• On Effective Parallelization of Monte Carlo Tree Search [51.15940034629022]
  Monte Carlo Tree Search (MCTS) is computationally expensive as it requires a substantial number of rollouts to construct the search tree. How to design effective parallel MCTS algorithms has not been systematically studied and remains poorly understood. We demonstrate how proposed necessary conditions can be adopted to design more effective parallel MCTS algorithms.
  arXiv  Detail & Related papers  (2020-06-15T21:36:00Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.