Constructing Elliptic Curves for the GLV Method with Low-cost Decomposition

• Autorzy: Wroński M. , Dryło R. , Kijko T. , Bora P.

Identyfikatory

DOI

10.3233/FI-2017-1546

• Języki publikacji: EN

Abstrakty

EN

The GLV method allows to improve scalar multiplication on an elliptic curve E/F_qwith an efficiently computable endomorphism Φ : E → E over F_q. For points in a subgroup of large prime order r this requires decomposition of scalar k = k₀ + k₁λ mod r, where Φ acts on the subgroup of order r as multiplication by λ ∊ F_r and k₀, k₁ are integers O(√r) . In this note we consider the case when λ is of the form λ = 2^s + a, where a is a small integer and λ=O(√r), which allows very easy and fast decomposition of k especially in hardware implementations. We give a method to construct such elliptic curves based on the complex multiplication method, and give examples of elliptic curves for λ ∊ {2^s, 2^s - 1} and various security levels.

Słowa kluczowe

EN

CM method; efficient hardware implementation; elliptic curves; GLV method; scalar multiplication

• Wydawca: IOS Press
• Czasopismo: Fundamenta Informaticae
• Rocznik: 2017
• Tom: Vol. 153, nr 4
• Strony: 399--413
• Opis fizyczny: Bibliogr. 18 poz., tab.

Twórcy

autor

Wroński M.

• Institute of Mathematics and Cryptology, Military University of Technology, Kaliskiego 2, 00-908 Warsaw, Poland

autor

Dryło R.

• Warsaw School of Economics, Aleja Niepodległości 162, 02-554 Warszawa, Poland

autor

Kijko T.

• Institute of Mathematics and Cryptology, Military University of Technology, Kaliskiego 2, 00-908 Warsaw, Poland

autor

Bora P.

• Institute of Mathematics and Cryptology, Military University of Technology, Kaliskiego 2, 00-908 Warsaw, Poland

Bibliografia

• [1] Bröker and R, Stevenhagen P. Efficient CM-constructions of elliptic curves over finite fields, Math. Comp. 2007;76(260):2161-2179. URL: http://www.jstor.org/stable/40234483.
• [2] Cohen H, Frey G. Handbook of Elliptic and Hyperelliptic Curve Cryptography, New York: Chapman & Hall/CRC, 2006. ISBN:1584885181.
• [3] Dryło R, Jelonek Z. Constructing elliptic curves with a subgroup of a given order and with a given endomorphism ring (in Polish), Studia Bezpieczeństwa Narodowego, rok IV, nr 6, 2014.
• [4] Faz-Hernandez A, Longa P, Sanchez A. Efficient and Secure Algorithms for GLV-Based Scalar Multiplication and their implementation on GLV-GLS Curves. URL https://eprint.iacr.org/2013.
• [5] Galbraith SD, Lin X, and Scott M. Endomorphisms for faster elliptic curve cryptography on a large class of curves, J. Cryptology, 2011;24(3):446–469. doi:10.1007/s00145-010-9065-y.
• [6] Gallant R, Lambert R, Vanstone S. Faster point multiplication on elliptic curves with efficient endomorphisms, In: Kilian, J. (ed.) CRYPTO. LNCS, vol. 2139, pp. 190–200. Springer (2001) URL http://dl.acm.org/citation.cfm?id=646766.704144.
• [7] Heegner K. Diophantische Analysis und Modulfunktionen, Math. Z. 1952;56:227-253. URL http://eudml.org/doc/169287.
• [8] Koblitz N. CM-curves with good cryptographic properties, Advances in Cryptology Crypto ’91, 1992, pp. 279–287. URL http://dl.acm.org/citation.cfm?id=646756.705386.
• [9] Lang S. Elliptic functions, Springer, vol. 112, 1987. doi:10.1007/978-1-4612-4752-4.
• [10] Lay G, Zimmer H. Constructing elliptic curves with given group order over large finite fields, Algorithmic Number theory Symposium I, Springer Lecture Notes in Computer Science, 1994, MR1322728 (96a:11054) http://dl.acm.org/citation.cfm?id=648182.749421.
• [11] Satoh T, and Araki K. Fermat quotients and the polynomial time discrete log algorithm for anomalous elliptic curves, Commentarii Math. Univ. St. Pauli 1998;47(1):81-92.
• [12] Semaev I. Evaluation of discrete logarithms in a group of p-torsion points of an elliptic curve in characteristic p, Math. Comp., 1998;67(221):353-356. URL https://doi.org/10.1090/S0025-5718-98-00887-4.
• [13] Sica F, Ciet M, Quisquater JJ. Analysis of the Gallant-Lambert-Vanstone Method based on Efficient Endomorphisms: Elliptic and Hyperelliptic Curves, In K. Nyberg and H. M. Heys (eds.), SAC 2002, Springer LNCS 2003;2595:21–36. doi:10.1007/3-540-36492-7 3.
• [14] Silverman J. Advanced Topics in the Arithmetic of Elliptic Curves, Springer-Verlag, GTM 151, 1995. doi:10.1007/978-1-4612-0851-8.
• [15] Smart NP. The discrete logarithm problem on elliptic curves of trace one, Journal of cryptology, 1999;12(3):193–196. doi:10.1007/s001459900052.
• [16] Solinas JA. Efficient arithmetic on Koblitz curves, Designs. Codes and Cryptography, 2000;19(2-3):195–249. doi:10.1023/A:1008306223194.
• [17] Solinas JA. Low-Weight Binary Representations for Pairs of Integers, Technical Report CORR 2001–41, CACR, 2001.
• [18] Sutherland A. Computing Hilbert class polynomials with the Chinese remainder theorem, Math. Comp., 2011;80:501-538. URL https://doi.org/10.1090/S0025-5718-2010-02373-7.