Top

Journal of Cryptographic Engineering

Published in:

15-03-2022 | Regular Paper

Rethinking modular multi-exponentiation in real-world applications

Authors: Vidal Attias, Luigi Vigneri, Vassil Dimitrov

Published in: Journal of Cryptographic Engineering | Issue 1/2023

Activate our intelligent search to find suitable subject content or patents.

search-config

AI-assisted search

Off

Abstract

The importance of efficient multi-exponentiation algorithms in a large spectrum of cryptographic applications continues to grow. Previous literature on the subject pays attention exclusively on the minimization of the number of modular multiplications. However, a small reduction of the multiplicative complexity 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 algorithms that perform best under the number of multi-exponentiation metric and show that some side operations affect their theoretical ranking. We provide this analysis on different hardware, such as Intel Core and ARM CPUs and the two latest generations of Raspberry Pis, to show how the machine chosen affects the execution time of multi-exponentiation.

previous article Faster multiplication over using AVX512 instruction set and VPCLMULQDQ instruction

next article Post-quantum hybrid key exchange: a systematic mapping study

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

über 102.000 Bücher
über 537 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Finance + Banking
Management + Führung
Marketing + Vertrieb
Maschinenbau + Werkstoffe
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 390 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Maschinenbau + Werkstoffe

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 340 Zeitschriften

aus folgenden Fachgebieten:

Bauwesen + Immobilien
Business IT + Informatik
Finance + Banking
Management + Führung
Marketing + Vertrieb
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

https://www.openssl.org.

https://github.com/iotaledger/research-multi-exponentiation.

Attias, V., Vigneri, L., Dimitrov, V.: Implementation study of two verifiable delay functions. In: Tokenomics, 6, pp. 1–6 (2020)

Barrett, P.: Implementing the Rivest Shamir and Adleman public key encryption algorithm on a standard digital signal processor. In: Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 263 LNCS (1987). https://doi.org/10.1007/3-540-47721-7_24

Blondel, V.D., Tsitsiklis, J.N.: When is a pair of matrices mortal? Inf. Process. Lett. (1997). https://doi.org/10.1016/s0020-0190(97)00123-3MathSciNetCrossRefMATH

Blum, T., Paar, C.: Montgomery modular exponentiation on reconfigurable hardware. Proc.: Symp. Comput. Arith. (1999). https://doi.org/10.1109/arith.1999.762831CrossRef

Borges, F., Lara, P., Portugal, R.: Parallel algorithms for modular multi-exponentiation. Appl. Math. Comput. 292, 406–416 (2017). https://doi.org/10.1016/j.amc.2016.07.036MathSciNetCrossRefMATH

Bosselaers, A., Govaerts, R., Vandewalle, J.: Comparison of three modular reduction functions. In: Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 773 LNCS (1994). https://doi.org/10.1007/3-540-48329-2_16

Brent, R., Zimmermann, P.: Modern Computer Arithmetic. Cambridge University Press, Cambridge (2010). https://doi.org/10.1017/cbo9780511921698CrossRefMATH

Chang, C.C., Lou, D.C.: Parallel computation of the multi-exponentiation for cryptosystems. Int. J. Comput. Math. 63, 1–2 (1997). https://doi.org/10.1080/00207169708804548MathSciNetCrossRefMATH

Chang, C.C., Lou, D.C.: Fast parallel computation of multi-exponentiation for public key cryptosystems. In: Parallel and Distributed Computing, Applications and Technologies, PDCAT Proceedings (2003). https://doi.org/10.1109/pdcat.2003.1236459

10.

Dimitrov, V.S., Jullien, G.A., Miller, W.C.: An algorithm for modular exponentiation. Inf. Process. Lett. 66(3), 155–159 (1998)MathSciNetCrossRefMATH

11.

Dimitrov, V.S., Jullien, G.A., Miller, W.C.: Complexity and fast algorithms for multiexponentiations. IEEE Trans. Comput. 49(2), 141–147 (2000)MathSciNetCrossRefMATH

12.

Euclid: The Elements of Euclid, 2nd edn. Dover Publications Inc., New York, USA (1956)

13.

Gueron, S.: Efficient software implementations of modular exponentiation. J. Cryptogr. Eng. (2012). https://doi.org/10.1007/s13389-012-0031-5CrossRefMATH

14.

Koç, Ç.K.: Montgomery Arithmetic, pp. 799–803. Springer, Boston (2011). https://doi.org/10.1007/978-1-4419-5906-5_38CrossRef

15.

Kochergin, V.V.: On Bellman’s and Knuth’s problems and their generalizations. J. Math. Sci. (U. S.) (2018). https://doi.org/10.1007/s10958-018-3928-4MathSciNetCrossRefMATH

16.

Lou, D.C., Chang, C.C.: An efficient divide-and-conquer technique for parallel computation of modular multi-exponentiation. Comput. Syst. Sci. Eng. 15(2), 111–117 (2000)

17.

Möller, B.: Algorithms for multi-exponentiation. In: Vaudenay, S., Youssef, A.M. (eds.) Selected Areas in Cryptography, vol. 2259, pp. 165–180. Springer, Berlin, Heidelberg (2001). https://doi.org/10.1007/3-540-45537-x_13CrossRef

18.

Montgomery, P.L.: Modular multiplication without trial division. Math. Comput. 44(170), 519–521 (1985)MathSciNetCrossRefMATH

19.

Rivest, R.L., Shamir, A., Adleman, L.: A method for obtaining digital signatures and public-key cryptosystems. Commun. ACM 21(2), 120–126 (1978). https://doi.org/10.1145/359340.359342MathSciNetCrossRefMATH

20.

Avanzi, R.M.: The complexity of certain multi-exponentiation techniques in cryptography. J. Cryptol. 18(4), 357–373 (2005). https://doi.org/10.1007/00145-004-0229-5

21.

Van Meter, R., Itoh, K.M.: Fast quantum modular exponentiation. Phys. Rev. A: At., Mol., Opt. Phys. (2005). https://doi.org/10.1103/PhysRevA.71.052320CrossRefMATH

22.

Wang, B., Hu, Y.: Signature scheme using the root extraction problem on quaternions. J. Appl. Math. (2014). https://doi.org/10.1155/2014/819182MathSciNetCrossRefMATH

23.

Wesolowski, B.: Efficient verifiable delay functions. In: Ishai, Yuval, Rijmen, Vincent (eds.) Advances in Cryptology – EUROCRYPT 2019, vol. 11478 LNCS, pp. 379–407. Springer International Publishing (2019). https://doi.org/10.1007/978-3-030-17659-4_13

24.

Yagisawa, M.: A digital signature using multivariate functions on quaternion ring. IACR Cryptol. ePrint Arch. 2010(2), 352 (2010)

25.

Yen, S.M., Laih, C.S., Lenstra, A.K.: Multi-exponentiation. IEE Proc.: Comput. Digit. Tech. 141(6), 325–326 (1994)MATH

Title: Rethinking modular multi-exponentiation in real-world applications
Authors: Vidal Attias
Luigi Vigneri
Vassil Dimitrov
Publication date: 15-03-2022
Publisher: Springer Berlin Heidelberg
Published in: Journal of Cryptographic Engineering / Issue 1/2023
Print ISSN: 2190-8508
Electronic ISSN: 2190-8516
DOI: https://doi.org/10.1007/s13389-022-00287-w

Springer Professional

Abstract

Please log in to get access to your license.

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Springer Professional "Technik"

Springer Professional "Wirtschaft"

Other articles of this Issue 1/2023

Subgroup membership testing on elliptic curves via the Tate pairing

Post-quantum hybrid key exchange: a systematic mapping study

A new read–write collision-based SRAM PUF implemented on Xilinx FPGAs

Improving recent side-channel attacks against the DES key schedule

Low area-time complexity point multiplication architecture for ECC over GF() using polynomial basis

Karatsuba-based square-root Vélu’s formulas applied to two isogeny-based protocols

Premium Partner