An optimization method for the generalized simplified SWU algorithm
Fengyuan Zhang, Yongbo Yu, Hongfang Yuan · 2024
The use of elliptic curve encoding algorithms is crucial in several areas including password-authenticated key exchanges, identity-based encryption, verifiable random functions, identity-based digital signatures, and BLS short signatures. Among the different forms of elliptic curves, the simplified form of the Weierstrass equation is the most widely used in cryptography. For this form of elliptic curve, the most efficient and widely used elliptic curve encoding algorithm with the most relaxed usage conditions is the generalized simplified SWU algorithm. In this paper, on the basis of reviewing the algorithmic ideas and operation mechanism of the generalized simplified SWU algorithm, we proposed an optimization method starting from the perspective of optimizing the sub-algorithm of the original algorithm, i.e., optimizing the algorithm for calculating the square root over the finite field. Substituting the TonelliShanks algorithm implemented in the original method with the more efficient algorithm proposed in this paper lead to a 43.7% enhancement in the algorithm’s total operational efficiency.