Simple verification of completeness of two addition formulas on twisted Edwards curves

Authors

  • Robert Dryło Institute of Mathematics and Cryptology, Military University of Technology, Kaliskiego 2, 00-908 Warsaw, Poland
  • Tomasz Kijko Institute of Mathematics and Cryptology, Military University of Technology, Kaliskiego 2, 00-908 Warsaw, Poland

Abstract

Daniel Bernstein and Tanja Lange  proved that
two given addition formulas on twisted Edwards elliptic curves
ax^2 + y^2 = 1 + dxy are complete (i.e. the sum of any two points
on a curve can be computed using one of these formulas). In
this paper we give other simple verification of completeness
of these formulas using for example Groebner bases and an ¨
algorithm implemented in Magma, which is based on the fact that
completeness means that some systems of polynomial equations
have no solutions. This method may be also applied to verify
completeness  of additions formulas on other models of elliptic
curves.

Downloads

Published

2024-04-19

Issue

Section

Cryptography and Cybersecurity