CS Paper Radar

Exposing SIMD Parallelism in SQIsign: An AVX-512 Implementation

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

cs.CR ·submitted 2026-08-14 04:39 UTC · v2

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.

Closest papers

Nearest neighbours by meaning across the whole index.

Locus: A Framework for Exploring and Optimizing Point Addition Hardware for Zero-Knowledge Proofs

cs.AR cs.CR ·2026-09-16 ·Gaurav Kuwar, Alhad Daftardar, Jianqiao Mo, Siddharth Garg, Brandon Reagen
publishedcode/data similarity 0.63
Abstract · 9 pages, 10 figures, 9 tables. Accepted at the IEEE/ACM International Conference on Computer-Aided Design (ICCAD 2026)

Zero-Knowledge Proofs (ZKPs) are critical for privacy-preserving and verifiable computation, but their cryptographic primitives impose high computational overheads. One such primitive is point addition (PADD) on elliptic curves. Several prior works have implemented PADDs in hardware, but only for a few specific elliptic curves and design points, leaving a large design space unexplored, and lacking systematic guidance on hardware design trade-offs. To address this gap, we present Locus, a framework dedicated to optimizing and exploring point addition hardware. Given the parameters of any elliptic curve in a supported equation form, Locus automatically generates ASIC and FPGA implementations of PADD, enabling systematic exploration of the PADD design space. Using Locus, we conduct the first comprehensive hardware-focused study of PADD designs, exploring trade-offs over 1,000 design points. On a 12nm technology node, our framework produces PADD designs that yield a $2.71\times$ geomean speedup and $3.11\times$ geomean area reduction compared to prior ASICs, $34.67\times$ geomean speedup over CPU, and $3.15\times$ geomean speedup on end-to-end proof generation when integrated into a prior ZKP accelerator at iso-area. Locus is available at https://github.com/cryptolets/cryptolets/tree/locus.

0.58

Parallelizing the Factorial Space: Multi-Core OpenMP Scaling and Scalable SIMD Acceleration of the Steinhaus-Johnson-Trotter Algorithm via Dual-Lane AVX2 Execution

cs.DS ·2026-09-07 ·Serge Melnikov
similarity 0.62
Abstract · Added extended framework with multi-core parallel execution via OpenMP, introduced dynamic state mapping and thread scalability benchmarks u…

This paper presents a high-performance SIMD acceleration framework for the Steinhaus-Johnson-Trotter algorithm, targeted at modern x86-64 architectures using the AVX2 instruction set. By exploiting a novel combinatorial space partitioning combined with single-cycle vector byte shuffling ($\texttt{\_mm256\_shuffle\_epi8}$), our dual-lane vectorized implementation processes two independent, concurrent permutation streams within a single 256-bit YMM register under a uniform execution mask. Empirical evaluations demonstrate a $3\times$ throughput increase over an optimized scalar baseline of Knuth's Algorithm P (accelerated by $3\times$ via isolated sweeping branches) and outperform the recent Ring-Cascade algorithm by Yusheng Hu, completely avoiding store-forwarding stalls during hot loops. To scale this engine across multi-core processors, we extend the framework into a highly concurrent environment via OpenMP using a localized mathematical state decoder and macro-period loop scheduling. The parallel performance is shown to scale strictly and linearly with the number of active physical processor cores ($\text{Speedup}(M) \approx M$) due to a lock-free thread-local accumulation pipeline that eliminates false sharing. On a 6-core processor, the multi-threaded engine delivers a $5.25\times$ throughput gain for $n=14$ ($3.25$ billion CPU cycles) and processes the massive $n=15$ space in just $16.0$ seconds, yielding a $5.25\times$ speedup over the sequential vector baseline, while Hyper-Threading virtual cores yield zero additional throughput due to physical SIMD port saturation.

0.26

Parallel Integration over Simple Radical Extensions in Mixed Towers: Charlwood's Integrals

cs.SC ·2026-09-22 ·Sam Blake
similarity 0.60
Abstract

We evaluate a SymPy implementation of the parallel Risch-Norman method using Charlwood's 2008 suite of 50 challenging indefinite integrals. The system automatically builds integrand towers, verifies answers by differentiation, and returns correct, verified integrals for 49 problems with zero errors. The single failure, $\int\arcsin(x\sqrt{1-x^2})\,dx$, is proven non-elementary using a holomorphic-remainder certificate, though limited by an unverified completeness hypothesis on a genus-three curve. Part II's degree bounds successfully reduce classical ansatz sizes by two-thirds without impacting running time. The paper details algorithmic mechanisms like $S'$-units, Pell units, and residue computing in tower coordinates. Compared to mature implementations, this untuned SymPy prototype is slower than FriCAS (by a factor of six on the median integral) but more accurate than AXIOM (which returned three wrong answers). Profiling pinpoints performance bottlenecks in nonlinear norm searches and nested number fields, outlining clear targets for optimisation.

0.38

FIGFLEX: A Mixed-Precision FP-INT GEMM Accelerator Co-Designed with Low-Bit LLM Quantization

cs.AR cs.LG ·2026-10-21 ·Faraz Tahmasebi, Haocheng Xu, Andrew Trauger, Yomal Perera, Zhenyu Tang +2 more
similarity 0.60
Abstract · 15 pages, 12 Figures

Weight-only quantization keeps LLM activations in floating point and stores weights as low-bit integers, turning the dominant workload into floating-point-integer (FP-INT) general matrix multiplication. Recent quantizers reach a 2-3-bit average with mixed precision, but hardware has not kept pace: GPUs dequantize weights to FP16 before the tensor-core multiply-accumulate, and bit-parallel FP-INT accelerators run at a single weight precision, so fewer bits save memory but not computation. In this paper, we present FIGFLEX, an algorithm-hardware co-designed mixed-precision accelerator whose bit-parallel datapath scales throughput as precision falls. FIGFLEX contributes (1) a shift-add, radix-4 reformulation of FP-INT multiplication that fuses the multiply-accumulate into a unified, precision-flexible partial-product reduction and roughly halves the partial products, together with a novel INT3 optimization that reclaims the idle datapath radix-4 leaves at that precision; and (2) a mixed-precision quantizer that assigns each channel group its bit-width according to the error GPTQ cannot compensate, with a per-input-channel column scaling whose power-of-two normalization keeps the scaled activations out of the FP16 subnormal range, so that the quantized model maps directly onto FIGFLEX's datapath with the same accuracy as on a GPU. On LLaMA-2-7B, FIGFLEX attains 5.85 and 8.77 WikiText-2 perplexity at 3- and 2-bit average precision, lower than GPTQ, AWQ, SliM-LLM, AMQ, and QuIP# (without fine-tuning), while delivering 1.56x and 1.42x higher whole-chip throughput per area on the linear GEMMs of a 3-bit mixed-precision model than AxCore and FIGLUT, respectively.

0.13

Faster PMNS Multi-precision Multiplications Using Truncated Montgomery Technique

cs.CR ·2026-10-07 ·Laurent-Stéphane Didier, Alexy Dutois-Ruiz, Jean-Marc Robert
similarity 0.59
Abstract · 21 pages, one figure

The Polynomial Modular Number Systems (PMNS) aim to represent elements of fields or rings of large characteristics using polynomials satisfying bounds on some parameters (degree, absolute values of the coefficients). Those PMNS, while some conditions are fulfilled, using convenient parameters and implementation features, allow some speed-ups in cryptographic computations. Recent works (Meloni \emph{et al.} \cite{MeloniPV25}) propose better speed-ups by improving the parameter generation of the system, and by using multi-precision polynomial coefficients, i.e. coefficients stored using several machine words. In this work, we first present PMNS schoolbook software implementation better in some context than the Toeplitz state-of-the-art counterpart of \cite{MeloniPV25}, taking advantage of smaller memory cost by being free to choose a smaller $n$ parameter, minimizing at the same time the complexity of the multiplication. This implementation for 4096 bit modulo size shows element size smaller by 11\% and 20 \% speed-up. We thus present a new improvement on the PMNS, applying to the \textsl{internal reduction} an approach similar to the truncated Montgomery reduction technique presented by Didier \emph{et al.} in \cite{DidierEGR24}. In the context of software implementations using \texttt{AVX512} instruction set extension, and modulo size up to 8192 bits, this new approach allows speed-ups up to 15\% in modular multiplication computation, in comparison with conventional approaches.

0.26

Algebraic Integer Quantization for Machine Learning Applications

cs.LG ·2026-09-25 ·Anthony Kostal-Vazquez, Vassil Dimitrov, Branden Butler
similarity 0.59
Abstract

In this article, we propose algebraic integer number formats (AINF) as a framework for highly configurable and accurate compressed computation. A key property of AINF is its straightforward reduction to purely integer arithmetic, enabling error-free multiply-accumulate operations. We develop a matrix multiplication engine that exploits this property, obtaining performance within a predictable factor of the most efficient numerical counterparts on modern hardware accelerators. Another key advantage of AIQ is the freedom to select algebraic integers tailored to the numerical characteristics of a given use case, offering optimization opportunities that are fundamentally unavailable in floating-point or fixed-point formats. Motivated by these properties, we introduce algebraic integer quantization (AIQ), a lossy compression format for large language model (LLM) inference, and provide results demonstrating that AIQ achieves competitive accuracy compared to the industry-standard MX format across a diverse set of models and benchmarks at equivalent bit-per-parameter budgets. The experiments presented in this article employ algebraic integers of degree two (quadratic integers); generalizations to higher-order and, in particular, multidimensional algebraic integers promise even greater computational advantages and remain a promising direction for future work.

0.28

BenX: Resource-Sharing Permutations for Computational Integrity

cs.CR ·2026-09-25 ·Luca Campa, Thomas De Cnudde, Al Kindi, Arnab Roy, Fabian Schmid +2 more
similarity 0.58
Abstract

Cryptographic hash functions over integers modulo a prime play a decisive role in the efficiency and security of proof systems for computational integrity. Early designs focused on compact arithmetic circuits and efficient software execution, primarily targeting general-purpose CPUs rather than hardware accelerators. This work focuses on enabling efficient resource sharing and hardware acceleration alongside efficient software execution. We propose BenX, a permutation-based hash function designed for hardware acceleration, fast CPU execution, and low circuit complexity in proof systems. To construct the underlying permutation, we turn the Benes network into an invertible function over $\mathbb{F}_p^2$ using a Dickson polynomial. Its structure yields a permutation particularly suited to hardware resource sharing and acceleration. Fully pipelined on FPGA, BenX matches the throughput of Poseidon2, with 1.36x and 2.15x lower latency for Goldilocks and BabyBear, respectively. Although larger as a standalone core, it makes more effective use of shared hardware: in our dual-mode architecture, where the NTT and hash share field multipliers, BenX keeps 100% of them busy, compared with 6.25-20.3% for the partial rounds of Poseidon and Poseidon2. In software, BenX outperforms Poseidon in all tested 31- and 64-bit configurations, but is slower than Poseidon2, except for the 16-element BabyBear instance. In zero-knowledge proofs, BenX proves Goldilocks permutations 6-10x faster than Monolith. Its compact arithmetization uses about 36% fewer trace cells than Poseidon and Poseidon2 over BabyBear, while its fast variant requires 1.3-2.6x the prover time of Poseidon2.

0.22

Long rational and Gaussian integer multiplication

cs.DS math.NT ·2026-11-13 ·Yuval Spiizer, Raphael S. Steiner
similarity 0.57
Abstract · 38 pages

Long integer multiplication is a fundamental operation in computational algebra, heavily relying on Toom--Cook and related evaluation-interpolation algorithms. Conventional wisdom dictates that multiplication on the Gaussian integers $\mathbb{Z}[i]$ is reduced to standard rational integer multiplication, since $\mathbb{Z}[i]$ is a ring extension of $\mathbb{Z}$. We show that this approach is far from optimal and moreover inverting this established paradigm, that is reducing rational to Gaussian multiplication, leads to faster rational integer multiplication algorithms. We introduce a novel Toom--Cook framework that reduces rational long integer multiplication to Gaussian integer multiplication, yielding a strictly more efficient computational pipeline. By taking advantage of the special properties of the rational integer domain inside the Gaussian integers, we achieve a more favourable algebraic structure that reduces the overall arithmetic cost in every metric. To validate this theoretical shift, we provide a complete implementation of our algorithm. Benchmarks demonstrate that our approach outperforms the highly optimised GNU Multiple Precision Arithmetic Library (GMP) by up to 29\%, bridging a fundamental theoretical insight with significant practical improvements in high-performance computer algebra.

0.20