Cryptology ePrint Archive: Report 2022/263

Rethinking Modular Multi-Exponentiation in Real-World Applications

Vidal Attias and Luigi Vigneri and Vassil Dimitrov

Abstract: The importance of efficient multi-exponen- tiation algorithms in a large spectrum of cryptographic applications continues to grow. Previous literature on the subject pays attention exclusively on the mini- mization of the number of modular multiplications. However, a small reduction of the multiplicative com- plexity can be easily overshadowed by other figures of merit. In this article, we demonstrate that the most efficient algorithm for computing multi-exponentiation changes if considering execution time instead of number of multi-exponentiations. We focus our work on two al- gorithms that perform best under the number of multi- exponentiation metric and show that some side opera- tions affects their theoretical ranking. We provide this analysis on different hardware, such as Intel Core and ARM CPUs and the two latest generations of Rasp- berry Pis, to show how the machine chosen affects the execution time of multi-exponentiation.

Category / Keywords: implementation / Multi-exponentiation OpenSSL benchmarking arithmetic

Original Publication (in the same form): Journal of Cryptographic Engineering

Date: received 27 Feb 2022

Contact author: vidal attias at gmail com

Available format(s): PDF | BibTeX Citation

Version: 20220302:141207 (All versions of this report)

Short URL:

[ Cryptology ePrint archive ]