Determining Formulas Related to Point Compression on Alternative Models of Elliptic Curves

• Autorzy: Dryło Robert , Kijko Tomasz , Wroński Michał

Identyfikatory

DOI

10.3233/FI-2019-1848

• Języki publikacji: EN

Abstrakty

EN

Let E be an elliptic curve given by any model over a field K. A rational function f : E → K of degree 2 such that f(P) = f(Q) ⇔ Q = ±P can be used as a point compression on E. Then there exists induced from E multiplication of values of f by integers given by [n]f(P) := f([n]P), which can be computed using the Montgomery ladder algorithm. For this algorithm one needs the generalized Montgomery formulas for differential addition and doubling that is rational functions A(X₁, X₂, X₃) ∈ K(X₁, X₂, X₃) and [2] ∈ K(X) such that f(P + Q) = A(f(P), f(Q), f(Q − P)) and [2]f(P) = f([2]P) for generic P,Q ∈ E. For most standard models of elliptic curves generalized Montgomery formulas are known. To use compression for scalar multiplication [n]P for P ∈ E, one can compute after compression [n]f(P), which is followed by [n + 1]f(P) in the Montgomery ladder algorithm, then one can recover [n]P on E, since there exists a rational map B such that [n]P = B(P, [n]f(P), [n + 1]f(P)) for generic P ∈ E and n ∈ Z. Such a map B is known for Weierstrass and Edwards curves, but to our knowledge it seems that it was not given for other models of elliptic curves. In this paper for an elliptic curve E and the above compression function f we give an algorithm to search for generalized Montgomery formulas, functions on K induced after compression by endomorphisms of E, and the above map B for point recovering. All these tasks require searching for solutions of similar type problems for which we describe an algorithm based on Gröbner bases. As applications we give formulas for differential addition, doubling and the above map B for Jacobi quartic, Huff curves, and twisted Hessian curves.

Słowa kluczowe

EN

alternative models of elliptic curves; scalar multiplication; Montgomery ladder; point compression; Gröbner bases

• Wydawca: IOS Press
• Czasopismo: Fundamenta Informaticae
• Rocznik: 2019
• Tom: Vol. 169, nr 4
• Strony: 285--294
• Opis fizyczny: Bibliogr. 22 poz., tab.

Twórcy

autor

Dryło Robert

• Institute of Mathematics and Cryptology, Military University of Technology, Warsaw, Poland

autor

Kijko Tomasz

• Institute of Mathematics and Cryptology, Military University of Technology, Warsaw, Poland

autor

Wroński Michał

• Institute of Mathematics and Cryptology, Military University of Technology, Warsaw, Poland

Bibliografia

• [1] Adams WW, and Loustaunau P. An introduction to Gröbner bases (No. 3). American Mathematical Soc. 1994.
• [2] Bernstein D, Birkner P, Joye M, and Lange T. Ch. Peters, Twisted Edwards curves, In: Progress in Cryptology-AFRICACRYPT 2008, Springer vol. 5023, 2008 pp. 389-405. doi:10.1007/978-3-540-68164-9_26.
• [3] Bernstein D, Chuengsatiansup Ch, Kohel D, and Lange T. Twisted Hessian curves, In: Lecture Notes in Computer Science, Springer vol. 9230, 2015 pp. 269-294. doi:10.1007/978-3-319-22174-8_15.
• [4] Bernstein D, and Lange T. Faster addition and doubling on elliptic curves, In: Advances in cryptology-ASIACRYPT, Springer vol. 4833, 2007 pp. 29-50. doi:10.1007/978-3-540-76900-2_3.
• [5] Billet O, and Joye M. The Jacobi model of an elliptic curve and side-channel analysis, In: AAECC-15 Conference Proceedings, Lecture Notes in Computer Science, Springer vol. 2643, 2003 pp. 34-42. doi:10.1007/3-540-44828-4_5.
• [6] Brier E, and Joye M. Weierstraßelliptic curves and side-channel attacks. In D. Naccache and P. Paillier, editors, Public Key Cryptography, in Lecture Notes in Computer Science, Berlin, Heidelberg, Springer vol. 2274, 2002 pp. 335-345. doi:10.1007/3-540-45664-3_24.
• [7] Castryck W, and Vercauteren F. Toric forms of elliptic curves and their arithmetic, Journal of Symbolic Computation, Elsevier 2011; 46(8):943-966. URL https://doi.org/10.1016/j.jsc.2011.02.003.
• [8] Costello C, Hisil H, and Smith B. Faster compact Diffie-Hellman: endomorphisms on the x-line. In Annual International Conference on the Theory and Applications of Cryptographic Techniques. Springer vol. 8441, 2014 pp. 183-200. doi:10.1007/978-3-642-55220-5_11.
• [9] Cox D, Little J, and O’shea D. Ideals, varieties, and algorithms (Vol. 3). New York: Springer 1992. doi:10.1007/978-1-4757-2181-2.
• [10] Edwards H. A normal form for elliptic curves, In: Bulletin of the American Mathematical Society, 2007; 44:393-422. URL https://doi.org/10.1090/S0273-0979-07-01153-6.
• [11] Farashahi R, and Hosseini S. Differential Addition on Twisted Edwards Curves, In: ACISP 2017: Information Security and Privacy, Lecture Notes in Computer Science, Springer vol. 10343, 2017 pp. 366-378. doi:10.1007/978-3-319-59870-3_21.
• [12] Farashahi RR, and Joye M. Efficient arithmetic on Hessian curves. In International Workshop on Public Key Cryptography, Springer vol. 6056, 2010 pp. 243-260. doi:10.1007/978-3-642-13013-7_15.
• [13] Gsenger G, and Hanser Ch. Improving the Efficiency of Elliptic Curve Scalar Multiplication Using Binary Huff Curves, In: CD-ARES 2013: Security Engineering and Intelligence Informatics, Lecture Notes in Computer Science, Springer vol. 8128, 2013 pp.155-167. doi:10.1007/978-3-642-40588-4_11.
• [14] Hisil H, Wong KKH, Carter G, and Dawson E. Faster group operations on elliptic curves. In: Proceedings of the Seventh Australasian Conference on Information Security-Volume 98. Australian Computer Society, Inc., 2009 pp. 7-20. ISBN:978-1-920682-79-8.
• [15] Joye M, Tibouchi M, and Vergnaud D. Huff’s Model for Elliptic Curves, In: Lecture Notes in Computer Science, Springer vol. 6197, 2010 pp 234-250. doi:10.1007/978-3-642-14518-6_20.
• [16] Justus B, and Loebenberger D. Differential addition in generalized Edwards coordinates. Advances in Information and Computer Security, Science vol. 6434, 2010 pp.316-325. doi:10.1007/978-3-642-16825-3_21.
• [17] Kohel D. Arithmetic of Split Kummer Surfaces: Montgomery Endomorphism of Edwards Products, In: Lecture Notes in Computer Science, Springer vol. 6639, 2011 pp. 238-245. doi:10.1007/978-3-642-20901-7_15.
• [18] Liardet P, and Smart N. Preventing SPA/DPA in ECC systems using the Jacobi form, In: CHES-2001 Conference Proceedings, Lecture Notes in Computer Science, Springer vol. 2162, 2001 pp. 391-401. doi:10.1007/3-540-44709-1_32.
• [19] Montgomery P. Speeding the Pollard and elliptic curve methods of factorization, In: Mathematics of Computation, 1987; 48(177):243-264. doi:10.2307/2007888.
• [20] Okeya K, and Sakurai K. Efficient elliptic curve cryptosystems from a scalar multiplication algorithm with recovery of the y-coordinate on a Montgomery-form elliptic curve. In International Workshop on Cryptographic Hardware and Embedded Systems. Springer vol. 2162, 2001 pp. 126-141. doi:10.1007/3-540-44709-1_12.
• [21] Oliveira T, López J, & Rodríguez-Henríquez F. The Montgomery ladder on binary elliptic curves. Journal of Cryptographic Engineering, 2018; 8(3):241-258. doi:10.1007/s13389-017-0163-8.
• [22] Smart NP. The Hessian Form of an Elliptic Curve, In: Cryptographic Hardware and Embedded Systems-CHES 2001, Lecture Notes in Computer Science, Springer vol. 2162, 2001 pp. 118-125. doi:10.1007/3-540-44709-1_11.

Uwagi

Opracowanie rekordu w ramach umowy 509/P-DUN/2018 ze środków MNiSW przeznaczonych na działalność upowszechniającą naukę (2019).