nach oben

Journal of Cryptographic Engineering

Erschienen in:

15.03.2022 | Regular Paper

Rethinking modular multi-exponentiation in real-world applications

verfasst von: Vidal Attias, Luigi Vigneri, Vassil Dimitrov

Erschienen in: Journal of Cryptographic Engineering | Ausgabe 1/2023

Einloggen

Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.

search-config

KI-gestützte Suche

Aus

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.

Vorheriger Artikel Faster multiplication over using AVX512 instruction set and VPCLMULQDQ instruction

Nächster Artikel Post-quantum hybrid key exchange: a systematic mapping study

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

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!

Jetzt informieren

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!

Jetzt informieren

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!

Jetzt informieren

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

Titel: Rethinking modular multi-exponentiation in real-world applications
verfasst von: Vidal Attias
Luigi Vigneri
Vassil Dimitrov
Publikationsdatum: 15.03.2022
Verlag: Springer Berlin Heidelberg
Erschienen in: Journal of Cryptographic Engineering / Ausgabe 1/2023
Print ISSN: 2190-8508
Elektronische ISSN: 2190-8516
DOI: https://doi.org/10.1007/s13389-022-00287-w

Springer Professional

Abstract

Bitte loggen Sie sich ein, um Zugang zu Ihrer Lizenz zu erhalten.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Springer Professional "Technik"

Springer Professional "Wirtschaft"

Weitere Artikel der Ausgabe 1/2023

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

Post-quantum hybrid key exchange: a systematic mapping study

Subgroup membership testing on elliptic curves via the Tate pairing

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

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

Faster multiplication over using AVX512 instruction set and VPCLMULQDQ instruction

Premium Partner