Abstract
Multi-computations in finite groups, such as multiexponentiations and multi-scalar multiplications, are very important in ElGamal-like public key cryptosystems. Algorithms to improve multi-computations can be classified into two main categories: precomputing methods and recoding methods. The first one uses a table to store the precomputed values, and the second one finds a better binary signed-digit (BSD) representation. In this article, we propose a new integer similarity strategy for multi-computations. The proposed strategy can aid with precomputing methods or recoding methods to further improve the performance of multi-computations. Based on the integer similarity strategy, we propose two efficient algorithms to improve the performance for BSD sparse forms. The performance factor can be improved from 1.556 to 1.444 and to 1.407, respectively.
This work was supported by the National Science Council, Taiwan, under contract NSC 92-2213-E-232-002.
Chapter PDF
Similar content being viewed by others
Keywords
References
Arno, S., Wheeler, F.S.: Signed digit representations of minimal hamming weight. IEEE Trans. Computers 42(8), 1007–1010 (1993)
Avanzi, R.M.: On multi-exponentiation in cryptography. IACR Cryptology ePrint Archive 2002/154 (2002), http://eprint.iacr.org
Bernstein, D.J.: Pippenger’s exponentiation algorithm (2002), http://cr.yp.to/antiforgery.html
Brickell, E.F., Gordon, D.M., McCurley, K.S., Wilson, D.B.: Fast exponentiation with precomputation. In: Rueppel, R.A. (ed.) EUROCRYPT 1992. LNCS, vol. 658, pp. 200–207. Springer, Heidelberg (1993)
C¸, K., Ko¸c.: High-speed RSA implementations. RSA Laboratories, Technique Notes TR201, pp. 9–32 (November 1994), http://www.rsasecurity.com/rsalabs
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)
Dimitrov, V.S., Jullien, G.A., Miller, W.C.: Complexity and fast algorithms for multiexponentiation. IEEE Trans. Computers 49(2), 141–147 (2000)
ElGamal, T.: A public key cryptosystem and a signature scheme based on discrete logarithms. IEEE Trans. Information Theory 31(4), 469–472 (1985)
FIPS186-2. Digital signature standard(DSS). NIST Computer Security FIPS page (2001), http://csrc.nist.gov/publications/fips/
Gordon, D.M.: A survey of fast exponentiation methods. Journal of Algorithms 27, 129–146 (1998)
Jedwab, J., Mitchell, C.J.: Minimum weight modified signed-digit representations and fast exponentiation. Electronics Letters 25(17), 1171–1172 (1989)
Joye, M., Yen, S.M.: Optimal left-to-right binary signed-digit recoding. IEEE Trans. Computers 49(7), 740–748 (2000)
Knuth, D.E.: The Art of Computer Programming, Seminumerical Algorithms, 3rd edn., vol. 2. Addison-Wesley, Reading (1998)
Lim, C.H., Lee, P.J.: More flexible exponentiation with precomputation. In: Desmedt, Y.G. (ed.) CRYPTO 1994. LNCS, vol. 839, pp. 95–107. Springer, Heidelberg (1994)
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)
Mishra, P.K.: Scalar multiplication in elliptic curve cryptosystems: Pipelining with pre-computations. IACR Cryptology ePrint Archive 2004/191 (2004), http://eprint.iacr.org
Muir, J., Stinson, D.: Minimality and other properties of the width-w nonadjacent form. Technique Report CORR 2004-08 (2004), http://www.cacr.math.uwaterloo.ca
Okeya, K., Sakurai, K.: Fast multi-scalar multiplication methods on elliptic curves with precomputation strategy using montgomery trick. In: Kaliski Jr., B.S., Koç, Ç.K., Paar, C. (eds.) CHES 2002. LNCS, vol. 2523, pp. 564–578. Springer, Heidelberg (2003)
Okeya, K., Schmidt-Samoa, K., Spahn, C., Takagi, T.: Signed binary representations revisited. IACR Cryptology ePrint Archive 2004/195 (2004), http://eprint.iacr.org
Reitwiesner, G.W.: Binary arithmetic. In: Advance in computers, pp. 231–308 (1960)
Schnorr, C.-P.: Efficient identification and signatures for smart cards. In: Brassard, G. (ed.) CRYPTO 1989. LNCS, vol. 435, pp. 239–252. Springer, Heidelberg (1990)
Solinas, J.A.: Low-weight binary representations for pairs of integers. Technique Report CORR 2001-41 (2001), http://www.cacr.math.uwaterloo.ca
Yen, S.M., Laih, C.S., Lenstra, A.K.: Multiexponentiation. IEE Proc. Computers and Digital Techniques 141(6), 325–326 (1994)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2005 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Yang, WC., Guan, DJ., Laih, CS. (2005). Fast Multi-computations with Integer Similarity Strategy. In: Vaudenay, S. (eds) Public Key Cryptography - PKC 2005. PKC 2005. Lecture Notes in Computer Science, vol 3386. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-540-30580-4_10
Download citation
DOI: https://doi.org/10.1007/978-3-540-30580-4_10
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-24454-7
Online ISBN: 978-3-540-30580-4
eBook Packages: Computer ScienceComputer Science (R0)