Skip to main content
placeholder image

Efficient Fixed-base exponentiation and scalar multiplication based on a multiplicative splitting exponent recoding

Journal Article


Abstract


  • Digital signature algorithm (DSA) (resp. ECDSA) involves modular exponentiation (resp. scalar multiplication) of a public and known base by a random one-time exponent. In order to speed up this operation, well-known methods take advantage of the memorization of base powers (resp. base multiples). Best approaches are the Fixed-base radix-R method and the Fixed-base Comb method. In this paper, we present a new approach for storage/online computation trade-off, by using a multiplicative splitting of the digits of the exponent radix-R representation. We adapt classical algorithms for modular exponentiation and scalar multiplication in order to take advantage of the proposed exponent recoding. An analysis of the complexity for practical size shows that our proposed approach involves a lower storage for a given level of online computation. This is confirmed by implementation results showing significant memory saving, up to 3 times for the largest NIST standardized key sizes, compared to the state-of-the-art approaches.

UOW Authors


  •   Robert, Jean-Marc (external author)
  •   Negre, Christophe (external author)
  •   Plantard, Thomas

Publication Date


  • 2019

Citation


  • Robert, J., Negre, C. & Plantard, T. (2019). Efficient Fixed-base exponentiation and scalar multiplication based on a multiplicative splitting exponent recoding. Journal of Cryptographic Engineering, 9 (2), 115-136.

Scopus Eid


  • 2-s2.0-85065892545

Number Of Pages


  • 21

Start Page


  • 115

End Page


  • 136

Volume


  • 9

Issue


  • 2

Place Of Publication


  • Germany

Abstract


  • Digital signature algorithm (DSA) (resp. ECDSA) involves modular exponentiation (resp. scalar multiplication) of a public and known base by a random one-time exponent. In order to speed up this operation, well-known methods take advantage of the memorization of base powers (resp. base multiples). Best approaches are the Fixed-base radix-R method and the Fixed-base Comb method. In this paper, we present a new approach for storage/online computation trade-off, by using a multiplicative splitting of the digits of the exponent radix-R representation. We adapt classical algorithms for modular exponentiation and scalar multiplication in order to take advantage of the proposed exponent recoding. An analysis of the complexity for practical size shows that our proposed approach involves a lower storage for a given level of online computation. This is confirmed by implementation results showing significant memory saving, up to 3 times for the largest NIST standardized key sizes, compared to the state-of-the-art approaches.

UOW Authors


  •   Robert, Jean-Marc (external author)
  •   Negre, Christophe (external author)
  •   Plantard, Thomas

Publication Date


  • 2019

Citation


  • Robert, J., Negre, C. & Plantard, T. (2019). Efficient Fixed-base exponentiation and scalar multiplication based on a multiplicative splitting exponent recoding. Journal of Cryptographic Engineering, 9 (2), 115-136.

Scopus Eid


  • 2-s2.0-85065892545

Number Of Pages


  • 21

Start Page


  • 115

End Page


  • 136

Volume


  • 9

Issue


  • 2

Place Of Publication


  • Germany