×

zbMATH — the first resource for mathematics

Toric forms of elliptic curves and their arithmetic. (English) Zbl 1228.14024
Since the discovery of the elliptic curve factorization method [H. W. Lenstra jun., Ann. Math. (2) 126, 649–673 (1987; Zbl 0629.10006)] and the introduction of elliptic curve cryptography by V. S. Miller [in: Advances in Cryptology – Crypto’85, Springer-Verlag, Lect. Notes Comput. Sci. 218, 417–426 (1986; Zbl 0589.94005)] and N. Koblitz [Math. Comput. 48, 203–209 (1987; Zbl 0622.94015)], there has been a continuous interest in speeding up addition/doubling and (multi)-scalar multiplication on elliptic curves. The goal of this paper is to provide new forms of equations of elliptic curves leading to efficient arithmetic. The paper analyzes a large class of forms over a field of sufficiently large characteristic. The class is inspired by classical results from toric geometry that give a natural classification of elliptic curves based on the Newton polytope of the defining polynomial. The class consists of over 50 000 one-parameter families of elliptic curves, all of which were scanned for efficient arithmetic by using an algorithm that combines interpolation techniques and lattice reduction. As a conclusion, some optimality results on Edwards and Montgomery doubling are presented and it is illustrated how toric geometry might serve as a source of inspiration in finding good projective coordinate systems and in finding elliptic curve shapes allowing for complete group operation formulas.

MSC:
14G50 Applications to coding theory and cryptography of arithmetic geometry
14H52 Elliptic curves
14Q05 Computational aspects of algebraic curves
11G20 Curves over finite and local fields
Software:
Curve25519; EFD; Magma
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Achter, J.D., Results of Cohen-Lenstra type for quadratic function fields, (), 1-8 · Zbl 1166.11018
[2] Batyrev, V.V., Variations of the mixed Hodge structure of affine hypersurfaces in algebraic tori, Duke math. J., 69, 2, 349-409, (1993) · Zbl 0812.14035
[3] Beelen, P., A generalization of baker’s theorem, Finite fields appl., 15, 5, 558-568, (2009) · Zbl 1219.11174
[4] Bernstein, D.J., Curve25519: new diffie-hellman speed records, (), 207-228 · Zbl 1151.94480
[5] Bernstein, D.J.; Birkner, P.; Joye, M.; Lange, T.; Peters, C., Twisted edwards curves, (), 389-405 · Zbl 1142.94332
[6] Bernstein, D.J.; Lange, T., Faster addition and doubling on elliptic curves, (), 29-50 · Zbl 1153.11342
[7] Bernstein, D.J., Lange, T., 2011. EFD. Explicit-formulas database. http://www.hyperelliptic.org/EFD/.
[8] Bernstein, D.J.; Lange, T.; Rezaeian Farashahi, R., Binary edwards curves, (), 244-265
[9] Billet, O.; Joye, M., The Jacobi model of an elliptic curve and side-channel analysis, (), 34-42 · Zbl 1031.94510
[10] Bosma, W.; Cannon, J.; Playoust, C., The magma algebra system. I. the user language, J. symbolic comput., 24, 3-4, 235-265, (1997) · Zbl 0898.68039
[11] Brier, E.; Joye, M., Weierstrass elliptic curves and side-channel attacks, (), 335-345 · Zbl 1055.94512
[12] Castryck, W., 2008. Forms of elliptic curves. Talk at BCRYPT ECC day, 2008/03/20, Leuven (Belgium). · Zbl 1228.11006
[13] Castryck, W.; Denef, J.; Vercauteren, F., Computing zeta functions of nondegenerate curves, IMRP int. math. res. pap. art. ID 72017, 57, (2006) · Zbl 1161.14302
[14] Castryck, W., Hubrechts, H., 2010. The distribution of the number of points modulo an integer on elliptic curves over finite fields (in preparation). http://arxiv.org/abs/0902.4332. · Zbl 1264.14044
[15] Chudnovsky, D.V.; Chudnovsky, G.V., Sequences of numbers generated by addition in formal groups and new primality and factorization tests, Adv. in appl. math., 7, 4, 385-434, (1986) · Zbl 0614.10004
[16] Handbook of elliptic and hyperelliptic curve cryptography, () · Zbl 1082.94001
[17] Cohen, H.; Miyaji, A.; Ono, T., Efficient elliptic curve exponentiation using mixed coordinates, (), 51-65 · Zbl 0939.11039
[18] Doche, C.; Icart, T.; Kohel, D., Efficient scalar multiplication by isogeny decompositions, (), 191-206 · Zbl 1151.94506
[19] Fulton, W., Introduction to toric varieties, () · Zbl 1083.14065
[20] Gaudry, P.; Lubicz, D., The arithmetic of characteristic 2 Kummer surfaces and of elliptic Kummer lines, Finite fields appl., 15, 2, 246-260, (2009) · Zbl 1220.14023
[21] Gel’fand, I.M.; Kapranov, M.M.; Zelevinsky, A.V., Discriminants, resultants, and multidimensional determinants, () · Zbl 0827.14036
[22] Harris, J., ()
[23] Hirschfeld, J.W.P., Projective geometries over finite fields, () · Zbl 0899.51002
[24] Hisil, H.; Carter, G.; Dawson, E., New formulae for efficient elliptic curve arithmetic, (), 138-151 · Zbl 1153.94390
[25] Hisil, H.; Koon-Ho Wong, K.; Carter, G.; Dawson, E., Twisted edwards curves revisited, (), 326-343 · Zbl 1206.94074
[26] Hovanskiĭ, A. G., Newton polyhedra, and the genus of complete intersections, Funktsional. anal. i prilozhen., 12, 1, 51-61, (1978)
[27] Joye, M.; Quisquater, J.-J., Hessian elliptic curves and side-channel attacks, (), 402-410 · Zbl 1012.94547
[28] Khetan, A., The resultant of an unmixed bivariate system, International symposium on symbolic and algebraic computation (ISSAC’2002) (Lille), J. symbolic comput., 36, 3-4, 425-442, (2003) · Zbl 1068.14070
[29] Koblitz, N., Elliptic curve cryptosystems, Math. comp., 48, 177, 203-209, (1987) · Zbl 0622.94015
[30] Koelman, R.J., A criterion for the ideal of a projectively embedded toric surface to be generated by quadrics, Beiträge algebra geom., 34, 1, 57-62, (1993) · Zbl 0781.14025
[31] Lange, T., 2008. Binary Edwards curves. Talk at Universidad Autonóma Madrid, 2008/05/09, Madrid (Spain).
[32] Lenstra, H. W., Factoring integers with elliptic curves, Ann. of math. (2), 126, 3, 649-673, (1987) · Zbl 0629.10006
[33] Liardet, P.-Y.; Smart, N., Preventing SPA/DPA in ECC systems using the Jacobi form, (), 391-401 · Zbl 1012.94552
[34] Miller, V., Use of elliptic curves in cryptography, (), 417-426
[35] Monagan, M.; Pearce, R., Rational simplicifation modulo a polynomial ideal, (), 239-245 · Zbl 1356.13037
[36] Montgomery, P.L., Speeding the Pollard and elliptic curve methods of factorization, Math. comp., 48, 177, 243-264, (1987) · Zbl 0608.10005
[37] Okeya, K.; Kurumatani, H.; Sakurai, K., Elliptic curves with the Montgomery-form and their cryptographic applications, (), 238-257 · Zbl 0969.94021
[38] Poonen, B.; Rodriguez-Villegas, F., Lattice polygons and the number 12, Amer. math. monthly, 107, 3, 238-250, (2000) · Zbl 0988.52024
[39] Rezaeian Farashahi, R., Shparlinski, I., 2009. On the number of distinct elliptic curves in some families. Des. Codes Crypt. online publication. · Zbl 1269.11060
[40] Smart, N., The Hessian form of an elliptic curve, (), 118-125 · Zbl 1021.94522
[41] Tsfasman, M.; Vlăduţ, S.; Nogin, D., Algebraic geometric codes: basic notions, () · Zbl 1127.94001
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. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.