Advertisement

An Advanced Method for Joint Scalar Multiplications on Memory Constraint Devices

  • Erik Dahmen
  • Katsuyuki Okeya
  • Tsuyoshi Takagi
Conference paper
Part of the Lecture Notes in Computer Science book series (LNCS, volume 3813)

Abstract

One of the most frequent operations in modern cryptosystems is a multi-scalar multiplication with two scalars. Common methods to compute it are the Shamir method and the Interleave method whereas their speed mainly depends on the (joint) Hamming weight of the scalars. To increase the speed, the scalars are usually deployed using some general representation which provides a lower (joint) Hamming weight than the binary representation. However, by using such general representations the precomputation and storing of some points becomes necessary and therefore more memory is required. Probably the most famous method to speed up the Shamir method is the joint sparse form (JSF). The resulting representation has an average joint Hamming weight of 1/2 and it uses the digits 0,± 1. To compute a multi-scalar multiplication with the JSF, the precomputation of two points is required. While for two precomputed points both the Shamir and the Interleave method provide the same efficiency, until now the Interleave method is faster in any case where more points are precomputed. This paper extends the used digits of the JSF in a natural way, namely we use the digits 0, ±1, ±3 which results in the necessity to precompute ten points. We will prove that using the proposed scheme, the average joint Hamming density is reduced to 239/661 ≈ 0.3615. Hence, a multi-scalar multiplication can be computed more than 10% faster, compared to the JSF. Further, our scheme is superior to all known methods using ten precomputed points and is therefore the first method to improve the Shamir method such that it is faster than the Interleave method. Another advantage of the new representation is, that it is generated starting at the most significant bit. More specific, we need to store only up to 5 joint bits of the new representation at a time. Compared to representations which are generated starting at the least significant bit, where we have to store the whole representation, this yields a significant saving of memory.

Keywords

elliptic curve cryptosystem joint sparse form left-to-right multi-scalar multiplication shamir method 

Preview

Unable to display preview. Download preview PDF.

Unable to display preview. Download preview PDF.

References

  1. [Ava02]
    Avanzi, R.: On multi-exponentiation in cryptography, Cryptology ePrint Archive: Report 2002/154 (2002), available at http://eprint.iacr.org/2002/154/
  2. [Ava04]
    Avanzi, R.: A Note on the Signed Sliding Window Integer Recoding and a Left-to-Right Analogue. In: Handschuh, H., Hasan, M.A. (eds.) SAC 2004. LNCS, vol. 3357, pp. 130–143. Springer, Heidelberg (2004)CrossRefGoogle Scholar
  3. [BSS99]
    Blake, I., Seroussi, G., Smart, N.: Elliptic Curves in Cryptography. Cambridge University Press, Cambridge (1999)zbMATHGoogle Scholar
  4. [CMO98]
    Cohen, H., Miyaji, A., Ono, T.: Efficient Elliptic Curve Exponentiation Using Mixed Coordinates. In: Ohta, K., Pei, D. (eds.) ASIACRYPT 1998. LNCS, vol. 1514, pp. 51–65. Springer, Heidelberg (1998)CrossRefGoogle Scholar
  5. [ElG85]
    ElGamal, T.: A Public Key Cryptosystem and a Signature Scheme Based on Discrete Logarithms. IEEE Transactions on Information Theory 31, 469–472 (1985)zbMATHCrossRefMathSciNetGoogle Scholar
  6. [GHPT03]
    Grabner, P., Heuberger, C., Prodinger, H., Thuswaldner, J.: Analysis of linear combination algorithms in cryptography, available at http://www.opt.math.tu-graz.ac.at/~cheub/publications/
  7. [Gor98]
    Gordon, D.: A survey of fast exponentiation methods. Journal of Algorithms 27, 129–146 (1998)zbMATHCrossRefMathSciNetGoogle Scholar
  8. [Häg02]
    Häggström, O.: Finite Markov Chains and Algorithmic Applications. In: London Mathematical Society Student Texts, vol. 52, Cambridge University Press, Cambridge (2002)Google Scholar
  9. [HKPR04]
    Heuberger, C., Katti, R., Prodinger, H., Ruan, X.: The Alternating Greedy Expansion and Applications to Left-To-Right Algorithms in Cryptography, available at http://www.opt.math.tu-graz.ac.at/~cheub/publications/
  10. [Kob87]
    Koblitz, N.: Elliptic Curve Cryptosystems. Math. Comp. 48, 203–209 (1987)zbMATHCrossRefMathSciNetGoogle Scholar
  11. [KZZ04]
    Kuang, B., Zhu, Y., Zhang, Y.: An Improved Algorithm for uP+vQ using JSF 3. In: Jakobsson, M., Yung, M., Zhou, J. (eds.) ACNS 2004. LNCS, vol. 3089, pp. 467–478. Springer, Heidelberg (2004)CrossRefGoogle Scholar
  12. [Mil86]
    Miller, V.S.: Use of Elliptic Curves in Cryptography. In: Williams, H.C. (ed.) CRYPTO 1985. LNCS, vol. 218, pp. 417–426. Springer, Heidelberg (1986)Google Scholar
  13. [MOC97]
    Miyaji, A., Ono, T., Cohen, H.: Efficient Elliptic Curve Exponentiation. In: Han, Y., Quing, S. (eds.) ICICS 1997. LNCS, vol. 1334, pp. 282–291. Springer, Heidelberg (1997)CrossRefGoogle Scholar
  14. [MO90]
    Morain, F., Olivos, J.: Speeding Up the Computations on an Elliptic Curve using Addition-Subtraction Chains. Informa. Theor. Appl. 24, 531–543 (1990)zbMATHMathSciNetGoogle Scholar
  15. [Möl01]
    Möller, B.: Algorithms for Multi-exponentiation. In: Vaudenay, S., Youssef, A.M. (eds.) SAC 2001. LNCS, vol. 2259, pp. 165–180. Springer, Heidelberg (2001)CrossRefGoogle Scholar
  16. [Möl02]
    Möller, B.: Improved Techniques for Fast Exponentiation. In: Lee, P.J., Lim, C.H. (eds.) ICISC 2002. LNCS, vol. 2587, pp. 298–312. Springer, Heidelberg (2003)CrossRefGoogle Scholar
  17. [Möl04]
    Möller, B.: Fractional Windows Revisited: Improved Signed-Digit Representations for Efficient Exponentiation. In: Park, C.-s., Chee, S. (eds.) ICISC 2004. LNCS, vol. 3506, pp. 137–153. Springer, Heidelberg (2005) (to appear)CrossRefGoogle Scholar
  18. [OSST04]
    Okeya, K., Schmidt-Samoa, K., Spahn, C., Takagi, T.: Signed Binary Representations Revisited. In: Franklin, M. (ed.) CRYPTO 2004. LNCS, vol. 3152, pp. 123–139. Springer, Heidelberg (2004), available at http://eprint.iacr.org/2004/195/ Google Scholar
  19. [Pro03]
    Proos, J.: Joint Sparse Forms and Generating Zero Columns when Combing, Technical Report of the Centre for Applied Cryptographic Research, University of Waterloo - CACR, CORR 2003-23 (2003), available at http://www.cacr.math.uwaterloo.ca
  20. [SST04]
    Schmidt-Samoa, K., Semay, O., Takagi, T.: Analysis of Some Efficient Window Methods and their Application to Elliptic Curve Cryptosystems, Technical Report No. TI-3/04, 16 (August 2004)Google Scholar
  21. [Sol00]
    Solinas, J.A.: Efficient Arithmetic on Koblitz Curves. Design, Codes and Cryptography 19, 195–249 (2000)zbMATHCrossRefMathSciNetGoogle Scholar
  22. [Sol01]
    Solinas, J.A.: Low-weight binary representations for pairs of integers, Technical Report of the Centre for Applied Cryptographic Research, University of Waterloo - CACR, CORR 2001-41 (2001), available at http://www.cacr.math.uwaterloo.ca

Copyright information

© Springer-Verlag Berlin Heidelberg 2005

Authors and Affiliations

  • Erik Dahmen
    • 1
  • Katsuyuki Okeya
    • 2
  • Tsuyoshi Takagi
    • 3
  1. 1.Fachbereich InformatikTechnische Universität DarmstadtDarmstadtGermany
  2. 2.Hitachi, Ltd., Systems Development LaboratoryKanagawa-kenJapan
  3. 3.Future University – HakodateHokkaidoJapan

Personalised recommendations