Source-linked AI summary
Differential Addition on Twisted Edwards Curves
Seyed Gholamhossein Hosseini, Reza Rezaeian Farashahi
TL;DR
Scalar multiplication needs efficient, secure differential addition and doubling, and existing formulas are limited for complete twisted Edwards curves. The paper develops Montgomery-like formulas for these curves, including affine-difference costs of 5M+4S+1D and 3M+7S+1D, with a faster 3M+6S+3D subfamily. These formulas match the costs of prior specialized formulas while applying to a twisted-Edwards family containing complete curves.
Problem
Existing mixed differential addition and doubling formulas at 3M + 6S + 3D are given only for elliptic curves with 3 points of order 2, while complete twisted Edwards curves have different torsion structure.
Method
The paper constructs new Montgomery-like differential addition and doubling formulas for twisted Edwards curves using w-coordinate representations and their relation to Montgomery curves.
Results
The proposed mixed formulas cost 5M+4S+1D and 3M+7S+1D, with 3M+6S+3D formulas for a twisted-Edwards subfamily.
Takeaways & Limitations
The formulas provide Montgomery-like differential addition and doubling for complete twisted Edwards curves, including a point-of-order-4 family.
Takeaways & Limitations
The proposed w functions have different coset invariance properties for complete and incomplete twisted Edwards curves, and full-point recovery remains an open practical question.
Abstract
from arXiv · showhide
This paper presents new differential addition (i.e., the addition of two points with the known difference) and doubling formulas, as the core step in Montgomery scaler multiplication, for twisted Edwards curves. The formulas are provided with cost of 5M+4S+1D, 3M+7S+1D when the given difference point is in affine form. Here, M,S,D denote the costs of a field multiplication, a field squaring and a field multiplication by a constant, respectively.
1 Introduction
Elliptic-curve scalar multiplication relies on repeated addition and doubling, motivating coordinate and curve forms that reduce field-operation costs. The Montgomery ladder combines both operations to resist simple side-channel attacks, and this paper targets faster analogous formulas for complete twisted Edwards curves.
- Motivation: Scalar multiplication computes kP recursively through point addition and doubling over a finite field.Reducing the number of underlying field operations is central to improving point multiplication efficiency.
- Montgomery ladder: Montgomery ladder steps perform addition and doubling together, making the method resistant against simple side-channel attacks.The ladder uses differential formulas expressed through coordinates of the points and their known difference.
- Montgomery ladder: 6M + 4S + 1D is the projective x-coordinate cost for Montgomery differential addition and doubling, reduced to 5M + 4S + 1D for an affine base point.M, S, and D denote field multiplication, squaring, and multiplication by a constant.
- Related work: Existing Montgomery-like formulas extend differential addition and doubling to other elliptic-curve forms through suitable coordinates.Prior work includes formulas for Edwards curves and Kummer lines, with costs depending on the curve family and affine-base assumption.
- Contribution: The paper contributes faster formulas for complete twisted Edwards curves, covering curves with a point of order 4 and a single point of order 2.Reported costs include 5M+4S+1D, 3M+7S+1D, and 3M+6S+3D when the difference point is affine.
- Contribution: Complete twisted Edwards curves have two points of order 4 and one point of order 2, unlike the three-point order-2 setting emphasized in prior mixed formulas.The paper positions this curve family as suitable for cryptographic applications because of its fast complete addition law.
2 Twisted Edwards curve
Twisted Edwards curves extend Edwards curves and support projective addition laws with explicit completeness conditions. Their finite-field structure, torsion points, and birational relationship to Montgomery curves motivate their use in Montgomery-like scalar multiplication.
- Affine structure: The affine twisted Edwards addition law has identity (0, 1), negation (−x, y), and a point of order 2 at (0, −1).When χ(a)=1, the points (±1/√a, 0) have order 4.
- Projective structure: The projective closure introduces singular points at infinity whose rational-point behavior depends on χ(ad) and χ(d).When χ(d)=χ(ad)=−1, the rational projective points are the affine points forming a group.
- Projective addition: Projective twisted Edwards addition formulas use products and sums of the coordinates of two input points.The identity and negation are represented in the P3 projective model.
- Curve family: Twisted Edwards curves extend the Edwards family and include Edwards curves together with their twists.Every Edwards curve in the stated family is a twisted Edwards curve with a=1.
- Completeness: The addition law is complete when χ(ad)=−1 under the stated nonzero-parameter conditions.The paper also gives an exchanged-variable formula covering the case χ(a)=χ(ad)=−1.
- Montgomery relation: Twisted Edwards curves are birationally equivalent to Montgomery curves through parameter-dependent maps.The Montgomery parameters satisfy A = 2(a+d)/(a−d) and B = 4/(a−d).
3 Differential addition
Differential addition computes the sum and double of points from their coordinates and the coordinate of their known difference. Projective Montgomery formulas support ladder multiplication without inversions, but have explicit exceptional inputs and parameter-dependent costs.
- Montgomery formulas: Montgomery ladder steps perform addition and doubling in projective X and Z coordinates, recovering the output Y coordinate afterward.The projective representation avoids the costly field inversion operation.
- Algorithm: The Montgomery x-coordinate algorithm outputs x(P1+P2) and x(2P1) from x(P1−P2), x(P1), and x(P2).Algorithm 1 provides these differential addition and doubling outputs in projective coordinates.
- Scope: The Montgomery ladder works for all inputs except when the base point is the point at infinity or (0, 0).For other points, it computes x(kP) correctly, including when the scalar exceeds the base-point order.
- Definition: Differential addition and doubling compute w(P+Q) and w(2Q) from w(P), w(Q), and w(P−Q).A rational function w satisfying w(P)=w(−P) is represented projectively when it is not regular.
- Cost: 6M+4S+1D is the cost of Montgomery projective x-coordinate differential addition and doubling, reduced to 5M + 4S + 1D for an affine base point.M, S, and D represent multiplication, squaring, and multiplication by a parameter.
- Related work: Prior Edwards and Kummer-line formulas achieve lower costs only for specific curve subfamilies or parameter conditions.The cited Kummer-line formulas target curves with three points of order 2, while some Edwards formulas require d to be a square.
4 Differential addition on twisted Edwards curve
The paper develops differential addition and doubling formulas for twisted Edwards curves using w-coordinates, including complete cases and mixed projective variants. It reports costs from 3M + 6S + 1D to 5M + 4S + 1D, with applicability to Montgomery curves through birational maps.
- The proposed mixed differential addition and doubling formulas cost 5M + 4S + 1D, or 3M + 7S + 1D when multiplication by a parameter is counted.If the parameter e/4 = a/d is small, the latter cost becomes 3M + 7S.
- The formulas are complete under stated quadratic-character conditions, ensuring that the computed projective outputs are not the undefined 0/0 case.For χ(a) = χ(ad) = −1, the formulas yield valid w-coordinates for both doubling and addition.
- The w-coordinate framework supports recovery of 4P from Q − P, w(P), and w(Q), and therefore recovery of 4kP within a Montgomery ladder.The paper states that the ladder can compute 4kP given P, w(kP), and w((k+1)P).
- 3M + 6S + 3D is achieved for twisted Edwards subfamilies satisfying χ(a/d) = 1, with a reduced cost of 3M + 6S + 1D when r is small.The parameter is defined as r^2 = a/d in the corresponding formulas.
- Through birational maps, the twisted Edwards formulas transfer to Montgomery curves, including mixed x-coordinate costs of 3M + 7S + 1D and 3M + 6S + 3D.For suitable Montgomery curves, choosing a small parameter can reduce the cost to 3M + 6S + 1D.
5 Concluding Remarks
The paper presents efficient Montgomery-like differential formulas for twisted Edwards curves, with near-completeness under suitable parameter choices and costs competitive with formulas for other curve families. The proposed w-functions also impose coset invariance, while recovering full point coordinates remains a related practical question.
- Scope and limitations: Known Montgomery-ladder differential addition formulas are incomplete at w(P) = (1 : 0) or (0 : 1), although this does not prevent their stated cryptographic use with large-prime-order base points.The paper suggests the proposed record may extend to elliptic-curve forms with group order divisible by 4, including Jacobi curves.
- Contributions: 3M + 7S + 1D mixed formulas are provided for twisted Edwards curves, with faster 3M + 6S + 3D formulas for a subfamily with small parameters.The paper describes the formulas as improved in efficiency and speed and almost complete when parameters are chosen carefully.
- Scope and limitations: For complete twisted Edwards curves, the proposed w-functions are invariant across the coset of P under the subgroup of Fq-rational points of order 4.The paper identifies computing the full point representation after the Montgomery ladder as a related question for applications requiring full scalar multiplication.