# On the Performance Analysis for CSIDH-Based Cryptosystems
## 2 Montgomery Curve and Tweaked Montgomery Curve
### Odd-Degree Isogeny Formulas on \(M_{a}\) and \(M_{a}^{t}\)  
In [16], [PERSON] and [PERSON] proposed a formula for computing an arbitrary odd-degree isogenies on the Montgomery curves. Let \(P=(x_{1},y_{1})\) be a point on a Montgomery curve \(M_{a}\), having order \(\ell=2d+1\) and let \((x_{i},y_{i})=[i]P\). Then \(\ell\)-isogeny \(\phi\) from \(M_{a}\) to \(M_{a^{\prime}}=M_{a}/\left\langle P\right\rangle\) is given by:  
\[\phi:(x,y)\rightarrow(f(x),y\cdot f^{\prime}(x))\]  
where  
\[f(x)=x\cdot\prod_{i=1}^{d}\left(\frac{xx_{i}-1}{x-x_{i}}\right)^{2}\]  
In the above equation, \(f^{\prime}(x)\) is derivative of \(f(x)\) and \(a^{\prime}=(6\tilde{\sigma}-6\sigma+a)\pi^{2}\) for \(\sigma=\sum_{i=1}^{d}x_{i}\), \(\tilde{\sigma}=\sum_{i=1}^{d}1/x_{i}\), and \(\pi=\prod_{i=1}^{d}x_{i}\). Now, in projective \(XZ\)-coordinate, let \([i]P=P_{i}=(X_{i}:Z_{i})\), where \(x_{i}=X_{i}/Z_{i}\) and \(P_{1}=P\). Then the evaluation of an isogeny refers to the computation of the image point of \(\phi\). Let \(Q=(X:Z)\) be another point on \(M_{a}\) and \(\phi(Q)=(X^{\prime}:Z^{\prime})\). Then \(X^{\prime}\) and \(Z^{\prime}\) are as follows:  
\[X^{\prime} =X\Bigg{(}\prod_{i=1}^{d}[(X-Z)(X_{i}+Z_{i})+(X+Z)(X_{i}-Z_{i})] \Bigg{)}^{2}, \tag{1}\] \[Z^{\prime} =Z\Bigg{(}\prod_{i=1}^{d}[(X-Z)(X_{i}+Z_{i})-(X+Z)(X_{i}-Z_{i})] \Bigg{)}^{2}. \tag{2}\]  
The computational cost of this formula is \((4d)\mathbf{M}+2\mathbf{S}\). For the coefficient of the image curve \(a^{\prime}\), [PERSON] et al. present a formula in projective coordinate in [6], which is as follows:  
\[a^{\prime}=\pi(a-3\sigma),\]  
where \(\pi=\prod_{i=1}^{\ell-1}\frac{X_{i}}{Z_{i}}\) and \(\sigma=\sum_{i=1}^{\ell-1}(\frac{X_{i}}{Z_{i}}-\frac{Z_{i}}{X_{i}})\). Which can be computed in \((6d-2)\mathbf{M}+3\mathbf{S}\). For the isogeny evaluation and computing the curve coefficient of the image curve of a tweaked Montgomery curve \(M_{a}^{t}\) presented in [14], \(f(x)\) is now defined as:  
\[f(x)=x\cdot\prod_{i=1}^{d}\left(\frac{xx_{i}+1}{x-x_{i}}\right)^{2}\]Let \(P\) be a point on \(M_{a}^{t}\), having order \(\ell=2d+1\). In projective coordinate, let \([i]P=P_{i}=(X_{i}:Z_{i})\), where \(x_{i}=X_{i}/Z_{i}\) and \(P_{1}=P\). Let \(\phi\) be an \(\ell\)-isogeny from \(M_{a}^{t}\) to \(M_{a^{\prime}}^{t}=M_{a}^{t}/\langle P\rangle\). Let \(Q=(X:Z)\) be another point on \(M_{a}^{t}\) and let \(\phi(Q)=(X^{\prime}:Z^{\prime})\). Then \(X^{\prime}\) and \(Z^{\prime}\) are as follows:  
\[X^{\prime} =X\Bigg{(}\prod_{i=1}^{d}(XX_{i}+ZZ_{i})\Bigg{)}^{2}, \tag{3}\] \[Z^{\prime} =Z\Bigg{(}\prod_{i=1}^{d}(XZ_{i}-ZX_{i})\Bigg{)}^{2}. \tag{4}\]  
Similar to the case for computing the differential addition, note that for (3) and (4), the optimized computation methods like (1) and (2) do not exist. So, the computational cost of odd-degree isogeny point evaluation on the tweaked Montgomery curve is \((6d)\mathbf{M}+2\mathbf{S}\). Formula in [14] for computing the coefficient of the image curve \(a^{\prime}\), is similar to the formula for Montgomery curve which is  
\[a^{\prime}=\pi(a-3\sigma),\]  
where \(\pi=\prod_{i=1}^{\ell-1}\frac{X_{i}}{Z_{i}}\) and \(\sigma=\sum_{i=1}^{\ell-1}(\frac{X_{i}}{Z_{i}}+\frac{Z_{i}}{X_{i}})\). This can be computed in \((6d-2)\mathbf{M}+3\mathbf{S}\). Summarizing the section, Table 1 presents the computational cost of the elliptic curve arithmetic and isogeny operations on Montgomery and tweaked Montgomery curves. In Table 1, DBLADD refers to the differential addition with doubling, and DBL refers to the doubling. \(\ell\)-isogeny eval. denotes the evaluation of an \(\ell\)-isogeny, and \(\ell\)-isogeny coeff. denotes the computation of the coefficient of the image curve for an \(\ell\)-isogeny. **Remark 1**. : _In [10], [PERSON] and [PERSON] proposed a hybrid version of CSIDH, which exploits Edwards curves for recovering the coefficient of the image curve. By using the efficiency of the birational equivalence between Montgomery and Edwards curves, the coefficient of the image curve is obtained using the Edwards isogeny formula.