Rethinking Modular Multi-Exponentiation in Real-World Applications

Vidal Attias; Luigi Vigneri; Vassil Dimitrov

Paper 2022/263

Rethinking Modular Multi-Exponentiation in Real-World Applications

Vidal Attias, 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.

Metadata

Available format(s): PDF
Category: Implementation
Publication info: Published elsewhere. Journal of Cryptographic Engineering
DOI: 10.1007/s13389-022-00287-w
Contact author(s): vidal attias @ gmail com
History: 2022-03-02: received
Short URL: https://ia.cr/2022/263
License: CC BY

BibTeX

@misc{cryptoeprint:2022/263,
      author = {Vidal Attias and Luigi Vigneri and Vassil Dimitrov},
      title = {Rethinking Modular Multi-Exponentiation in Real-World Applications},
      howpublished = {Cryptology {ePrint} Archive, Paper 2022/263},
      year = {2022},
      doi = {10.1007/s13389-022-00287-w},
      url = {https://eprint.iacr.org/2022/263}
}