On modular decomposition of integers. (English) Zbl 1246.94024
Preneel, Bart (ed.), Progress in cryptology – AFRICACRYPT 2009. Second international conference on cryptology in Africa, Gammarth, Tunisia, June 21–25, 2009. Proceedings. Berlin: Springer (ISBN 978-3-642-02383-5/pbk). Lecture Notes in Computer Science 5580, 386-402 (2009).
Summary: In [Lect. Notes Comput. Sci. 2139, 190–200 (2001; Zbl 1002.94022)], R. P. Gallant et al. showed how to exploit fast endomorphisms on some specific classes of elliptic curves to obtain fast scalar multiplication. The GLV method works by decomposing scalars into two small portions using multiplications, divisions, and rounding operations in the rationals. We present a new simple method based on the extended Euclidean algorithm that uses notably different operations than that of traditional decomposition. We obtain strict bounds on each component. Additionally, we examine the use of random decompositions, useful for key generation or cryptosystems requiring ephemeral keys. Specifically, we provide a complete description of the probability distribution of random decompositions and give bounds for each component in such a way that ensures a concrete level of entropy. This is the first analysis on distribution of random decompositions in GLV allowing the derivation of the entropy and thus an answer to the question first posed by Gallant in 1999.
For the entire collection see [Zbl 1165.94004].
For the entire collection see [Zbl 1165.94004].
Citations:
Zbl 1002.94022References:
| [1] | Gallant, R.P., Lambert, R.J., Vanstone, S.A.: Faster point multiplication on elliptic curves with efficient endomorphisms. In: Kilian, J. (ed.) CRYPTO 2001. LNCS, vol. 2139, pp. 190–200. Springer, Heidelberg (2001) · Zbl 1002.94022 · doi:10.1007/3-540-44647-8_11 |
| [2] | Bellman, R., Straus, E.G.: Problems and Solutions: Solutions of Advanced Problems: 5125. Amer. Math. Monthly 71(7), 806–808 (1964) · doi:10.2307/2310929 |
| [3] | ElGamal, T.: A public key cryptosystem and a signature scheme based on discrete logarithms. IEEE Trans. Inform. Theory 31(4), 469–472 (1985) · Zbl 0571.94014 · doi:10.1109/TIT.1985.1057074 |
| [4] | Galbraith, S.D., Lin, X., Scott, M.: Endomorphisms for faster elliptic curve cryptography on a large class of curves. In: Advances in cryptology–EUROCRYPT 2009. LNCS, Springer, Heidelberg (2009) (to appear) · Zbl 1239.94048 |
| [5] | Gallant, R.: Faster elliptic curve cryptography using efficient endomorphisms. In: 3rd workshop on Elliptic Curve Cryptography–ECC 1999 (1999) (presentation slides) |
| [6] | SECG: Recommended elliptic curve domain parameters. Standards for Efficient Cryptography SEC 2 (September 20, 2000) |
| [7] | ANSI: Public key cryptography for the financial services industry: Key agreement and key transport using elliptical curve cryptography (2001) ANSI X9.63 |
| [8] | Hankerson, D., Menezes, A.J., Vanstone, S.A.: Guide to Elliptic Curve Cryptography. Springer, New York (2004) · Zbl 1059.94016 |
| [9] | Babai, L.: On Lovász’ lattice reduction and the nearest lattice point problem. Combinatorica 6(1), 1–13 (1986) · Zbl 0593.68030 · doi:10.1007/BF02579403 |
| [10] | Kim, D., Lim, S.: Integer decomposition for fast scalar multiplication on elliptic curves. In: Nyberg, K., Heys, H.M. (eds.) SAC 2002. LNCS, vol. 2595, pp. 13–20. Springer, Heidelberg (2003) · Zbl 1125.94325 · doi:10.1007/3-540-36492-7_2 |
| [11] | Sica, F., Ciet, M., Quisquater, J.J.: Analysis of the Gallant-Lambert-Vanstone method based on efficient endomorphisms: elliptic and hyperelliptic curves. In: Nyberg, K., Heys, H.M. (eds.) SAC 2002. LNCS, vol. 2595, pp. 21–36. Springer, Heidelberg (2003) · Zbl 1066.94551 · doi:10.1007/3-540-36492-7_3 |
| [12] | Park, Y.H., Jeong, S., Kim, C.H., Lim, J.: An alternate decomposition of an integer for faster point multiplication on certain elliptic curves. In: Naccache, D., Paillier, P. (eds.) PKC 2002. LNCS, vol. 2274, pp. 323–334. Springer, Heidelberg (2002) · Zbl 1055.94527 · doi:10.1007/3-540-45664-3_23 |
| [13] | Grabner, P.J., Heuberger, C., Prodinger, H.: Distribution results for low-weight binary representations for pairs of integers. Theoret. Comput. Sci. 319(1-3), 307–331 (2004) · Zbl 1050.94009 · doi:10.1016/j.tcs.2004.02.012 |
| [14] | Antipa, A., Brown, D., Gallant, R., Lambert, R., Struik, R., Vanstone, S.: Accelerated verification of ECDSA signatures. In: Preneel, B., Tavares, S. (eds.) SAC 2005. LNCS, vol. 3897, pp. 307–318. Springer, Heidelberg (2006) · Zbl 1151.94595 · doi:10.1007/11693383_21 |
| [15] | Knuth, D.E.: The Art of Computer Programming, Volume II: Seminumerical Algorithms, 2nd edn. Addison-Wesley, Reading (1981) · Zbl 0477.65002 |
| [16] | Järvinen, K., Forsten, J., Skyttä, J.: Efficient circuitry for computing {\(\tau\)}-adic non-adjacent form. In: Proceedings of the 13th IEEE International Conference on Electronics, Circuits and Systems, ICECS 2006, pp. 232–235. IEEE, Los Alamitos (2006) · doi:10.1109/ICECS.2006.379768 |
| [17] | Lange, T., Shparlinski, I.E.: Distribution of some sequences of points on elliptic curves. J. Math. Cryptol. 1(1), 1–11 (2007) · Zbl 1129.14040 · doi:10.1515/JMC.2007.001 |
| [18] | Cohen, H., Frey, G. (eds.): Handbook of elliptic and hyperelliptic curve cryptography. CRC Press, Boca Raton (2005) · Zbl 1082.94001 |
| [19] | IEEE: IEEE P1363 working group for public-key cryptography standards. meeting minutes (November 15, 2000), http://grouper.ieee.org/groups/1363/WorkingGroup/minutes/Nov00.txt |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
