Cryptology ePrint Archive: Report 2021/1394

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. Many of the algorithms proposed in the past pay attention exclusively on the minimization of the number of modular multiplications. However, a short reduction of the multiplicative com- plexity can be easily overshadowed by other figures of merit. In this article we demonstrate a large number of practical results aimed at concrete cryptographic tasks requiring multi-exponentiations and provide rec- ommendations on the best possible algorithmic strate- gies for different selection of security parameters.

Category / Keywords: implementation / multiexponentiation open-ssl benchmarking arithmetic

Date: received 15 Oct 2021

Contact author: vidal attias at gmail com

Available format(s): PDF | BibTeX Citation

Version: 20211015:082843 (All versions of this report)

Short URL: ia.cr/2021/1394


[ Cryptology ePrint archive ]