Arithmetic Using Compression on Elliptic Curves in Huff’s Form and Its Applications

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

Identyfikatory

DOI

10.24425/ijet.2021.135964

• Języki publikacji: EN

Abstrakty

EN

In this paper for elliptic curves provided by Huff’s equation H a,b : ax(y² − 1) = by(x² − 1) and general Huff’s equation G a,b : x(ay² − 1) = y(bx² − 1) and degree 2 compression function f(x, y) = xy on these curves, herein we provide formulas for doubling and differential addition after compression, which for Huff’s curves are as efficient as Montgomery’s formulas for Montgomery’s curves By² = x³ + Ax² + x. For these curves we also provided point recovery formulas after compression, which for a point P on these curves allows to compute [n]f(P) after compression using the Montgomery ladder algorithm, and then recover [n]P. Using formulas of Moody and Shumow for computing odd degree isogenies on general Huff’s curves, we have also provide formulas for computing odd degree isogenies after compression for these curves. Moreover, it is shown herein how to apply obtained formulas using compression to the ECM algorithm.

Słowa kluczowe

EN

Huff's curves; isogeny-based cryptography; compression functions on elliptic curves

• Wydawca: Polish Academy of Sciences, Committee of Electronics and Telecommunication
• Czasopismo: International Journal of Electronics and Telecommunications
• Rocznik: 2021
• Tom: Vol. 67, No. 2
• Strony: 193--200
• Opis fizyczny: Bibliogr. 18 poz., 1 tabl.

Twórcy

autor

Dryło Robert

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

autor

Kijko Tomasz

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

autor

Wroński Michał

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

Bibliografia

• [1] D. J. Bernstein and T. Lange, “Montgomery curves and the montgomery ladder.” IACR Cryptol. ePrint Arch., vol. 2017, p. 293, 2017.
• [2] C. Costello and B. Smith, “Montgomery curves and their arithmetic,” Journal of Cryptographic Engineering, vol. 8, no. 3, pp. 227–240, 2018.
• [3] P. L. Montgomery, “Speeding the pollard and elliptic curve methods of factorization,” Mathematics of Computation, vol. 48, pp. 243–264, 1987.
• [4] E. Brier and M. Joye, “Weierstraß elliptic curves and side-channel attacks,” in International workshop on public key cryptography. Springer, 2002, pp. 335–345.
• [5] R. R. Farashahi and S. G. Hosseini, “Differential addition on twisted edwards curves,” in Australasian Conference on Information Security and Privacy. Springer, 2017, pp. 366–378.
• [6] B. Justus and D. Loebenberger, “Differential addition in generalized edwards coordinates,” in International Workshop on Security. Springer, 2010, pp. 316–325.
• [7] R. R. Farashahi and M. Joye, “Efficient arithmetic on hessian curves,” in International Workshop on Public Key Cryptography. Springer, 2010, pp. 243–260.
• [8] W. Castryck and F. Vercauteren, “Toric forms of elliptic curves and their arithmetic,” Journal of Symbolic Computation, vol. 46, no. 8, pp. 943–966, 2011.
• [9] R. Dryło, T. Kijko, and M. Wronski, “Determining formulas related to point compression on alternative models of elliptic curves,” Fundamenta Informaticae, vol. 169, no. 4, pp. 285–294, 2019.
• [10] K. Okeya and K. Sakurai, “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, 2001, pp. 126–141.
• [11] M. Joye, M. Tibouchi, and D. Vergnaud, “Huff’s model for elliptic curves,” in International Algorithmic Number Theory Symposium. Springer, 2010, pp. 234–250.
• [12] H. Wu and R. Feng, “Elliptic curves in huff’s model,” Wuhan University Journal of Natural Sciences, vol. 17, no. 6, pp. 473–480, 2012.
• [13] T. Oliveira, J. López, H. Hişil, A. Faz-Hernández, and F. Rodríguez-Henríquez, “How to (pre-) compute a ladder,” in International Conference on Selected Areas in Cryptography. Springer, 2017, pp. 172–191.
• [14] R. R. Farashahi and S. G. Hosseini, “Differential addition on binary elliptic curves,” in International Workshop on the Arithmetic of Finite Fields. Springer, 2016, pp. 21–35.
• [15] D. Moody and D. Shumow, “Analogues of vélu’s formulas for isogenies on alternate models of elliptic curves,” Mathematics of Computation, vol. 85, no. 300, pp. 1929–1951, 2016.
• [16] C. Costello and H. Hisil, “A simple and compact algorithm for sidh with arbitrary degree isogenies,” in International Conference on the Theory and Application of Cryptology and Information Security. Springer, 2017, pp. 303–329.
• [17] D. Jao, R. Azarderakhsh, M. Campagna, C. Costello, L. Feo, B. Hess, A. Jalali, B. Koziel, B. LaMacchia, P. Longa, M. Naehrig, G. Pereira, J. Renes, V. Soukharev, and D. Urbanik, “Supersingular isogeny key encapsulation,” 04 2019.
• [18] D. Jeon, C. H. Kim, and Y. Lee, “Families of elliptic curves over quartic number fields with prescribed torsion subgroups,” Mathematics of computation, vol. 80, no. 276, pp. 2395–2410, 2011.

Uwagi

Opracowanie rekordu ze środków MNiSW, umowa Nr 461252 w ramach programu "Społeczna odpowiedzialność nauki" - moduł: Popularyzacja nauki i promocja sportu (2021).