# Memory-Efficient Algorithm for Scalar Multiplications on Twisted Edwards Curves for Isogeny-Based Cryptosystems

Authors: Sookyung Eom; Hyang-Sook Lee; Kyunghwan Song
Journal: Mathematical Problems in Engineering
 (2022)

---

## Abstract

Scalar multiplications are considered an essential aspect of implementations of isogeny-based cryptography. The efficiency of scalar multiplication depends on the equation of the underlying elliptic curves and the addition chain employed. Bos and Friedberger recently stated that, for larger scalar multiplication, addition-subtraction chains will become more useful for twisted Edwards curves because of the differential restriction on Montgomery curves in the setting of isogeny-based cryptosystem. Motivated by these comments, we attempt to increase the efficiency of scalar multiplication in twisted Edwards curves in terms of the memory of algorithms. In this paper, we present a double-base addition-subtraction chain algorithm with memory efficiency for scalar multiplication. The memory usage of this part isOlogn2/loglogn, which is better than the result of the tree-based approach, which is Ologn2.


---

## Body

## 1. Introduction

### 1.1. Isogeny-Based Cryptosystem

The isogeny cryptosystem is currently considered one of the promising candidates for maintaining security in quantum computing environments. Couveignes [1] first introduced the concept of isogeny-based cryptosystems in 2006, and Charles et al. [2] first developed an isogeny cryptosystem based on supersingular elliptic curves in 2009. However, the ordinary elliptic curve was found to be vulnerable in an isogeny-based system by a subexponential quantum algorithm developed by Childs et al. [3]. Therefore, an isogeny-based cryptosystem is currently being studied at the supersingular curve rather than at the ordinary elliptic curves. One of the important works on the isogeny-based cryptosystem is the supersingular isogeny Diffie–Hellman (SIDH) key exchange that was introduced by Jao and Feo [4] in 2011. There have been a lot of related studies [5–8] examining this scheme. One example is the supersingular isogeny key encapsulation (SIKE) [9] submitted to the NIST (National Institute of Standards and Technology) competition on the standardisation of post-quantum cryptosystems. Practical hardware implementations [10–14] of SIKE have also been developed, and more are expected to be available in the future.To achieve more efficient isogeny-based cryptosystems, it is necessary to investigate methods that improve the isogeny calculations or the scalar multiplications. In particular, fast exponentiation and inversion are critical in the process of the scalar multiplication of points over elliptic curve. Koziel et al. [15] improved upon the efficiency of isogeny-based cryptosystems by avoiding the computation of finite field inversions in the scalar multiplication of points. They also worked on the shape of smooth isogeny primes and presented new windowing methods to calculate fast addition chains. Recently, Bos and Friedberger [16] sped up the scalar multiplications on twisted Edward curves by using an efficient addition-subtraction chain algorithm.


### 1.2. Our Contribution

Motivated by the previous research stated in Section1.1, our work proposes a new double-base addition-subtraction chain algorithm and demonstrates scalar multiplication using the proposed chain for a twisted Edwards curve with projective coordinates. In particular, we focus on the memory efficiency aspect. Our algorithm leads to a memory-efficient system because it only needs Ologn2/loglogn, which is better than the result of the tree-based approach, which is Ologn2 [17]. Therefore, in terms of memory efficiency, the approach based on a modified greedy algorithm is shown to be a good choice for scalar multiplication. These results represent an improvement upon the scalar multiplication of isogeny-based cryptosystems in the field of post-quantum cryptography. The experimental results also show that the length of the chain is much shorter, and as a result, for scalar multiplication in a isogeny-based cryptosystem, the complexity is reduced by 20% compared to the single-base number system.


### 1.3. Organization

The paper is organized as follows. In Section2, we give preliminaries on isogenies and addition-subtraction chains on double-base number systems for elliptic curve isogeny-based cryptosystems. Section 3 introduces twisted Edwards curves and their various coordinates. In Section 4, we present our new algorithms and compare the memory usage with previous work [18] and suggest the experimental result for the computational complexity. Section 5 concludes our work.


## 1.1. Isogeny-Based Cryptosystem

The isogeny cryptosystem is currently considered one of the promising candidates for maintaining security in quantum computing environments. Couveignes [1] first introduced the concept of isogeny-based cryptosystems in 2006, and Charles et al. [2] first developed an isogeny cryptosystem based on supersingular elliptic curves in 2009. However, the ordinary elliptic curve was found to be vulnerable in an isogeny-based system by a subexponential quantum algorithm developed by Childs et al. [3]. Therefore, an isogeny-based cryptosystem is currently being studied at the supersingular curve rather than at the ordinary elliptic curves. One of the important works on the isogeny-based cryptosystem is the supersingular isogeny Diffie–Hellman (SIDH) key exchange that was introduced by Jao and Feo [4] in 2011. There have been a lot of related studies [5–8] examining this scheme. One example is the supersingular isogeny key encapsulation (SIKE) [9] submitted to the NIST (National Institute of Standards and Technology) competition on the standardisation of post-quantum cryptosystems. Practical hardware implementations [10–14] of SIKE have also been developed, and more are expected to be available in the future.To achieve more efficient isogeny-based cryptosystems, it is necessary to investigate methods that improve the isogeny calculations or the scalar multiplications. In particular, fast exponentiation and inversion are critical in the process of the scalar multiplication of points over elliptic curve. Koziel et al. [15] improved upon the efficiency of isogeny-based cryptosystems by avoiding the computation of finite field inversions in the scalar multiplication of points. They also worked on the shape of smooth isogeny primes and presented new windowing methods to calculate fast addition chains. Recently, Bos and Friedberger [16] sped up the scalar multiplications on twisted Edward curves by using an efficient addition-subtraction chain algorithm.


## 1.2. Our Contribution

Motivated by the previous research stated in Section1.1, our work proposes a new double-base addition-subtraction chain algorithm and demonstrates scalar multiplication using the proposed chain for a twisted Edwards curve with projective coordinates. In particular, we focus on the memory efficiency aspect. Our algorithm leads to a memory-efficient system because it only needs Ologn2/loglogn, which is better than the result of the tree-based approach, which is Ologn2 [17]. Therefore, in terms of memory efficiency, the approach based on a modified greedy algorithm is shown to be a good choice for scalar multiplication. These results represent an improvement upon the scalar multiplication of isogeny-based cryptosystems in the field of post-quantum cryptography. The experimental results also show that the length of the chain is much shorter, and as a result, for scalar multiplication in a isogeny-based cryptosystem, the complexity is reduced by 20% compared to the single-base number system.


## 1.3. Organization

The paper is organized as follows. In Section2, we give preliminaries on isogenies and addition-subtraction chains on double-base number systems for elliptic curve isogeny-based cryptosystems. Section 3 introduces twisted Edwards curves and their various coordinates. In Section 4, we present our new algorithms and compare the memory usage with previous work [18] and suggest the experimental result for the computational complexity. Section 5 concludes our work.


## 2. Preliminaries

In this section, we review briefly some concepts and properties of isogenies and addition-subtraction chains for elliptic curve isogeny-based cryptosystems.


### 2.1. Isogeny

LetE1 and E2 be two elliptic curves over a finite field Fq. An isogeny ϕ:E1Fq¯⟶E2Fq¯ is a nonconstant group homomorphism (E1 and E2) that is given by rational functions. This means that ϕP+Q=ϕP+ϕQ for all P,Q∈E1Fq¯ and there exist rational functions r1,r2 such that if ϕx1,y1=x2,y2, then(1)x2=r1x1,y1,y2=r2x1,y1,for all but finitely many x1,y1∈E1Fq¯ [19].If the degree ofϕ as a group homomorphism is ℓ, the isogeny is called an ℓ-isogeny. If the degree of ϕ is equal to the cardinality of kernel of ϕ, ϕ is called separable. If there exists a separable isogeny between two curves, we say that they are isogenous. For an isogeny ϕ between two curves E1,E2 with E1=E2, we say ϕ is an endomorphism. The set of endomorphisms of an elliptic curve, denoted by end E, has a ring structure with the operations of point-wise addition and function composition.


### 2.2. Isogeny-Based Cryptosystems

Definition 1.
A prime of the formp=ℓAeAℓBeBf±1 is called a smooth isogeny prime, where ℓA and ℓB and small primes, eA and eB, are positive integers, and f is a small cofactor to make p prime.
Isogeny-based cryptosystems use smooth isogeny primes, and the case whereℓA=2 and ℓB=3 is preferred since this case enjoys the fastest known isogeny computations [8]. Let E be an elliptic curve and let m∈ℕ.Definition 2.
LetE be an elliptic curve and let m∈ℕ. Then, Em is called m-torsion subgroup of E, which is the set of points of order m:(2)Em=P∈E|mP=O.
An elliptic curveE over a field of characteristic p has a torsion subgroup Epr for which holds that either Epr=O or Epr=ℤ/prℤ for all r≥1, the first case is called that E is supersingular and the other case is called E is ordinary. There are some hard problem candidate hard problem related to supersingular elliptic curves as follows [20].Problem 1.
Letp,ℓ be distinct prime numbers. Let E1 and E2 be two elliptic curves over Fp2 with #E1Fp2=#E2Fp2=p+12, chosen uniformly at random. Find k∈ℕ and an isogeny of degree ℓk from E1 to E2.
We remark that the ordinary Problem1 stated for the general curve is not known to be equivalent, and that there also exists a subexponential algorithm that computes the endomorphism ring of ordinary curves [21]. Although the best algorithm that computes isogenies is still exponential, there is a subexponential quantum algorithm that computes an isogeny between two ordinary curves [3]; therefore, studies on isogeny-based cryptography are focused on supersingular cases.


### 2.3. Chains for Scalar Multiplication

There are several candidates to reduce the cost of scalar multiplications on elliptic curve cryptosystems. In isogeny-based cryptosystems, the results of the scalar multiplication of elliptic curves are addition chains [15], addition-subtraction chains [16], etc. In this section, we introduce an addition-subtraction chain using double base.Definition 3.
Given two primesp,q∈ℕ, a double-base number system (DBNS) is a representation into which every positive integer n is represented as the linear combination with coefficients in 1,−1 and sum of difference of p,q-integers, i.e., numbers of the form paqb:(3)n=∑i=0ℓdipaiqbi,with di∈−1,1 and a0≥a1≥a2≥…≥aℓ≥0 and b0≥b1≥b2≥…≥bℓ≥0.
The representation of an integern is not unique in both unsigned case and signed case. The most representative algorithm for expressing arbitrary n by DBNS is the greedy algorithm. The greedy algorithm is as follows.Theorem 1 (see [22]).
Algorithm 1 terminates afterk∈Ologn/loglogn steps.Algorithm 1: The greedy algorithm for double-base number system [23].
Input:a0, S=1,−1, NOutput: three sequencesdi,ai,bi0≤i≤ℓ such that N=∑i=0ℓdi2ai3bi with di∈S, a0≥⋯≥aℓ, b0≥⋯≥bℓ(1)
ifa0>log3Nthen(2)
return fail(3)
end if(4)
b0←⌈log2N−a0log23⌉(5)
i,t,s←1,N,1(6)
whilet>0do(7)
find the best approximationz=di2ai3bi of t with di∈S, 0≤ai≤ai−1, and 0≤bi≤bi−1(8)
di←s×di(9)
ift<zthen(10)
s←−s(11)
end if(12)
t←|t−z|(13)
i←i+1(14)
end while(15)
returndi,ai,bii≤i≤ℓIn Algorithm 1, lines 1–3 give the limitation for the input parametera0 and line 4 gives the value of the parameter b0. The parameter a0 is used when the exponentiation a1 of 2 is the biggest term in the expansion, that is, 0≤aℓ≤aℓ−1≤⋯≤a1≤a0. The value of b0 also gives limit of bi ’s similarly.


## 2.1. Isogeny

LetE1 and E2 be two elliptic curves over a finite field Fq. An isogeny ϕ:E1Fq¯⟶E2Fq¯ is a nonconstant group homomorphism (E1 and E2) that is given by rational functions. This means that ϕP+Q=ϕP+ϕQ for all P,Q∈E1Fq¯ and there exist rational functions r1,r2 such that if ϕx1,y1=x2,y2, then(1)x2=r1x1,y1,y2=r2x1,y1,for all but finitely many x1,y1∈E1Fq¯ [19].If the degree ofϕ as a group homomorphism is ℓ, the isogeny is called an ℓ-isogeny. If the degree of ϕ is equal to the cardinality of kernel of ϕ, ϕ is called separable. If there exists a separable isogeny between two curves, we say that they are isogenous. For an isogeny ϕ between two curves E1,E2 with E1=E2, we say ϕ is an endomorphism. The set of endomorphisms of an elliptic curve, denoted by end E, has a ring structure with the operations of point-wise addition and function composition.


## 2.2. Isogeny-Based Cryptosystems

Definition 1.
A prime of the formp=ℓAeAℓBeBf±1 is called a smooth isogeny prime, where ℓA and ℓB and small primes, eA and eB, are positive integers, and f is a small cofactor to make p prime.
Isogeny-based cryptosystems use smooth isogeny primes, and the case whereℓA=2 and ℓB=3 is preferred since this case enjoys the fastest known isogeny computations [8]. Let E be an elliptic curve and let m∈ℕ.Definition 2.
LetE be an elliptic curve and let m∈ℕ. Then, Em is called m-torsion subgroup of E, which is the set of points of order m:(2)Em=P∈E|mP=O.
An elliptic curveE over a field of characteristic p has a torsion subgroup Epr for which holds that either Epr=O or Epr=ℤ/prℤ for all r≥1, the first case is called that E is supersingular and the other case is called E is ordinary. There are some hard problem candidate hard problem related to supersingular elliptic curves as follows [20].Problem 1.
Letp,ℓ be distinct prime numbers. Let E1 and E2 be two elliptic curves over Fp2 with #E1Fp2=#E2Fp2=p+12, chosen uniformly at random. Find k∈ℕ and an isogeny of degree ℓk from E1 to E2.
We remark that the ordinary Problem1 stated for the general curve is not known to be equivalent, and that there also exists a subexponential algorithm that computes the endomorphism ring of ordinary curves [21]. Although the best algorithm that computes isogenies is still exponential, there is a subexponential quantum algorithm that computes an isogeny between two ordinary curves [3]; therefore, studies on isogeny-based cryptography are focused on supersingular cases.


## 2.3. Chains for Scalar Multiplication

There are several candidates to reduce the cost of scalar multiplications on elliptic curve cryptosystems. In isogeny-based cryptosystems, the results of the scalar multiplication of elliptic curves are addition chains [15], addition-subtraction chains [16], etc. In this section, we introduce an addition-subtraction chain using double base.Definition 3.
Given two primesp,q∈ℕ, a double-base number system (DBNS) is a representation into which every positive integer n is represented as the linear combination with coefficients in 1,−1 and sum of difference of p,q-integers, i.e., numbers of the form paqb:(3)n=∑i=0ℓdipaiqbi,with di∈−1,1 and a0≥a1≥a2≥…≥aℓ≥0 and b0≥b1≥b2≥…≥bℓ≥0.
The representation of an integern is not unique in both unsigned case and signed case. The most representative algorithm for expressing arbitrary n by DBNS is the greedy algorithm. The greedy algorithm is as follows.Theorem 1 (see [22]).
Algorithm 1 terminates afterk∈Ologn/loglogn steps.Algorithm 1: The greedy algorithm for double-base number system [23].
Input:a0, S=1,−1, NOutput: three sequencesdi,ai,bi0≤i≤ℓ such that N=∑i=0ℓdi2ai3bi with di∈S, a0≥⋯≥aℓ, b0≥⋯≥bℓ(1)
ifa0>log3Nthen(2)
return fail(3)
end if(4)
b0←⌈log2N−a0log23⌉(5)
i,t,s←1,N,1(6)
whilet>0do(7)
find the best approximationz=di2ai3bi of t with di∈S, 0≤ai≤ai−1, and 0≤bi≤bi−1(8)
di←s×di(9)
ift<zthen(10)
s←−s(11)
end if(12)
t←|t−z|(13)
i←i+1(14)
end while(15)
returndi,ai,bii≤i≤ℓIn Algorithm 1, lines 1–3 give the limitation for the input parametera0 and line 4 gives the value of the parameter b0. The parameter a0 is used when the exponentiation a1 of 2 is the biggest term in the expansion, that is, 0≤aℓ≤aℓ−1≤⋯≤a1≤a0. The value of b0 also gives limit of bi ’s similarly.


## 3. Twisted Edwards Curves

### 3.1. Twisted Edwards Curves

Letk be a field of odd characteristic, and a,d∈k with ada−d≠0.Definition 4.
(see [24]). The twisted Edwards curve with coefficients a and d is defined by the equation(4)EE,a,d:ax2+y2=1+dx2y2.
An Edwards curve is a twisted Edwards curve witha=1.
Edwards curves and twisted Edwards curves have been broadly used in cryptography [24]. Every twisted Edwards curve is birationally equivalent to an elliptic curve in Montgomery curve [24].Definition 5.
(see [24]). The twisted Edwards curve EE,a,d:ax2+y2=1+dx2y2 is a quadratic twist of the Edwards curve EE,1,d/a:x˜2+y˜2=1+d/ax˜2y˜2. The map x˜,y˜↦x,y=x˜/a,y˜ is an isomorphism from EE,1,d/a to EE,a,d over ka. If a is a square in k and d∈k∗/k∗2 is not square in k, then EE,a,d is isomorphic to EE,1,d/a over k but not isomorphic to E over k [25]. Generally, EE,a,d is a quadratic twist of EE,a¯,d¯ for a¯,d¯ satisfying d¯/a¯=d/a. Conversely, every quadratic twist of a twisted Edwards curve is isomorphic to a twisted Edwards curve. That is, the set of twisted Edwards curves is invariant under quadratic twists.
LetP=x1,y2 and Q=x2,y2 be points on a twisted Edwards curve EE,a,d. The sum of these points x1,y1,x2,y2 on EE,a,d is(5)P+Q=x1y2+y1x21+dx1x2y1y2,y1y2−ax1x21−dx1x2y1y2.
0,1 is the neutral element of the group, and the opposite of x1,y1 is −x1,y1. These formulas also work for doubling, that is, if P=Q. In particular,(6)2P=2x1y1ax12+y12,y12−ax122−ax12−y12.
In [6], the twisted Edwards curves have simple completeness and support the ADD function. The twisted Edwards model has been considered for implementations because it offers a single simple group law formula that works for all possible inputs. When one can exploit precomputation, the ADD operation used in scalar multiplication for Edwards and twisted Edwards curves[6] can play an important role in improving the speed of scalar multiplication, particularly in the ephemeral Diffie–Hellman key-exchange protocol.


### 3.2. Coordinates

Bernstein et al. [24] offered efficient formulas for addition and doubling for Edwards curves and twisted Edwards curves. They introduced various coordinates for Edwards curves and twisted Edwards curves.Definition 6.
A projective pointx,y,z on ax2+y2=1+dx2y2 is represented as X,Y,Z,T satisfying the following relations: x=X/Z,y=Y/Z,xy=T/Z. The coordinates of the point X:Y:Z:T are called the extended twisted Edwards coordinates. The identity element is represented by 0:1:1:0. The opposite of a point is −X:Y:Z:−T.Definition 7.
The following equation:(7)aX2+Y2Z2=Z4+dX2Y2,is called the projective twisted Edwards curve to avoid inversions. For Z1≠0, the homogeneous point X1:Y1:Z1 represents the affine point X1/Z1,Y1/Z1 on EE,a,d.Definition 8.
Another way to avoid inversions is using a pointX1:Y1:Z1 with X1Y1Z1≠0 to represent the affine point Z1/X1,Z1/Y1 on EE,a,d. These points are called the inverted twisted Edwards coordinates.
The following Table1 shows the complexity of addition and doubling calculated according to the considered coordinates of the curves, that DBL is point doubling, ADD is point addition, mADD is mixed point addition: addition of an input that has been scaled to have Z-coordinate 1, mDBL is mixed doubling: doubling of an input that has been scaled to have Z-coordinate 1.
Bos and Friedberger [16] proposed an algorithm to compute scalar multiplications on twisted Edwards curves using addition-subtraction chains. Their results show improved speed of scalar multiplication compared to the Montgomery curves most commonly used in isogeny-based cryptography systems. They also show that using larger scalar values in scalar multiplication leads to better performance. However, their chains are difficult to find for such large numbers, and the operations are generally more expensive; therefore, it is unclear if twisted Edwards curves can become faster in their setting. The present work was motivated by the results of Bos and Friedberger’s research. We propose the use of a double-base addition-subtraction chain on twisted Edwards curves with projective coordinates, which led us to think about the efficiency of scalar multiplication.Table 1
Costs of addition and doubling operations in twisted Edwards curve.
Curve, representationDBLADDmADDmDBLTwisted Edwards curve with projective coordinates711106Twisted Edwards curve with inverted coordinates71096Twisted Edwards curve with extended coordinates8987


## 3.1. Twisted Edwards Curves

Letk be a field of odd characteristic, and a,d∈k with ada−d≠0.Definition 4.
(see [24]). The twisted Edwards curve with coefficients a and d is defined by the equation(4)EE,a,d:ax2+y2=1+dx2y2.
An Edwards curve is a twisted Edwards curve witha=1.
Edwards curves and twisted Edwards curves have been broadly used in cryptography [24]. Every twisted Edwards curve is birationally equivalent to an elliptic curve in Montgomery curve [24].Definition 5.
(see [24]). The twisted Edwards curve EE,a,d:ax2+y2=1+dx2y2 is a quadratic twist of the Edwards curve EE,1,d/a:x˜2+y˜2=1+d/ax˜2y˜2. The map x˜,y˜↦x,y=x˜/a,y˜ is an isomorphism from EE,1,d/a to EE,a,d over ka. If a is a square in k and d∈k∗/k∗2 is not square in k, then EE,a,d is isomorphic to EE,1,d/a over k but not isomorphic to E over k [25]. Generally, EE,a,d is a quadratic twist of EE,a¯,d¯ for a¯,d¯ satisfying d¯/a¯=d/a. Conversely, every quadratic twist of a twisted Edwards curve is isomorphic to a twisted Edwards curve. That is, the set of twisted Edwards curves is invariant under quadratic twists.
LetP=x1,y2 and Q=x2,y2 be points on a twisted Edwards curve EE,a,d. The sum of these points x1,y1,x2,y2 on EE,a,d is(5)P+Q=x1y2+y1x21+dx1x2y1y2,y1y2−ax1x21−dx1x2y1y2.
0,1 is the neutral element of the group, and the opposite of x1,y1 is −x1,y1. These formulas also work for doubling, that is, if P=Q. In particular,(6)2P=2x1y1ax12+y12,y12−ax122−ax12−y12.
In [6], the twisted Edwards curves have simple completeness and support the ADD function. The twisted Edwards model has been considered for implementations because it offers a single simple group law formula that works for all possible inputs. When one can exploit precomputation, the ADD operation used in scalar multiplication for Edwards and twisted Edwards curves[6] can play an important role in improving the speed of scalar multiplication, particularly in the ephemeral Diffie–Hellman key-exchange protocol.


## 3.2. Coordinates

Bernstein et al. [24] offered efficient formulas for addition and doubling for Edwards curves and twisted Edwards curves. They introduced various coordinates for Edwards curves and twisted Edwards curves.Definition 6.
A projective pointx,y,z on ax2+y2=1+dx2y2 is represented as X,Y,Z,T satisfying the following relations: x=X/Z,y=Y/Z,xy=T/Z. The coordinates of the point X:Y:Z:T are called the extended twisted Edwards coordinates. The identity element is represented by 0:1:1:0. The opposite of a point is −X:Y:Z:−T.Definition 7.
The following equation:(7)aX2+Y2Z2=Z4+dX2Y2,is called the projective twisted Edwards curve to avoid inversions. For Z1≠0, the homogeneous point X1:Y1:Z1 represents the affine point X1/Z1,Y1/Z1 on EE,a,d.Definition 8.
Another way to avoid inversions is using a pointX1:Y1:Z1 with X1Y1Z1≠0 to represent the affine point Z1/X1,Z1/Y1 on EE,a,d. These points are called the inverted twisted Edwards coordinates.
The following Table1 shows the complexity of addition and doubling calculated according to the considered coordinates of the curves, that DBL is point doubling, ADD is point addition, mADD is mixed point addition: addition of an input that has been scaled to have Z-coordinate 1, mDBL is mixed doubling: doubling of an input that has been scaled to have Z-coordinate 1.
Bos and Friedberger [16] proposed an algorithm to compute scalar multiplications on twisted Edwards curves using addition-subtraction chains. Their results show improved speed of scalar multiplication compared to the Montgomery curves most commonly used in isogeny-based cryptography systems. They also show that using larger scalar values in scalar multiplication leads to better performance. However, their chains are difficult to find for such large numbers, and the operations are generally more expensive; therefore, it is unclear if twisted Edwards curves can become faster in their setting. The present work was motivated by the results of Bos and Friedberger’s research. We propose the use of a double-base addition-subtraction chain on twisted Edwards curves with projective coordinates, which led us to think about the efficiency of scalar multiplication.Table 1
Costs of addition and doubling operations in twisted Edwards curve.
Curve, representationDBLADDmADDmDBLTwisted Edwards curve with projective coordinates711106Twisted Edwards curve with inverted coordinates71096Twisted Edwards curve with extended coordinates8987


## 4. Memory-Efficient Algorithm for Scalar Multiplications

In terms of addition and doubling operations in twisted Edwards curves, we use the following notations.(1)
ADDresp. SUB: the cost of point addition (resp. subtraction)(2)
M: number of field multiplications(3)
D: number of field doublings(4)
S: number of field squarings(5)
T: number of field triplings(6)
I: number of field inversionsBos and Friedberger [16] showed that scalar multiplications are more effective in twisted Edwards curves than they are in Montgomery curves for isogeny-based protocols. In this section, we introduce an algorithm that improves upon those of Bos and Friedberger [16] and Yu et al. [18] in terms of memory. Our method first uses double-base addition-subtraction chains. Secondly, we use twisted Edwards curves with projective coordinates to improve the addition and subtraction calculations determined by the chains in isogeny-based cryptosystems.We show that the following algorithm generates addition-subtraction chains using a double base to improve the total complexity. Addition-subtraction chains with double base can generate chains that are much shorter than a single-base chain. This means that the number of operations in terms of addition and subtraction calculations can be reduced. A decrease in the length of the chain suggests a more optimized structure. After a short chain with double base is achieved using Algorithm 2, we use the twisted Edwards curves with projective coordinates to reduce the complexity of the addition and subtraction calculation, since the projective twisted Edwards curves allow for computing inversions to be avoided. That is, the projective twisted Edward curves haveADD=SUB=10M+1S=11M for S=1M, D=3M+4S=7M, T=9M+3S=12M, I=100M (see the twisted Edwards curve projective row in the 1st table in [26]). We can thus see that the total complexity can be reduced by adjusting the number of additions and subtractions. Therefore, in terms of total complexity, our algorithm decreases the addition part because the length of the chain is decreased.Algorithm 2: A modified greedy algorithm for isogeny-based cryptography.
Input:NOutput: an addition-subtraction multiplication chainc for N(1)
b←⌈log3N/2⌉(2)
a←⌈log3N−blog23⌉(3)
i,t,s←0,N,1(4)
whilet≠0do(5)
Find the pair of integersα,β with 0≤α≤a,0≤β≤b such that 2α3β is the closest number to t(6)
vi←s,α,β(7)
t←t−s⋅2α3β(8)
ift>0then(9)
s←1(10)
else ift<0then(11)
s←−1(12)
else(13)
returnv0,…,vi(14)
end if(15)
i←i+1(16)
a,b←α,β(17)
end whileWe provide a modified greedy algorithm for isogeny-based cryptography, which is used to produce a double-base addition-subtraction chain for each givenN to compute the scalar multiplication NP, where P is a point in a twisted Edwards curve with projective coordinates over Fq2. Furthermore, to avoid the large inversion part of the calculation, we work on twisted Edwards curve with projective coordinates.In Algorithm 2, checking the integersα and β for all 0≤α≤a and 0≤β≤b is very inefficient, since it is necessary to repeat Ologn times to find and compare the values t−2x3y where 0≤y≤b for fixed 0≤x≤a, whose complexity is Ologn. As an efficient way to obtain α and β, we suggest Algorithm 3, which is an application of the binary search [27] and which only requires Ologlogn iterations.Algorithm 3: An efficient way to obtain α and β in Algorithm 2.
Input:tOutput:α,β with 0≤α≤a,0≤β≤b such that 2α3β is the closest number to t(1)
i←b,v←0,0,0(2)
x←30,31,…,3b(3)
whilei≠0do(4)
F←0, L←a(5)
whileF≤Ldo(6)
M←⌈F+L/2⌉(7)
if2M3xi<tthen(8)
F←M+1(9)
else if2M3xi>tthen(10)
L←M−1(11)
else(12)
vtmp←πt−2M3xi,M,xi(13)
end if(14)
end while(15)
if2M3xi<tthen(16)
ift<3⋅2M−23xithen(17)
vtmp←t−2M−13xi,M−1,xi(18)
else(19)
vtmp←t−2M3xi,M,xi(20)
end if(21)
else(22)
ift<3⋅2M−13xi then(23)
vtmp←t−2M3xi,M,xi(24)
else(25)
vtmp←t−2M+13xi,M+1,xi(26)
end if(27)
end if(28)
ifv=0,0,0orv0>vtmp0then(29)
v←vtmp(30)
end if(31)
i←i−1(32)
end while(33)
returnv1,v2Note that the required number of steps of Algorithm 2 is equivalent to that of Algorithm 1, in big-O notation manner. By combining Algorithm 3, we obtain an addition-subtraction multiplication chain c for N whose number of iterations is Ologn/loglogn⋅loglogn=Ologn. It is equivalent to many existing results such as those in [6, 17, 22] which are focusing on the speed to find a chain.For example, whenN=72641, the double-base chain is(8)72641=2736−2536+2534+2332=2131223122323222−1+1+1−1−1.In this case, the number of doubling is 7, tripling is 6, and addition (or subtraction) is 5. Therefore, the complexity is7⋅7+12⋅6+11⋅5=176M. A single-based chain [28] is(9)72641=217−216+213−211+210−27+26−20=26223222232−1+1−1+1−1+1−1.In this case, the number of doubling is 17, and addition (or subtraction) is 7. Therefore, the complexity is7⋅17+11⋅7=196M.To find a short chain, various techniques are considered, such as a brute force approach [16] or a tree-based approach [29]. However, these approaches require huge amounts of memory for the following reasons. First, these approaches use recursive calls. These approaches also search for and store the chains in the intermediate stage, which are useless in the final stage, thus representing a burden on memory. As the number of chains required to conduct scalar multiplications increases, the burden on memory increases dramatically because the number of chains under consideration increases exponentially. By contrast, Algorithm 2 provides a memory-efficient system because it requires a total of 3×l+1 array. The burden on memory does not increase exponentially, as it only increases linearly. Therefore, in terms of memory efficiency, the approach based on a modified greedy algorithm is a good choice for scalar multiplication.In Algorithm 3, first, the values of powers of 3 are stored to find the number2α3β, which is closest to t faster, and t is then compared with the following values: 203i,213i,…,2a3i with the rules in binary search. For example, let t=53 and say that we have to find the closest number to t in the following numbers: 2031,2131,…,21031 First, take 2531=96 and compare it to t. Since t<96, we only need to compare t to 2031,…,2431, and then take 2231=12 and compare it with t. Since t>12, we only need to compare t with 2331,2431. Finally, take 2431=48 and compare it to t. Since t>48, the remaining step is to compare t−2431 to t−2531.Hence, we obtain that2431=48 is the closest number to t when the power of 3 is fixed to 1. Now, we can find the numbers of the form 2M3i closest to t for each fixed i, and by checking for all i, we obtain the closest number to t between 0 and 2a3b. Hence, we find that 2431 = 48 is the closest number to t when the power of 3 is fixed to 1. Now, we can find the numbers of the form 2M3i that are closest to t for each fixed i, and by checking for all i, we obtain the closest number to t between 0 and 2a3b.The memory of our algorithm is compared to the amount of memory in Yu et al. [18], a recent study of the same double-base addition-subtraction chain. Because Yu et al.’s results are also more recent than those of Bos and Friedberger, and Bos and Friedberger’s results still show no results on the amount of memory in the algorithm. The part that takes up the most memory is line 4 and line 5 in Algorithm 2. The memory usage of this part is (the chain length) Ologn, that is, Ologn2/loglogn. It is better than the memory usage of the tree-based approach, that is, Ologn2 [18].To do the practical experiment, we letn be a fixed positive integer and generate ten random numbers between 2n−1 and 2n. In other words, we generate ten n-bit integers N, and then we write(i)
#M: the average value of the number of multiplications for scalar multiplication,(ii)
#M/bit: the number of multiplications per number of bits,(iii)
Improvement: the percentage of improvementsrelative to the result of the binary representation for each case in Table 2. Our algorithm obtains a complexity result that improves by more than 20% for large scalars, i.e., above 160 bits in scalar multiplication, which is comparable to that of Al Musa [17].Table 2
The comparison of the different models.
# of bits#M#M/bitImprovement (%)BinaryModified greedyBinaryModified greedyN=173108.5M123M8.359.46−13.36N=193112.75M128M8.679.85−13.531601990.1M1559.6M12.449.75+21.632242787.9M2168.4M12.459.68+22.222563198.9M2480.3M12.59.69+22.463844847.3M3711.8M12.629.67+23.435126370.3M5020.9M12.449.81+21.18


## 5. Conclusion

In this paper, we first use double-base addition-subtraction chains. We also use twisted Edwards curves with projective coordinates to improve the addition and subtraction calculations in the chain. Our algorithm generates addition-subtraction chains using double base to improve the total complexity. The memory used by our algorithm to execute scalar multiplication is better than the result of the tree-based approach [17]. This memory efficiency leads to efficient scalar multiplication. That is, it can also be applied to efficient scalar multiplexing in isogeny-based cryptosystems. We also show experimental results demonstrating that the length of the chain is much shorter; therefore, for scalar multiplication in an isogeny-based cryptosystem, the complexity is reduced by 20% compared to the single-base number system. These results are also expected to contribute to research improving the efficiency of SIDH and SIKE-based protocols, which comprise one of the candidate groups for post-quantum cryptosystems. We can also consider implementing it in terms of efficiency in multisystem and network environments such as those in [30–33].



---

*Source: 3846369-2022-04-27.xml*