High-Performance Elliptic Curve Point Addition on Versal AI Engine for Multi-Scalar Multiplication

Abstract

Multi-Scalar Multiplication (MSM) is a primary computational bottleneck in modern cryptographic applications, especially zero-knowledge proofs. The Pippenger algorithm parallelizes MSM by decomposing it into numerous elliptic curve point additions (PADDs), but accelerating these operations on novel hardware like the Versal ACAP presents a significant challenge. This work explores the acceleration of PADDs on the Versal ACAP’s spatial array of 400 AI Engines (AIEs). While the SIMD-VLIW architecture of AIEs is ideal for the multiplication-heavy workloads in PADD, the complex 377-bit modular arithmetic, particularly carry propagation, demands architecture-aware optimization. We propose two key contributions: (1) algorithmic optimizations for carry propagation employing a carry-save-like technique to exploit VLIW and SIMD capabilities, and (2) a comparison of spatial mapping strategies and modular reduction algorithms to enhance intra- and intertask parallelism. Our approach achieves 567× speedup over the integrated CPU on the AIE evaluation board, utilizing 51.1% of the theoretical memory bandwidth.