VROOM: Accelerating (Almost All) Number-Theoretic Cryptography Using Vectorization and the Residue Number System

Modular arithmetic with a large prime modulus is a dominant computational cost in number-theoretic cryptography. Modular operations are especially challenging to parallelize efficiently on CPUs using vector instructions; standard CPU implementations rely on costly carry operations and permutation instructions to align with the multiplication datapath, negating the benefits of vectorization.

We develop vectorized algorithms for modular addition and multiplication, and present a new, constant-time modular multiplication algorithm suitable for general moduli -prime or otherwise. Our method uses a Residue Number System (RNS) representation to align the arithmetic naturally with wide vector units, and strategically eliminate extraneous instructions. Existing works either require the use of customized hardware or fail to show latency improvements.

Reducing the latency of modular arithmetic results in speedups for cryptographic applications. We accelerate RSA-4096 signatures by 4.0× (verify) and 1.3× (sign) over OpenSSL, and speed up BLS signature verifications by 4.05× over the assembly-optimized blst library. Results on mapping our algorithm to Nvidia GPUs demonstrate speedups on modular multiplication over Nvidia's CGBN library.

Our contributions We summarize our contributions:

• We develop VROOM 1 , a new RNS Montgomery algorithm that uses a new least number of multiplications. This algorithm is novel to the best of our knowledge, since prior works [3,39] resorted to significantly more complicated techniques, and still required more multiplications than our work (See Section 7).

• We create a new unifying optimization framework of premultiplications and post-multiplications that subsumes several ad-hoc techniques [3, 39] as suboptimal special cases. This framework allows us to arrive at VROOM, and may be of independent interest to future works.

• We develop a new programming framework for RNS computation that generalizes the ideas behind VROOM into settings beyond a single modular multiplication, including computing modular inner products, extension field arithmetic, and elliptic-curve arithmetic (Section 4), used in high-level protocols. We show how to enforce compile-time correctness for arbitrary algorithms, and how to utilize RNS Montgomery to reduce the computational cost below that of "schoolbook" methods.

• We provide an open-source, constant-time implementation of VROOM in C++ via a strategic mapping to AVX512IFMA instruction intrinsics, and show how our implementation can be adapted to work with any multiply-accumulate vector instruction (Section 5).

• We provide a full-fledged fork of BoringSSL using VROOM, and demonstrate a 3.3-3.6× speedup in RSA signature verification for RSA modulus ranging from 2048 to 4096 bits.

• We show how to adapt VROOM to the 381-bit modulus of the BLS12-381 elliptic curve, by taking advantage of optimizations for modular arithmetic, and demonstrate a speedup of 3.15× for elliptic-curve pairings [46] over popular libraries.

• We show how VROOM can be adapted to GPUs to obtain significant speedups for modular multiplication under large primes.