Geodesic
Small scalar multiplication on Weierstrass curves using division polynomials
Matematičeskie voprosy kriptografii, Tome 13 (2022) no. 2, pp. 17-35 Cet article a éte moissonné depuis la source Math-Net.Ru

Voir la notice de l'article

This paper deals with elliptic curves in the short Weierstrass form over large prime fields and presents algorithms for computing small odd multiples of a given point $P$ on a curve. Our algorithms make use of division polynomials and are more efficient than the naive algorithm based on repeated additions with $2P$. We show how to perform scalar multiplication in the variable base settings using the precomputed small multiples. By employing the window method and avoiding conditional branches, we achieve the constant-time property for the final scalar multiplication algorithm. Small multiples are computed in either Jacobian or affine coordinates. To obtain affine coordinates, we use Montgomery's trick of simultaneous multiplicative inversion of several field elements. The conversion to affine coordinates slows down the precomputations but speeds up the main scalar multiplication loop. We show that the conversion makes sense and gives an overall performance boost in practical settings. 
@article{MVK_2022_13_2_a2,
     author = {S. V. Agievich and S. V. Poruchnik and V. I. Semenov},
     title = {Small scalar multiplication on {Weierstrass} curves using~division polynomials},
     journal = {Matemati\v{c}eskie voprosy kriptografii},
     pages = {17--35},
     year = {2022},
     volume = {13},
     number = {2},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/MVK_2022_13_2_a2/}
}
TY  - JOUR
AU  - S. V. Agievich
AU  - S. V. Poruchnik
AU  - V. I. Semenov
TI  - Small scalar multiplication on Weierstrass curves using division polynomials
JO  - Matematičeskie voprosy kriptografii
PY  - 2022
SP  - 17
EP  - 35
VL  - 13
IS  - 2
UR  - http://geodesic.mathdoc.fr/item/MVK_2022_13_2_a2/
LA  - en
ID  - MVK_2022_13_2_a2
ER  - 
%0 Journal Article
%A S. V. Agievich
%A S. V. Poruchnik
%A V. I. Semenov
%T Small scalar multiplication on Weierstrass curves using division polynomials
%J Matematičeskie voprosy kriptografii
%D 2022
%P 17-35
%V 13
%N 2
%U http://geodesic.mathdoc.fr/item/MVK_2022_13_2_a2/
%G en
%F MVK_2022_13_2_a2
S. V. Agievich; S. V. Poruchnik; V. I. Semenov. Small scalar multiplication on Weierstrass curves using division polynomials. Matematičeskie voprosy kriptografii, Tome 13 (2022) no. 2, pp. 17-35. http://geodesic.mathdoc.fr/item/MVK_2022_13_2_a2/

[1] Bernstein D. J., Lange T., Explicit-formulas database, , 2007 http://hyperelliptic.org/EFD

[2] Bernstein D. J., Lange T., “Faster addition and doubling on elliptic curves”, ASIACRYPT 2007, Lect. Notes Comput. Sci., 4833, 2007, 29–50 | DOI | MR | Zbl

[3] Bernstein D. J., Birkner P., Joye M., Lange T., Peters C., “Twisted Edwards curves”, AFRICACRYPT 2008, Lect. Notes Comput. Sci., 5023, 2008, 389–405 | DOI | MR | Zbl

[4] Edwards H. M., “A normal form for elliptic curves”, Bull. (New Series) Amer. Math. Soc., 44:3 (2007), 393–422 | DOI | MR | Zbl

[5] Hamburg M., Faster Montgomery and double-add ladders for short Weierstrass curves, Cryptology ePrint Archive, Report 2020/437, , 2020 https://eprint.iacr.org/2020/437 | Zbl

[6] Hankerson D., Menezes A. J., Vanstone S., Guide to Elliptic Curve Cryptography, Springer-Verlag, 2003 | MR

[7] Joye M., Tunstall M., “Exponent recoding and regular exponentiation algorithms”, AFRICACRYPT 2009, Lect. Notes Comput. Sci., 5580, 2008, 334–349 | DOI | MR

[8] Kanayama N., Liu Y., Okamoto E., Saito K., Teruya T., Uchiyama S., “Implementation of an elliptic curve scalar multiplication method using division polynomials”, IEICE Trans. Fund. Electr., Communic. Comput. Sci., E97.A:1 (2014), 300–302 | DOI

[9] Koblitz N., “Elliptic curve cryptosystems”, Math. Comput., 48:177 (1987), 203–209 | DOI | MR | Zbl

[10] Langley A., Hamburg M., Turner S., Elliptic curves for security, Request for Comments, 7748, RFC Editor, 2016 https://rfc-editor.org/rfc/rfc7748.txt

[11] Longa P., Miri A., “New composite operations and precomputation scheme for elliptic curve cryptosystems over prime fields”, PKC 2008, Lect. Notes Comput. Sci., 4939, 2008, 229–247 | DOI | MR | Zbl

[12] Longa P., Miri A., New multibase non-adjacent form scalar multiplication and its application to elliptic curve cryptosystems (extended version), Cryptology ePrint Archive, Report 2008/052, , 2008 https://eprint.iacr.org/2008/052

[13] Meloni N., “New Point Addition Formulae for ECC Applications”, WAIFI 2007, Lect. Notes Comput. Sci., 4547, 1986, 189–201 | DOI | MR

[14] Miller V. S., “Use of elliptic curves in cryptography”, CRYPTO'85, Lect. Notes Comput. Sci., 218, 1986, 417–426 | DOI | MR | Zbl

[15] Montgomery P., “Speeding the Pollard and elliptic curve methods of factorization”, Math. Comput., 48:177 (1987), 243–264 | DOI | MR | Zbl

[16] Okeya K., Takagi T., “The width-$w$ NAF method provides small memory and fast elliptic scalar multiplications secure against side channel attacks”, CT-RSA 2003, Lect. Notes Comput. Sci., 2612, 2003, 328–342 | DOI | MR | Zbl

[17] Renes J., Costello C., Batina L., “Complete addition formulas for prime order elliptic curves”, EUROCRYPT 2016, Lect. Notes Comput. Sci., 9665, 2007, 403–428 | DOI | MR

[18] Rivain M., Fast and Regular Algorithms for Scalar Multiplication over Elliptic Curves, Cryptology ePrint Archive, Report 2011/338, , 2011 https://eprint.iacr.org/2011/338

[19] Shipsey R., Elliptic Divisibility Sequences, PhD thesis, Univ. of London, Goldsmiths, 2001

[20] Stange K. E., “The tate pairing via elliptic nets”, Pairing 2007, Lect. Notes Comput. Sci., 4575, 2007, 329–348 | DOI | MR | Zbl