Symmetric digit sets for elliptic curve scalar multiplication without precomputation

Area of Science:

• Elliptic curve cryptography
• Number theory
• Abstract algebra

Background:

• Scalar multiplication is a fundamental operation in elliptic curve cryptography.
• Efficient computation of scalar multiplication is crucial for performance and security.
• Existing methods often rely on precomputation, which can be resource-intensive.

Purpose of the Study:

• To develop a novel method for scalar multiplication on specific classes of ordinary elliptic curves.
• To leverage efficient endomorphisms (4th and 6th roots of unity) for computational speed-up.
• To design a precomputationless algorithm for scalar multiplication.

Main Methods:

• Utilizing width-w-NAF (Non-Adjacent Form) digit expansion in a complex base defined by the Frobenius endomorphism's characteristic polynomial.
• Factoring the unit group within the endomorphism ring modulo τ.
• Constructing a digit set using powers of efficient subgroup generators (endomorphisms).

Main Results:

• A precomputationless algorithm for scalar multiplication on ordinary elliptic curves [Formula: see text] and [Formula: see text].
• Demonstration of how 4th and 6th roots of unity function as efficient endomorphisms.
• The proposed method optimizes scalar multiplication by avoiding precomputation steps.

Conclusions:

• The developed method offers a significant improvement in scalar multiplication efficiency for targeted elliptic curves.
• The use of endomorphisms and optimized digit expansion provides a viable alternative to traditional precomputation-based algorithms.
• This research contributes to the advancement of efficient and secure elliptic curve cryptography.