Design and implementation of a low-latency modular multiplication algorithm

Official URL: http://dx.doi.org/10.1109/TCSI.2020.2966755

Modular multiplication is one of the most compute-intensive arithmetic operations. Most public-key cryptosystems utilize modular multiplication of integers of various lengths, depending on security requirements. Efficient algorithms and implementations are required to realize a practical public-key cryptosystem. Different parameters, such as area, power and time, can be optimized for different implementation requirements. Low latency was not as important as high throughput requirement for modular multiplication implementations before. However, with recent work on Verifiable Delay Functions (VDFs), a necessity for the lowest possible latency for modular multiplication implementations emerged. VDFs are designed to take a prescribed time to realize the underlying computation that can be publicly verified. VDF constructions utilize inherently sequential arithmetic operations. Efficient VDF constructions have been proposed recently, based on time-lock puzzles constructed by Rivest, Shamir, and Wagner. An exponentiation operation in an RSA group needs to be realized for these VDF constructions. In this paper, a modular multiplication algorithm suitable for low-latency circuit implementations is proposed and an FPGA-optimized variant of this algorithm is presented.