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

Authors

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

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

Section

Articles