TL;DR
This paper introduces a novel algorithm for computing $2P+Q$ on elliptic curves that saves a field multiplication compared to standard methods. This optimization, when applied to scalar multiplication and pairing computations, leads to significant performance improvements, estimated between 3.8% and 8.5% for scalar multiplication and up to 7.8% for Weil and Tate pairings.
What Problem Does This Paper Address?
Elliptic curve cryptography relies heavily on efficient arithmetic operations, particularly scalar multiplication ($kP$) and more recently, pairings (like Weil and Tate pairings). These operations are computationally intensive, and even small percentage improvements can have a substantial impact on the overall performance and practicality of cryptographic systems. Standard methods for computing $2P+Q$ (a common sub-operation in scalar multiplication) involve a certain number of field multiplications, squarings, and divisions. The paper identifies an opportunity to reduce the number of field multiplications required for the specific computation of $2P+Q$ when the intermediate results of $2P$ and $P+Q$ are not needed. This is particularly relevant for algorithms like left-to-right binary scalar multiplication and simultaneous multiple scalar multiplication.
Methods
The core innovation lies in a clever algebraic manipulation to compute $2P+Q$ more efficiently. Instead of computing $P+Q$ and then doubling $P$ to get $2P$, and finally adding $2P$ and $Q$, the authors propose a method that computes $P+Q$ but omits the calculation of its y-coordinate. This saved y-coordinate calculation is then used in a subsequent step to compute $(P+Q)+P$. This effectively bypasses one field multiplication that would otherwise be needed to compute the y-coordinate of $P+Q$.
The paper details this "double-add trick" and shows how it can be applied to:
- Scalar Multiplication: By integrating this optimized $2P+Q$ computation into standard scalar multiplication algorithms (like left-to-right binary methods with windowing), the overall cost is reduced.
- Simultaneous Multiple Scalar Multiplication: Algorithms that compute linear combinations of points ($k_1P_1 + k_2P_2 + \dots$) can also benefit.
- Elliptic Curve Method (ECM) of Factorization: This number-theoretic algorithm uses scalar multiplication, so improvements here translate to faster factorization attempts.
- Weil and Tate Pairings: The paper adapts the technique to the computation of rational functions used in pairing algorithms, specifically by optimizing the calculation of intermediate values and using a parabolic equation to represent certain line evaluations.
Datasets
Not discussed in the paper. The paper focuses on theoretical algorithmic improvements and their estimated performance gains, rather than empirical evaluation on specific datasets.
Key Insights and Ideas
- The "Omitted y-coordinate" Trick: The fundamental insight is that for computing $2P+Q$ when only the final result is needed, the y-coordinate of the intermediate $P+Q$ can be omitted, saving a field multiplication. This is a non-obvious optimization that exploits the structure of elliptic curve addition formulas.
- Generalizability: The technique is not limited to a specific type of elliptic curve or field characteristic, with the paper providing pseudocode for the general Weierstrass form.
- Impact on Pairings: The application to Weil and Tate pairings is particularly significant, as these are becoming increasingly important in modern cryptography. The paper shows how this optimization can be integrated into existing pairing algorithms like Miller's algorithm.
- Trade-offs in Field Operations: The paper explicitly analyzes the savings in terms of multiplications, squarings, and divisions, and discusses how the relative cost of field inversion (which is often more expensive) affects the overall percentage savings.
Key Results
- Scalar Multiplication Speedup: Estimated savings of 3.8% to 8.5% over best-known general methods for scalar multiplication on general elliptic curves.
- Pairing Speedup: Estimated savings of up to 7.8% for Weil and Tate pairings.
- ECM Factorization: The method offers improvements in the cost of scalar multiplication within the ECM algorithm.
- Reduced Field Operations: The core $2P+Q$ operation is shown to require one fewer field multiplication. For example, a "double-add" operation (which is $2P+Q$) costs 2 squarings, 1 multiplication, and 2 divisions, saving one multiplication compared to a naive approach.
Limitations and Future Work
- Precomputation Costs: The paper acknowledges that the savings are primarily in the "online" phase of computation and do not account for precomputation costs, which can be significant in some cryptographic schemes.
- Specific Curve Forms: While the general form is discussed, the most significant savings are often realized on specific curve forms (like $E_{simple}: y^2 = x^3 + ax + b$) where the formulas are simpler.
- Hardware Implementations: The paper provides theoretical estimates and some hardware timings, but further optimization for specific hardware architectures might be possible.
- Future Work: The authors suggest exploring further applications of their technique to other cryptographic primitives and investigating its impact on different elliptic curve forms and field characteristics. The pseudocode provided in Appendix A serves as a basis for implementation and further research.
Summary updated