High-degree compression functions on alternative models of elliptic curves and their applications

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

Identyfikatory

DOI

10.3233/FI-2021-2094

• Języki publikacji: EN

Abstrakty

EN

This paper presents method for obtaining high-degree compression functions using natural symmetries in a given model of an elliptic curve. Such symmetries may be found using symmetry of involution [–1] and symmetry of translation morphism τ T = P + T , where T is the n -torsion point which naturally belongs to the E (𝕂) for a given elliptic curve model. We will study alternative models of elliptic curves with points of order 2 and 4, and specifically Huff’s curves and the Hessian family of elliptic curves (like Hessian, twisted Hessian and generalized Hessian curves) with a point of order 3. We bring up some known compression functions on those models and present new ones as well. For (almost) every presented compression function, differential addition and point doubling formulas are shown. As in the case of high-degree compression functions manual investigation of differential addition and doubling formulas is very difficult, we came up with a Magma program which relies on the Gröbner basis. We prove that if for a model E of an elliptic curve exists an isomorphism φ : E → E M , where E M is the Montgomery curve and for any P ∈ E (𝕂) holds that φ (P ) = (φ x (P ), φ y (P )), then for a model E one may find compression function of degree 2. Moreover, one may find, defined for this compression function, differential addition and doubling formulas of the same efficiency as Montgomery’s. However, it seems that for the family of elliptic curves having a natural point of order 3, compression functions of the same efficiency do not exist.

Słowa kluczowe

EN

alternative models of elliptic curves; compression on elliptic curves

• Wydawca: IOS Press
• Czasopismo: Fundamenta Informaticae
• Rocznik: 2021
• Tom: Vol. 184, nr 2
• Strony: 107--139
• Opis fizyczny: Bibliogr. 25 poz.

Twórcy

autor

Wroński Michał

• Faculty of Cybernetics Military University of Technology in Warsaw

autor

Kijko Tomasz

• Faculty of Cybernetics Military University of Technology in Warsaw

autor

Dryło Robert

• Faculty of Cybernetics Military University of Technology in Warsaw

Bibliografia

• [1] Jao D, De Feo L. Towards Quantum-Resistant Cryptosystems from Supersingular Elliptic Curve Isogenies. In: Yang BY (ed.), Post-Quantum Cryptography. Springer Berlin Heidelberg, Berlin, Heidelberg. ISBN 978-3-642-25405-5, 2011 pp. 19-34.
• [2] Azarderakhsh R, Campagna M, Costello C, Feo L, Hess B, Jalali A, Jao D, Koziel B, LaMacchia B, Longa P, et al. Supersingular isogeny key encapsulation. Submission to the NIST Post-Quantum Standardization project, 2020.
• [3] Castryck W, Lange T, Martindale C, Panny L, Renes J. CSIDH: an efficient post-quantum commutative group action. In: International Conference on the Theory and Application of Cryptology and Information Security. Springer, 2018 pp. 395-427. doi:10.1007 / 978-3-030-03332-3 15.
• [4] Montgomery PL. Speeding the Pollard and elliptic curve methods of factorization. Mathematics of computation, 1987. 48(177):243-264. doi:10.1090/S0025-5718-1987-0866113-7.
• [5] Edwards H. A normal form for elliptic curves. Bulletin of the American mathematical society, 2007. 44(3):393-422. doi:10.1090/S0273-0979-07-01153-6.
• [6] Bernstein DJ, Lange T. Inverted Edwards Coordinates. In: Boztas¸ S, Lu HFF (eds.), Applied Algebra, Algebraic Algorithms and Error-Correcting Codes. Springer Berlin Heidelberg, Berlin, Heidelberg. 2007 pp. 20-27. ISBN: 978-3-540-77224-8.
• [7] Bernstein DJ, Birkner P, Joye M, Lange T, Peters C. Twisted Edwards curves. In: International Conference on Cryptology in Africa. Springer, 2008 pp. 389-405. doi:c798703ae3ecfdc375112f19dd0787e4.
• [8] Joye M, Quisquater JJ. Hessian Elliptic Curves and Side-Channel Attacks. In: Koc¸ C¸ K, Naccache D, Paar C (eds.), Cryptographic Hardware and Embedded Systems — CHES 2001. Springer Berlin Heidelberg, Berlin, Heidelberg. 2001 pp. 402-410. ISBN:978-3-540-44709-2.
• [9] Bernstein DJ, Chuengsatiansup C, Kohel D, Lange T. Twisted hessian curves. In: International Conference on Cryptology and Information Security in Latin America. Springer, 2015 pp. 269-294. doi:10.1007/978-3-319-22174-8 15.
• [10] Farashahi RR, Joye M. Efficient arithmetic on Hessian curves. In: International Workshop on Public Key Cryptography. Springer, 2010 pp. 243-260. doi:10.1007/978-3-642-13013-7_15.
• [11] Joye M, Tibouchi M, Vergnaud D. Huff’s model for elliptic curves. In: International Algorithmic Number Theory Symposium. Springer, 2010 pp. 234-250. doi:10.1007/978-3-642-14518-6_20.
• [12] Lenstra AK, Verheul ER. The XTR public key system. In: Annual International Cryptology Conference. Springer, 2000 pp. 1-19. doi:10.1007/3-540-44598-6_1.
• [13] De Feo L, Jao D, Plˆut J. Towards quantum-resistant cryptosystems from super singular elliptic curve isogenies. Journal of Mathematical Cryptology, 2014. 8(3):209-247. doi:10.1515/jmc-2012-0015.
• [14] Jao D, Azarderakhsh R, Campagna M, Costello C. Super singular Isogeny Key Encapsulation (version from April 17, 2019. NIST PQC, 2019. https://sike.org/files/SIDH-spec.pdf.
• [15] Bernstein D, De Feo L, Leroux A, Smith B. Faster computation of isogenies of large prime degree. arXiv preprint arXiv:2003.10118, 2020.
• [16] Kohel D. Addition law structure of elliptic curves. Journal of Number Theory, 2011. 131(5):894-919. doi:10.1016/j.jnt.2010.12.001.
• [17] Kohel D. Efficient arithmetic on elliptic curves in characteristic 2. In: International Conference on Cryptology in India. Springer, 2012 pp. 378-398. ISBN:978-3-642-34930-0, doi:10.1007/978-3-642-34931-7 22.
• [18] Farashahi RR, Hosseini SG. Differential Addition on Twisted Edwards Curves. In: Pieprzyk J, Suriadi S (eds.), Information Security and Privacy. Springer International Publishing, Cham. 2017 pp. 366-378. ISBN:978-3-319-59870-3.
• [19] Dryło R, Kijko T, Wroński M. Determining Formulas Related to Point Compression on Alternative Models of Elliptic Curves. Fundamenta Informaticae, 2019. 169(4):285-294. doi:10.3233/FI-2019-1848.
• [20] Adams WW, Loustaunau P. An introduction to Grobner bases. 3. American Mathematical Soc., 1994. ISBN:978-1-4704-6981-8.
• [21] Cox D, Little J, O’Shea D, Sweedler M. Ideals, varieties, and algorithms. American Mathematical Monthly, 1994. 101(6):582-586.
• [22] Haihua Gu, Dawu Gu, WenLu Xie. Differential addition on Jacobi quartic curves. In: Symposium on ICT and Energy Efficiency and Workshop on Information Theory and Security (CIICT 2012). 2012 pp. 194-197. doi:10.1049/cp.2012.1890.
• [23] Faugère JC, Huot L, Joux A, Renault G, Vitse V. Symmetrized Summation Polynomials: Using Small Order Torsion Points to Speed Up Elliptic Curve Index Calculus. In: Nguyen PQ, Oswald E (eds.), Advances in Cryptology – EUROCRYPT 2014. Springer Berlin Heidelberg, Berlin, Heidelberg. 2014 pp. 40-57. ISBN:978-3-642-55220-5.
• [24] Castryck W, Galbraith SD, Farashahi RR. Efficient arithmetic on elliptic curves using a mixed Edwards-Montgomery representation. IACR Cryptology ePrint Archive, 2008. 2008:218. http://eprint.iacr.org/2008/218.
• [25] Dryło R, Kijko T, Wroński M. Efficient Montgomery-like formulas for general Huff’s and Huff’s elliptic curves and their applications to the isogeny-based cryptography. Cryptology ePrint Archive, Report 2020/526, 2020. https://eprint.iacr.org/2020/526.

Uwagi

Opracowanie rekordu ze środków MEiN, umowa nr SONP/SP/546092/2022 w ramach programu "Społeczna odpowiedzialność nauki" - moduł: Popularyzacja nauki i promocja sportu (2022-2023). (PL)