Evaluation of the efficiency of differential addition of points of curves in the generalized Edwards form

Authors

  • A.V. Bessalov Киевский Университет имени Бориса Гринченко, Ukraine https://orcid.org/0000-0002-6967-5001
  • L.V. Kovalchuk Национальный технический университет Украины "Киевский политехнический институт имени Игоря Сикорского", Ukraine https://orcid.org/0000-0003-2874-7950
  • N.V. Kuchynska Национальный технический университет Украины "Киевский политехнический институт имени Игоря Сикорского", Ukraine https://orcid.org/0000-0002-6457-7525

DOI:

https://doi.org/10.30837/rt.2020.4.203.05

Keywords:

Edwards curve in generalized form, complete Edwards curve, twisted Edwards curve, quadratic Edwards curve, curves order, points order, isomorphism, differential addition, computing cost, square, non square

Abstract

A survey of the main properties of three classes of curves in the generalized Edwards form is given: complete, quadratic and twisted Edwards curves. The analysis of the Montgomery algorithm for differential addition of points for the Montgomery curve is carried out. An estimation of the record low cost of computing the scalar product kP of a point P is given, which is equal to 5M+4S+1U on one step of the iterative cycle (M is the cost of finite field multiplication, S is the cost of squaring, U is the cost of field multiplication by a known constant). A detailed derivation of the formulas for addition-subtraction and doubling points for the curve in the generalized Edwards form in projective coordinates of Farashahi-Hosseini is carried out. Moving from three-dimensional projective coordinates (X: Y: Z) to two-dimensional coordinates (W: Z) allows achieving the same minimum computational cost for the Edwards curves as for the Montgomery curve. Aspects of the choice of an Edwards-form curve acceptable for cryptography and its parameters optimization in the problem of differential addition of points are discussed. Twisted Edwards curves with the order of NE=4n (n is prime) at p≡5mod8 are recommended, minimizing the parameters a and d allows achieving the minimum cost estimation 5M+4S for one step of computing the point product. It is shown that the transition from the Weierstrass curves (the form used in modern cryptographic standards) to the Edwards curves makes it possible to obtain a potential gain in the speed of computing the scalar product of the point by a factor of 3.09.

References

Menezes A., van Oorshot P.C., Vanstone S.A. Handbook of Applied Cryptography. CRC press, New York, 2006.

Washington L.C. Elliptic Curvres. Number Theory and Cryptography. Second Edition. CRC Press, 2008.

Montgomery, P.L. Speeding the Pollard and elliptic curve methods of factorization // Math. Comp. 48(177). Р. 243–264 (1987).

Farashahi R.R., Hosseini S.G. Differential addition on twisted Edwards curves // Pieprzyk J., Suriadi S. (eds.) Information Security and Privacy. pp. 366-378. Springer International Publishing, Cham (2017).

Bernstein D.J., Lange T. Faster Addition and Doubling on Elliptic Curves // Advances in Cryptology – ASIACRYPT’2007 (Proc. 13th Int. Conf. on the Theory and Application of Cryptology and Information Security. Kuching, Malaysia. December 2–6, 2007). Lect. Notes Comp. Sci. V. 4833. Berlin: Springer, 2007. P. 29–50.

Bernstein Daniel J., Birkner Peter, Joye Marc, Lange Tanja, Peters Christiane. Twisted Edwards Curves // IST Programme under Contract IST–2002–507932 ECRYPT,and in part by the National Science Foundation under grant ITR–0716498, 2008. Р. 1-17.

Бессалов А.В. Эллиптические кривые в форме Эдвардса и криптография : монография. Киев : Политехника, 2017. 272с.

Бессалов А.В., Дихтенко А.A., Третьяков Д.Б. Сравнительная оценка быстродействия канонических эллиптических кривых и кривых в форме Эдвардса над конечным полем // Сучасний захист інформації. 2011. №4. С.33-36.

Бессалов А.В., Цыганкова О.В. Производительность групповых операций на скрученной кривой Эдвардса над простым полем // Радиотехника. 2015. №181. С.58-63.

Suhri Kim, Kisoon Yoon, Young-Ho Park, and Seokhie Hong. Optimized Method for Computing Odd-Degree Isogenies on Edwards Curves. Center for Information Security Technologies (CIST), Korea University, Seoul,Republic of Korea, 2018.

Downloads

Published

2020-12-23

How to Cite

Bessalov, A., Kovalchuk, L., & Kuchynska, N. (2020). Evaluation of the efficiency of differential addition of points of curves in the generalized Edwards form. Radiotekhnika, 4(203), 50–59. https://doi.org/10.30837/rt.2020.4.203.05

Issue

No. 203 (2020): Radiotekhnika

Section

Articles

License

Authors who publish with this journal agree to the following terms:

1. Authors retain copyright and grant the journal right of first publication with the work simultaneously licensed under a Creative Commons Attribution License that allows others to share the work with an acknowledgement of the work's authorship and initial publication in this journal.

2. Authors are able to enter into separate, additional contractual arrangements for the non-exclusive distribution of the journal's published version of the work (e.g., post it to an institutional repository or publish it in a book), with an acknowledgement of its initial publication in this journal.

3. Authors are permitted and encouraged to post their work online (e.g., in institutional repositories or on their website) prior to and during the submission process, as it can lead to productive exchanges, as well as earlier and greater citation of published work (See The Effect of Open Access).