Jacobi quartic curves revisited. (English) Zbl 1284.94078
Boyd, Colin (ed.) et al., Information security and privacy. 14th Australasian conference, ACISP 2009, Brisbane, Australia, July 1–3, 2009. Proceedings. Berlin: Springer (ISBN 978-3-642-02619-5/pbk). Lecture Notes in Computer Science 5594, 452-468 (2009).
Summary: This paper provides new results about efficient arithmetic on Jacobi quartic form elliptic curves, \(y^2 = dx^4 + 2ax^2 + 1\). With recent bandwidth-efficient proposals, the arithmetic on Jacobi quartic curves became solidly faster than that of Weierstrass curves. These proposals use up to 7 coordinates to represent a single point. However, fast scalar multiplication algorithms based on windowing techniques, precompute and store several points which require more space than what it takes with 3 coordinates. Also note that some of these proposals require \(d = 1\) for full speed. Unfortunately, elliptic curves having 2-times-a-prime number of points, cannot be written in Jacobi quartic form if \(d = 1\). Even worse the contemporary formulae may fail to output correct coordinates for some inputs. This paper provides improved speeds using fewer coordinates without causing the above mentioned problems. For instance, our proposed point doubling algorithm takes only 2 multiplications, 5 squarings, and no multiplication with curve constants when \(d\) is arbitrary and \(a = \pm 1/2\).
For the entire collection see [Zbl 1165.94302].
For the entire collection see [Zbl 1165.94302].
References:
| [1] | Avanzi, R.M.: A note on the signed sliding window integer recoding and its left-to-right analogue. In: Handschuh, H., Hasan, M.A. (eds.) SAC 2004. LNCS, vol. 3357, pp. 130–143. Springer, Heidelberg (2004) · Zbl 1117.94007 · doi:10.1007/978-3-540-30564-4_9 |
| [2] | Billet, O., Joye, M.: The Jacobi model of an elliptic curve and side-channel analysis. In: Fossorier, M.P.C., Høholdt, T., Poli, A. (eds.) AAECC 2003. LNCS, vol. 2643, pp. 34–42. Springer, Heidelberg (2003) · Zbl 1031.94510 · doi:10.1007/3-540-44828-4_5 |
| [3] | Bernstein, D.J., Lange, T.: Analysis and optimization of elliptic-curve single-scalar multiplication. In: Finite Fields and Applications Fq8. Contemporary Mathematics, American Mathematical Society, vol. 461, pp. 1–18 (2008) · doi:10.1090/conm/461/08979 |
| [4] | Bernstein, D.J., Lange, T.: eBACS: ECRYPT benchmarking of cryptographic systems (2008), http://bench.cr.yp.to |
| [5] | Bernstein, D.J., Lange, T.: Explicit-formulas database, http://www.hyperelliptic.org/EFD |
| [6] | Bernstein, D.J., Lange, T.: Faster addition and doubling on elliptic curves. In: Kurosawa, K. (ed.) ASIACRYPT 2007. LNCS, vol. 4833, pp. 29–50. Springer, Heidelberg (2007) · Zbl 1153.11342 · doi:10.1007/978-3-540-76900-2_3 |
| [7] | Bernstein, D.J., Birkner, P., Joye, M., Lange, T., Peters, C.: Twisted Edwards curves. In: Vaudenay, S. (ed.) AFRICACRYPT 2008. LNCS, vol. 5023, pp. 389–405. Springer, Heidelberg (2008) · Zbl 1142.94332 · doi:10.1007/978-3-540-68164-9_26 |
| [8] | Chudnovsky, D.V., Chudnovsky, G.V.: Sequences of numbers generated by addition in formal groups and new primality and factorization tests. Advances in Applied Mathematics 7(4), 385–434 (1986) · Zbl 0614.10004 · doi:10.1016/0196-8858(86)90023-0 |
| [9] | 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) · Zbl 0939.11039 · doi:10.1007/3-540-49649-1_6 |
| [10] | Cohen, H., Frey, G. (eds.): Handbook of Elliptic and Hyperelliptic Curve Cryptography. CRC Press, Boca Raton (2005) · Zbl 1082.94001 |
| [11] | Duquesne, S.: Improving the arithmetic of elliptic curves in the Jacobi model. Information Processing Letters 104(3), 101–105 (2007) · Zbl 1183.94031 · doi:10.1016/j.ipl.2007.05.012 |
| [12] | Eisenträger, K., Lauter, K., Montgomery, P.L.: Fast elliptic curve arithmetic and improved Weil pairing evaluation. In: Joye, M. (ed.) CT-RSA 2003. LNCS, vol. 2612, pp. 343–354. Springer, Heidelberg (2003) · Zbl 1038.11079 · doi:10.1007/3-540-36563-X_24 |
| [13] | Euler, L.: De integratione aequationis differentialis \(m \, dx/\sqrt{1-x^4} = n \, dy/\sqrt{1-y^4}\) . Novi Commentarii Academiae Scientiarum Petropolitanae 6, 37–57 (1761); Translated from the Latin by Langton, S.G. On the integration of the differential equation \(m \, dx/\sqrt{1-x^4} = n \, dy/\sqrt{1-y^4}\) , http://home.sandiego.edu/ langton/eell.pdf |
| [14] | Galbraith, S.D., Lin, X., Scott, M.: Endomorphisms for faster elliptic curve cryptography on a large class of curves. In: EUROCRYPT 2009. LNCS, vol. 5479, pp. 518–535. Springer, Heidelberg (2009) · Zbl 1239.94048 · doi:10.1007/978-3-642-01001-9_30 |
| [15] | Gaudry, P., Thomé, E.: The mpFq library and implementing curve-based key exchanges. In: SPEED 2007, pp.49–64 (2007), http://www.loria.fr/ gaudry/publis/mpfq.pdf |
| [16] | Hankerson, D., Menezes, A.J., Vanstone, S.A.: Guide to Elliptic Curve Cryptography. Springer, New York (2003) · Zbl 1059.94016 |
| [17] | Hisil, H., Carter, G., Dawson, E.: New formulae for efficient elliptic curve arithmetic. In: Srinathan, K., Rangan, C.P., Yung, M. (eds.) INDOCRYPT 2007. LNCS, vol. 4859, pp. 138–151. Springer, Heidelberg (2007) · Zbl 1153.94390 · doi:10.1007/978-3-540-77026-8_11 |
| [18] | Hisil, H., Wong, K.K., Carter, G., Dawson, E.: Faster group operations on elliptic curves. In: Australasian Information Security Conference (AISC 2009), Wellington, New Zealand (January 2009); Conferences in Research and Practice in Information Technology (CRPIT), vol. 98, pp. 7–19 (2009) |
| [19] | Hisil, H., Wong, K.K., Carter, G., Dawson, E.: Twisted Edwards curves revisited. In: Pieprzyk, J. (ed.) ASIACRYPT 2008. LNCS, vol. 5350, pp. 326–343. Springer, Heidelberg (2008) · Zbl 1206.94074 · doi:10.1007/978-3-540-89255-7_20 |
| [20] | Jacobi, C.G.J.: Fundamenta nova theoriae functionum ellipticarum. Sumtibus Fratrum Borntræger (1829) |
| [21] | Longa, P., Gebotys, C.: Novel precomputation schemes for elliptic curve cryptosystems. In: ACNS 2009. LNCS. Springer, Heidelberg (to appear, 2009) · Zbl 1227.94054 |
| [22] | 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) · Zbl 1030.11075 · doi:10.1007/3-540-36552-4_21 |
| [23] | Monagan, M., Pearce, R.: Rational simplification modulo a polynomial ideal. In: ISSAC 2006, pp. 239–245. ACM, New York (2006) · Zbl 1356.13037 |
| [24] | Whittaker, E.T., Watson, G.N.: A Course of Modern Analysis. Cambridge University Press, Cambridge (1927) · JFM 45.0433.02 |
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.
