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
Creative Commons Attribution
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},
      note = {\url{https://eprint.iacr.org/2022/263}},
      url = {https://eprint.iacr.org/2022/263}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.