arXiv:2606.16394v1 [cs.CR] 15 Jun 2026
MPX: A Unified Systolic Array for Matrix and Polynomial Multiplication George Alexakis
Dimitrios Schoinianakis
Giorgos Dimitrakopoulos
Electrical and Computer Engineering Democritus University of Thrace, Xanthi, Greece
Nokia Bell Labs Athens, Greece
Electrical and Computer Engineering Democritus University of Thrace, Xanthi, Greece
Abstract—Polynomial multiplication is a fundamental kernel in Fully Homomorphic Encryption (FHE) and post-quantum cryptography (PQC) and is commonly accelerated through Number Theoretic Transforms (NTTs). To avoid the cost of designing dedicated cryptographic accelerators, recent efforts have mapped NTT computations onto existing systolic matrix engines, enabling the reuse of AI hardware for cryptographic workloads. In this work, we take the opposite approach. We observe that the wavefront dataflow of systolic arrays naturally aligns with the accumulation pattern of polynomial multiplication and leverage this correspondence to design MPX, a dual-mode systolic array that supports both matrix multiplication and direct polynomial multiplication within the same hardware fabric. Experimental results show that extending a conventional systolic array with this dual-mode capability requires only 20% additional area and introduces negligible power overhead during matrix-multiplication execution. In polynomial-multiplication mode, MPX achieves more than 1.2× lower latency compared to NTT-based polynomial multiplication on systolic matrix engines.
I. I NTRODUCTION Polynomial multiplication is a fundamental operation in modern lattice-based cryptography, forming the computational backbone of both Fully Homomorphic Encryption (FHE) and many post-quantum cryptographic (PQC) schemes [1], [2]. Despite the strong security and functionality guarantees offered by these systems, their practical deployment remains constrained by the high computational cost. While specialized accelerators have been proposed to address this challenge [3], [4], designing dedicated hardware for rapidly evolving FHE and PQC algorithms is costly and difficult to scale. An increasingly attractive alternative is to leverage existing AI hardware [5]. Modern accelerators built around systolic arrays (SAs) provide massive parallelism and energy efficiency, motivating a growing body of work that maps cryptographic workloads onto AI accelerators [6], [7], [8]. The challenge is that FHE and PQC computations are organized around polynomial arithmetic, whereas SAs are designed to efficiently execute matrix operations. Most prior approaches bridge this gap through the Number Theoretic Transform (NTT) [9]. By expressing polynomial multiplication as a sequence of NTTs and pointwise multiplications, these methods expose regular computations that can be executed efficiently on matrix engines [8]. Effectively, this approach adapts polynomial arithmetic to the currently available capabilities of matrix hardware. In this work, we explore the opposite direction. Rather than transforming polynomial multiplication to fit existing matrix engines, we adapt the matrix engine itself to directly support
polynomial multiplication. We observe that the wavefront propagation pattern of systolic arrays naturally aligns with the accumulation pattern of polynomial multiplication, enabling polynomial arithmetic to execute directly within the SA. Guided by this observation, we design MPX, a dual-mode systolic architecture that supports both matrix multiplication and polynomial multiplication within the same hardware structure. MPX preserves the hardware-reuse benefits of AI matrix engines while eliminating the need to route polynomial multiplication through an NTT-centric execution flow. The contributions of this work can be summarized as follows: • We present MPX, the first SA architecture, to the best of our knowledge, that directly maps polynomial multiplication onto the existing multiply-accumulate processing elements of a SA. • The introduced polynomial-multiplication dataflow supports arbitrary sequences of back-to-back polynomial multiplications, enabling the execution of large polynomial multiplications on SAs with fixed dimensions. • Experimental results show that MPX extends a conventional SA with native polynomial-multiplication support at 20% area overhead, while achieving more than 1.2× speedup compared to NTT-based polynomial multiplication approaches. II. BACKGROUND AND R ELATED W ORK FHE and PQC workloads are dominated by polynomial arithmetic, which is commonly accelerated through the Number Theoretic Transform (NTT). NTT converts polynomial convolution into element-wise multiplication in the transform domain, making it a key building block for efficient polynomial multiplication [9]. Recent work has increasingly explored the reuse of AI accelerators for NTT execution. For example, TensorFHE [6], TensorFHE+ [7], and CROSS [8] demonstrate that cryptographic kernels can be reformulated as dense linear-algebra operations and mapped onto tensor cores and SAs. This is typically achieved using the 4-step NTT algorithm [10], which decomposes large transforms into a sequence of matrixfriendly operations. The 4-step NTT first reshapes the input vector into a matrix and then performs column-wise transforms, twiddle-factor multiplication, a matrix transpose, and row-wise transforms. The transform stages are expressed as matrix multiplications, while the remaining stages consist of element-wise operations and data reorganization.
(a) MPX
Fig. 1: The micro-architecture of a typical SA, and a highlevel overview of the weight-stationary (WS) dataflow. Although this approach enables polynomial arithmetic to leverage the computational throughput of existing matrix engines, it also introduces additional transpositions, buffering, synchronization, and data movement overheads. A typical SA consists of a 2D array of processing elements (PEs), as shown in Fig. 1(a). Each PE contains a multiplier, an adder, and the registers required to sustain pipelined data movement through the array. Input operands are streamed from local memory banks located along the North and West edges, while outputs are collected along the South edge. The organization of computation within the SA is determined by its dataflow. In the widely adopted weightstationary dataflow [11], weights are preloaded into the array while input is streamed from the West side, as illustrated in Fig. 1(b). The matrix product is computed through a wavefront of multiply-accumulate operations that propagates diagonally across the fabric. III. U NIFIED S YSTOLIC A RRAY FOR M ATRIX AND P OLYNOMIAL M ULTIPLICATIONS In this work, instead of adapting polynomial multiplication to existing matrix engines, we extend the SA itself to directly support polynomial multiplication. The objective is to preserve the efficiency of matrix-multiplication accelerators while enabling polynomial multiplication through minimal architectural modifications. The key observation behind MPX is that polynomial multiplication naturally maps to the wavefront execution Pn−1 Pm−1model of SAs. Given A(x) = i=0 ai xi and B(x) = j=0 bj xj , Pn+m−2 ck xk has coefficients ck that their product C(x) = k=0 are defined by the sum of all P cross-products with index sum i + j equal to k, i.e., ck = i+j=k ai bj . As a result, the products contributing to a given coefficient lie along a common diagonal in the 2D (i, j) index space, closely matching the wavefront propagation already present in SAs. A. Dual-mode Systolic Array Leveraging this correspondence, Fig. 2 presents MPX, a dual-mode systolic architecture that supports both matrix multiplication and polynomial multiplication within the same SA. Relative to the baseline SA, MPX introduces a second accumulation path for polynomial multiplication. In matrix mode, inputs propagate horizontally while partial sums follow the conventional vertical reduction path. In polynomial mode, the two input polynomials are streamed from orthogonal
(b) Matrix Multiplication mode
(c) Polynomial Multiplication mode
Fig. 2: (a) MPX PE supporting two modes of operation. The corresponding dataflows are highlighted separately in (b) weight-stationary matrix-multiplication mode and (c) polynomial-multiplication mode. directions (North and West), with partial sums forwarded diagonally across the array. To support this operation, the vertical weight-loading path used during matrix multiplication is reused to stream the second polynomial, allowing products contributing to the same output coefficient to be accumulated as they traverse the systolic fabric. Correct operation requires the diagonally-propagated partial sums to remain synchronized with the incoming operands. To maintain this alignment, MPX introduces a single pipeline register along the diagonal polynomial accumulation path. This lightweight modification preserves the critical path of the SA, while ensuring that operands and partial sums arrive at each PE at the appropriate cycle for accumulation. By supporting both accumulation patterns within the same hardware structure, MPX enables direct polynomial multiplication while remaining fully compatible with conventional matrix workloads. To illustrate the polynomial multiplication dataflow, Fig. 3 shows the multiplication of 2 + 3x + 4x2 and 1 + 5x + 2x2 in MPX. As coefficients stream into the array from orthogonal directions, each PE generates a local partial product. In polynomial mode, these partial products are accumulated along the diagonals as they traverse the array. Consequently, all products contributing to the same output coefficient meet and are added within the SA.
Fig. 3: Running example of polynomial multiplication on MPX. B. Scaling to Larger Polynomial Multiplications To support polynomials exceeding the array’s physical dimensions, operands are decomposed into L-coefficient blocks. P A polynomial A(x) is partitioned as A(x) = i Ai (x)xiL . The product A(x)B(x) is then reconstructed by computing all pairwise convolutions Ai (x)Bj (x) natively on the hardware and accumulating them with the corresponding x(i+j)L shift. For example, multiplying degree-4 polynomials on an array with block length L = 2 partitions the inputs into A(x) = A0 (x) + A1 (x)x2 and B(x) = B0 (x) + B1 (x)x2 , where A0 (x) = a0 + a1 x and A1 (x) = a2 + a3 x (with an analogous decomposition for B). The multiplication expands to A(x)B(x) = A0 B0 + (A0 B1 + A1 B0 )x2 + A1 B1 x4 . This reduces the larger multiplication to four independent, hardware-native polynomial multiplications. As illustrated in Fig. 4, the sub-polynomials are streamed into MPX backto-back without introducing idle cycles between successive computations, allowing MPX to remain continuously utilized. To reconstruct the final polynomial, the resulting products are accumulated in vector units outside MPX. IV. E VALUATION We evaluate MPX from two complementary perspectives. First, we quantify the hardware overhead of extending a conventional SA with native polynomial-multiplication support. Second, we compare the latency of direct polynomial multiplication on MPX against state-of-the-art approaches that perform polynomial multiplication through NTTs mapped onto existing AI accelerators. A. Hardware Cost of Dual-Mode Operation To quantify the hardware cost of MPX, we compare the proposed architecture against a conventional SA of identical
Fig. 4: Back-to-back execution of sub-polynomial multiplications on a 2×2 MPX. dimensions. The additional hardware consists of two components: (i) mode-controlled routing and multiplexing within each PE to support diagonal accumulation, and (ii) an additional pipeline register in the polynomial datapath to maintain operand alignment. The PEs employ 8-bit integer multipliers and 32-bit adders, matching the arithmetic precision of industrial systolic arrays [5], [12]. Both architectures were implemented using the OpenROAD physical-design flow and the ASAP7 technology library. All designs were synthesized and placed-and-routed at a target clock frequency of 1 GHz. Table I summarizes the post-layout area and power results across multiple SA sizes, while Fig. 5 illustrates the physical layouts of a baseline 8 × 8 SA and an MPX design of the same size. The additional hardware required to support both matrix- and polynomial-multiplication modes increases area by approximately 20%, with similar overhead observed across all evaluated array dimensions.
TABLE I: Post-layout area and power comparison between the baseline SA and MPX. For MPX power is reported separately per mode of operation. Area (mm2 ) SA Size Baseline MPX Baseline 16x16 32x32 64x64
0.017 0.066 0.263
0.020 0.079 0.317
0.101 0.405 1.632
Power (W) MPX MPX Matrix Mode Poly mode 0.104 0.417 1.682
0.146 0.587 2.367
Fig. 5: Physical layout of 8×8 instances of the baseline SA and the proposed MPX. Power is reported separately for each operating mode. In matrix-multiplication mode, MPX incurs only 3% additional power consumption relative to the baseline SA, primarily due to the added 32-bit multiplexing logic. The diagonal registers and routing associated with polynomial execution remain clock-gated and therefore do not contribute to dynamic power consumption. In polynomial-multiplication mode, power consumption increases relative to matrix mode due to the activation of the diagonal accumulation path, including the additional 32-bit registers and interconnects required for diagonal data propagation. Overall, MPX achieves its goal of supporting both matrix and polynomial multiplication within the same SA while introducing minimal power overhead for conventional matrixmultiplication workloads. B. Performance Evaluation Table II compares MPX against a conventional SA executing polynomial multiplication through a four-step NTT decomposition for various polynomial degrees and SA sizes. All configurations were evaluated using SCALE-Sim v3 [11] after modeling MPX. Operations that do not execute inside the SA, such as element-wise multiplications, or subpolynomial accumulations, were modeled using SCALE-Sim’s SIMD backend configured with 16 lanes to approximate an AVX-512-class vector unit for 32-bit element vectors. MPX consistently outperforms the NTT-based baseline across the evaluated configurations. The advantage becomes more pronounced as the SA dimensions increase, since direct polynomial multiplication is able to exploit the available spatial parallelism more effectively than the matrix-oriented decomposition imposed by the four-step NTT. As polynomial sizes grow, the relative benefit decreases because both approaches become increasingly dominated by the multiply-add arithmetic intensity. Importantly, configurations that favor NTT-based execution do not diminish the utility of MPX. Since MPX retains full
TABLE II: Number of cycles for computing polynomial multiplication either directly in MPX or through matrixmultiplication-based NTTs. Polynomial Degree
SA Size
NTT-based
MPX
Speedup
128
16x16 32x32 64x64
567 855 1431
159 95 135
3.57 9.00 10.60
256
16x16 32x32 64x64
766 1054 1630
543 191 159
1.41 5.52 10.25
512
16x16 32x32 64x64
2500 1546 2122
2079 575 255
1.20 2.69 8.32
matrix-multiplication functionality, NTT computations can be executed on the same hardware when they are the preferred algorithmic choice. MPX provides the flexibility to select between direct polynomial multiplication or NTT-based execution according to the characteristics of the target workload. V. C ONCLUSIONS This work presented MPX, a dual-mode SA that extends conventional matrix-multiplication engines with native support for polynomial multiplication. Unlike prior approaches that accelerate polynomial arithmetic through NTT computations mapped onto matrix engines, MPX exploits the natural correspondence between polynomial multiplication and systolic wavefront execution to perform polynomial multiplication directly within the SA. With lightweight modifications to the PEs and dataflow, MPX supports both matrix and polynomial multiplication on the same hardware substrate, enabling efficient reuse across AI and FHE/PQC workloads. R EFERENCES [1] Y. Gong et al., “Practical solutions in fully homomorphic encryption: a survey analyzing existing acceleration methods,” Cybersecurity, vol. 7, no. 1, p. 5, 2024. [2] C. Zeng et al., “The implementation of polynomial multiplication for lattice-based cryptography: A survey,” Journal of Information Security and Applications, vol. 83, p. 103782, 2024. [3] J. Zhang et al., “Sok: Fully homomorphic encryption accelerators,” ACM Computing Surveys, vol. 56, no. 12, pp. 1–32, 2024. [4] L. Daksha et al., “Fhecore: Rethinking gpu microarchitecture for fully homomorphic encryption,” arXiv preprint arXiv:2602.22229, 2026. [5] N. P. Jouppi et al., “Ten lessons from three generations shaped Google’s TPUv4i : Industrial product,” in IEEE Inter. Symp. on Comp. Arch. (ISCA), 2021. [6] S. Fan et al., “Tensorfhe: Achieving practical computation on encrypted data using gpgpu,” in IEEE Inter. Symp. on High-Perf. Comp. Arch. (HPCA), 2023, pp. 922–934. [7] Y. Sun et al., “Tensorfhe+: Fully homomorphic encryption acceleration based on linear algebra,” IEEE Trans. on Computers, 2025. [8] J. Tong et al., “Leveraging ASIC AI chips for homomorphic encryption,” in IEEE Inter. Symp. on High Perf. Comp. Arch. (HPCA), 2026. [9] D. Harvey, “Faster arithmetic for number-theoretic transforms,” Journal of Symbolic Computation, vol. 60, pp. 113–119, 2014. [10] D. H. Bailey, “FFTs in external or hierarchical memory,” The journal of Supercomputing, vol. 4, no. 1, pp. 23–35, 1990. [11] R. Raj et al., “Scale-sim v3: A modular cycle-accurate systolic accelerator simulator for end-to-end system analysis,” in IEEE Intern. Symp. on Perf.e Analysis of Systems and Software (ISPASS), 2025, pp. 186–200. [12] Intel, “Architecture instruction set extensions and future features programming reference,” Intel, Tech. Rep., 2026.