×

Sublinear scalar multiplication on hyperelliptic Koblitz curves. (English) Zbl 1266.94023

Miri, Ali (ed.) et al., Selected areas in cryptography. 18th international workshop, SAC 2011, Toronto, ON, Canada, August 11–12, 2011. Revised selected papers. Berlin: Springer (ISBN 978-3-642-28495-3/pbk). Lecture Notes in Computer Science 7118, 399-411 (2012).
Summary: Recently, V. S. Dimitrov et. al. [IEEE Trans. Comput. 57, No. 11, 1469–1481 (2008; doi:10.1109/TC.2008.65)] proposed a novel algorithm for scalar multiplication of points on elliptic Koblitz curves that requires a provably sublinear number of point additions in the size of the scalar. Following some ideas used by this article, most notably double-base expansions for integers, we generalize their methods to hyperelliptic Koblitz curves of arbitrary genus over any finite field, obtaining a scalar multiplication algorithm requiring a sublinear number of divisor additions.
For the entire collection see [Zbl 1234.94005].

MSC:

94A60 Cryptography
14G50 Applications to coding theory and cryptography of arithmetic geometry
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Avanzi, R., Dimitrov, V., Doche, C., Sica, F.: Extending Scalar Multiplication Using Double Bases. In: Lai, X., Chen, K. (eds.) ASIACRYPT 2006. LNCS, vol. 4284, pp. 130–144. Springer, Heidelberg (2006) · Zbl 1172.94558 · doi:10.1007/11935230_9
[2] Cohen, H., Frey, G., Avanzi, R., Doche, C., Lange, T., Nguyen, K., Vercauteren, F. (eds.): Handbook of elliptic and hyperelliptic curve cryptography. Discrete Mathematics and its Applications (Boca Raton). Chapman & Hall/CRC, Boca Raton (2006); MR2162716 (2007f:14020) · Zbl 1082.94001
[3] Dimitrov, V.S., Jullien, G.A., Miller, W.C.: An algorithm for modular exponentiation. Inform. Process. Lett. 66(3), 155–159 (1998); MR 1627991 (99d:94023) · Zbl 1078.94510 · doi:10.1016/S0020-0190(98)00044-1
[4] Dimitrov, V.S., Imbert, L., Zakaluzny, A.: Multiplication by a constant is sublinear. In: IEEE Symposium on Computer Arithmetic 2007, pp. 261–268 (2007) · doi:10.1109/ARITH.2007.24
[5] Dimitrov, V.S., Järvinen, K.U., Jacobson Jr., M.J., Chan, W.F., Huang, Z.: Provably sublinear point multiplication on Koblitz curves and its hardware implementation. IEEE Trans. Comput. 57(11), 1469–1481 (2008); MR2464687 (2009j:68053) · Zbl 1367.11088 · doi:10.1109/TC.2008.65
[6] Doche, C., Kohel, D.R., Sica, F.: Double-Base Number System for Multi-scalar Multiplications. In: Joux, A. (ed.) EUROCRYPT 2009. LNCS, vol. 5479, pp. 502–517. Springer, Heidelberg (2009) · Zbl 1239.94046 · doi:10.1007/978-3-642-01001-9_29
[7] Enge, A.: Computing discrete logarithms in high-genus hyperelliptic Jacobians in provably subexponential time. Math. Comp. 71(238), 729–742 (2002); (electronic). MR 1885624 (2003b:68083) · Zbl 0988.68069 · doi:10.1090/S0025-5718-01-01363-1
[8] Günther, C., Lange, T., Stein, A.: Speeding up the Arithmetic on Koblitz Curves of Genus Two. In: Stinson, D.R., Tavares, S. (eds.) SAC 2000. LNCS, vol. 2012, pp. 106–117. Springer, Heidelberg (2001); MR 1895585 (2003c:94024) · Zbl 0976.94014 · doi:10.1007/3-540-44983-3_8
[9] Koblitz, N.: Elliptic curve cryptosystems. Math. Comp. 48(177), 203–209 (1987); MR 866109 (88b:94017) · Zbl 0622.94015 · doi:10.1090/S0025-5718-1987-0866109-5
[10] Koblitz, N.: CM-Curves with Good Cryptographic Properties. In: Feigenbaum, J. (ed.) CRYPTO 1991. LNCS, vol. 576, pp. 279–287. Springer, Heidelberg (1992) · Zbl 0780.14018 · doi:10.1007/3-540-46766-1_22
[11] Lange, T.: Efficient arithmetic on hyperelliptic curves, Ph.D. thesis, Universität-Gesamthochschule Essen, Essen, Germany (2001) · Zbl 1047.94008
[12] 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) · doi:10.1007/3-540-39799-X_31
[13] Solinas, J.A.: Efficient arithmetic on Koblitz curves. Des. Codes Cryptogr. 19(2-3), 195–249 (2000) · Zbl 0997.94017 · doi:10.1023/A:1008306223194
[14] Tijdeman, R.: On the maximal distance between integers composed of small primes. Compositio. Math. 28, 159–162 (1974); MR 0345917 (49 #10646) · Zbl 0283.10024
[15] Vercauteren, F.: Computing Zeta Functions of Hyperelliptic Curves Over Finite Fields of Characteristic 2. In: Yung, M. (ed.) CRYPTO 2002. LNCS, vol. 2442, pp. 369–384. Springer, Heidelberg (2002) · Zbl 1023.14007 · doi:10.1007/3-540-45708-9_24
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.